Алгоритм F4 был предложен Жан-Шарль Фожером (Jean-Charles Faugerе) в 1999 г как новый эффективный алгоритм вычисления базиса Грёбнера[1]. Этот алгоритм вычисляет базис Грёбнера идеала в кольце многочленов с помощью серии стандартной процедуры линейной алгебры: приведений матриц к ступенчатому виду. Он является одним из самых быстрых на сегодняшний день.
Алгоритм
Определения
- Критическая пара
является членом
![{\displaystyle T\cdot T\cdot K[x_{1},...,x_{n}]\cdot T\cdot K[x_{1},...,x_{n}],Pair(f_{i},f_{j}):=(HOK_{ij},t_{i},f_{i},t_{j},f_{j})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ee549f372cdacabe3dc94b026e3e7397cc298b0)
такое, что

- Определим степень критической пары
как
.
- Определим следующие операторы:
and 
Псевдокод алгоритма F4 (упрощённая версия)
Вход: ![{\displaystyle {\begin{cases}F{\text{ конечное подмножество }}K[X_{1},...,X_{n}]\\Sel{\text{ функция }}List(Pairs)\rightarrow List(Pairs)\\{\text{такое, что }}Sel(I)\neq \varnothing {\text{ если }}I\neq \varnothing \end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa7ab5cf3356779cb85ffc96cae579ac7ff28d08)
Выход: конечное подмножество ![{\displaystyle K[X_{1},...,X_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e20fd61950fb293653d0124f442fc8d98f3d9e76)

While
do





for
do

return 
Алгоритм редукции
Теперь мы можем расширить определение редукции полинома по модулю
подмножества
, до редукции подмножества
по
модулю другого подмножества
:
Вход: L, G конечные подмножества ![{\displaystyle K[X_{1},...,X_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e20fd61950fb293653d0124f442fc8d98f3d9e76)
Выход: конечные подмножества
(Может быть пустым)



return 
Арифметическая операция не используется: это символьный препроцессинг.
Алгоритм Символьного Препроцессинга
Вход: L, G конечные подмножества ![{\displaystyle K[X_{1},...,X_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e20fd61950fb293653d0124f442fc8d98f3d9e76)
Выход: конечные подмножества ![{\displaystyle K[X_{1},...,X_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e20fd61950fb293653d0124f442fc8d98f3d9e76)


while
do


if
приводим сверху по модулю
then
существует 

return 
Лемма
Для всех многочленов
, мы имеем ![{\displaystyle p{\xrightarrow[{}]{G\cup {\tilde {F}}+}}0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/301802a083718911cd2a7c1a38b429a72ff0a2ac)
Теорема (без доказательства)
Алгоритм
вычисляет базис Гребнера G в ![{\displaystyle K[X_{1},...,X_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e20fd61950fb293653d0124f442fc8d98f3d9e76)
такой что 
Замечание
Если #
для всех
, тогда алгоритм
сводится к алгоритму Бухбергера. В этом случае функция Sel является эквивалентом стратегии выбора для алгоритма Бухбергера.
Функция выбора
Вход:
список критических пар
Выход: список критических пар


return 
Назовём эту стратегию нормальной стратегией для
.
Следовательно, если входные полиномы однородны, мы получаем в степени, и d - базис Гребнера.
На следующем шаге мы выбираем все критические пары, необходимые для вычисления базиса Гребнера в степени d+1.
Оптимизация алгоритма F4
Существует несколько путей оптимизации алгоритма:
- включение критерия Бухбергера (или критерия F5);
- повторное использование всех строк в приведённых матрицах.
Критерии Бухбергера Алгоритм - реализация:

Вход: ![{\displaystyle {\begin{cases}{\text{конечное подмножество }}G_{old}{\text{ в }}K[X_{1},...,X_{n}]\\{\text{конечное подмножество }}P_{old}{\text{ критических пар в }}K[X_{1},...,X_{n}]\\0\neq h\in K[x_{1},...,X_{n}]\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6f798e7cef13c3efbea4ada56bc05731afcad30)
Выход: конечное подмножество в
обновлённый список критических пар
Пседвокод алгоритма F4 (с критерием)
Вход: ![{\displaystyle {\begin{cases}F\subset K[X_{1},...,X_{n}]\\Sel{\text{ функция }}List(Pairs)\rightarrow List(Pairs)\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/394d1a49588581c4d1b49191f48a8c2c02428ad0)
Выход: конечное подмножество
.

while
do


while
do




for 


return 
Пусть есть некоторое конечное множество многочленов
. По этому множеству строится большая разреженная матрица, строки которой соответствуют многочленам из
, а столбцы — мономам. В матрице записаны коэффициенты многочленов при соответствующих мономах. Столбцы матрицы отсортированы согласно выбранному мономиальному упорядочению (старший моном соответствует первому столбцу). Приведение такой матрицы к ступенчатому виду позволяет узнать базис линейной оболочки многочленов из
в пространстве многочленов.
Пусть в классическом алгоритме Бухбергера требуется провести шаг редукции многочлена
относительно
, и при этом
должен быть домножен на моном
. В алгоритме F4 в матрицу будут специально помещены
и 
. Утверждается, что можно заранее подготовить множество всех потенциальных домноженных редукторов, которые могут потребоваться, и поместить их заранее в матрицу.[2]
Обобщим алгоритм F4[3]:
пусть нам требуется отредуцировать многочлен
относительно множества
. Для этого мы
(1) добавляем
в матрицу;
(2) строим носитель
многочлена
(множество мономов);
(3) если
пусто, то заканчиваем процедуру;
(4) выбираем максимальный моном
в
(и выкидываем его из
);
(5) если
не делится ни на один старший моном элементов
, то переходим к шагу (3);
(6) иначе выбираем редуктор
∈
(и дополнительный множитель
): тогда 
;
(7) добавляем
в матрицу;
(8) добавляем мономы многочлена
(кроме старшего
) ко множеству
;
(9) переходим к шагу (3).
Эта процедура пополнения матрицы домноженными редукторами называется символьным препроцессингом. Кроме того, вместо S-полиномов можно поместить в матрицу их левые и правые части (при редукции одной строки по другой автоматически получится S-полином).
Наконец, третьим отличием от алгоритма Бухбергера является то, что в алгоритме F4 разрешается поместить в одну матрицу части сразу нескольких S-полиномов, выбранных согласно какой-либо стратегии. Так, если на каждом шаге выбирается один S-полином, то он повторяет классический алгоритм Бухбергера.
Другая крайность — когда на очередном шаге редуцируется множество всех имеющихся S-полиномов. Это тоже не очень эффективно из-за больших размеров матриц. Автор алгоритма Ж.-Ш. Фожер предложил нормальную стратегию выбора S-полиномов для редукции[4], согласно которой выбираются S-полиномы с наименьшей степенью левых и правых частей. Она даёт хорошие эмпирические результаты для упорядочения DegRevLex и ее выбор является естественным для однородных идеалов.
В алгоритм можно внести несколько естественных усовершенствований. Как и в классическом алгоритме вычисления базиса Грёбнера, можно применять критерии Бухбергера для отсеивания заведомо ненужных S-полиномов.
Реализации
Реализован алгоритм F4
- в FGb - собственная реализация Фожера[4], которая включает интерфейсы для его использования из C/C ++ или Maple;
- в системе компьютерной алгебры Maple в качестве опции method = fgb функции Groebner [gbasis];
- в системе компьютерной алгебры Magma , в системе компьютерной алгебры SageMath.
Пример
Задача: посчитать базис Грёбнера для многочленов
В начале присваиваем

1) Символьный препроцессинг

уже готов.
2) Символьный препроцессинг

сверху сводится к
.
3) Символьный препроцессинг

не сводится к
.
4) 
Матричное представление полученного
:

Редукция Гаусса полученной матрицы
:

По этой матрице получаем:
![{\displaystyle {\tilde {F_{1}}}=[f_{5}=ad+bd+cd+d^{2},f_{6}=ab+bc-bd-d^{2},f_{7}=b^{2}+2bd+d^{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fd416bdc284a7bcfde1c82873d71bf1c4212f30)
А так как
, то
и тогда 
Для следующего шага мы должны рассмотреть 
Отсюда 
В Символьном препроцессинге можно попытаться упростить
используя предыдущие вычисления:
Например,
1) Символьный препроцессинг

2) Символьный препроцессинг

3) Символьный препроцессинг


Опишем упрощение
Цель: заменить любое произведение
на произведение
, где
- ранее вычисленная строка, а
делит моном 
В первом варианте алгоритма: некоторые строки матрицы никогда не используются (строки в матрице
).
Новая версия алгоритма: мы сохраняем эти строки


SIMPLIFY пытается заменить произведение
произведением
, где
уже вычисленная строка в гауссовой редукции, и u t делит моном m; Если мы нашли такое лучшее произведение, то рекурсивно вызываем функцию SIMPLIFY:
Вход: ![{\displaystyle {\begin{cases}t\in T{\text{ моном}}\\t\in K[X_{1},...,X_{n}]{\text{ многочлен}}\\F=(F_{i})_{d=1,...,(d-1)},{\text{ Где }}F_{k}\in K[X_{1},...,X_{n}]\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2688cdb147c5c420d32da2c839ae59cf839daf5e)
Выход: Результат
эквивалентно 
for
do
if 


if 
return 
else return 
return 
Algorithm SYMBOLICPREPROCESSING
Вход: ![{\displaystyle {\begin{cases}L,G{\text{ конечные подмножества }}K[X_{1},...,X_{n}]\\F=(F_{i})_{d=1,...,(d-1)},{\text{ Где }}F_{k}\\{\text{конечное подмножество}}K[X_{1},...,X_{n}]\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d32bab48adebbbc91b4b5ee7ca390503ac2bf875)
Выход: конечное подмножество
.


while
do

if
приводим сверху по модулю
then
существует 

return 
Теперь возвращаемся к примеру.
4) Символьный препроцессинг

И так далее....
5) Символьный препроцессинг
![{\displaystyle F_{2}=[cf_{5},df_{7},bf_{5},f_{2},cf_{6}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d14d18599e0cd17b5ef272610c2cb8bbaf426637)

После редукции Гаусса:


и 
На следующем шаге имеем:

и рекурсивно вызываем упрощение:

На следующем шаге имеем:
и ![{\displaystyle F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13},df_{13},df_{10}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd1cc33b4d1d187b0f4f375a92e876cd5c1a540b)
После некоторых вычислений, получается, что ранг
составляет 5.
Это означает, что есть бесполезное сведение к нулю.
На следующем шаге имеем:
и ![{\displaystyle F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7ac352e4335af48e3cbb992edd1155f60a7e8df)
Символьный препроцессинг
![{\displaystyle F_{3}=[f_{1},df_{12},c^{2}f_{5},bf_{13},df_{13},df_{10}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9020b693b7f1bfea250310287e16a5ff83f5d120)

Ссылки
- https://en.wikipedia.org/wiki/Magma_(computer_algebra_system)
Примечания
Литература
- J.-C. Faug`ere. A new efficient algorithm for computing Gr¨obner bases without reduction to zero (F5).
- J.-C. Faug`ere A New Efficient Algorithm for Computing Gr¨obner Bases (F4). Journal of Pure and Applied Algebra, 139 (1999), 61–88.
- Cox D., Little J., O’Shea D., Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, New York, NY: Springer, 1998. [Имеется перевод: Кокс Д., Литтл Дж., О’Ши Д., Идеалы, многообразия и алгоритмы, М., Мир, 2000.]