F4 (алгоритм)

Алгоритм F4 был предложен Жан-Шарль Фожером (Jean-Charles Faugerе) в 1999 г как новый эффективный алгоритм вычисления базиса Грёбнера. Этот алгоритм вычисляет базис Грёбнера идеала в кольце многочленов с помощью серии стандартной процедуры линейной алгебры: приведений матриц к ступенчатому виду. Он является одним из самых быстрых на сегодняшний день.

Алгоритм

Определения 

 Критическая пара  является членом

такое, что

 Определим степень критической пары  как . 

 Определим следующие операторы:  and

Псевдокод алгоритма F4 (упрощённая версия) 
Вход: 

Выход: конечное подмножество 

While  do

for  do

return

Алгоритм редукции 
Теперь мы можем расширить определение редукции полинома по модулю

подмножества , до редукции подмножества  по

модулю другого подмножества :Вход: L, G конечные подмножества 

Выход: конечные подмножества  (Может быть пустым)

return  Арифметическая операция не используется: это символьный препроцессинг.

Алгоритм Символьного Препроцессинга 
Вход: L, G конечные подмножества 

Выход: конечные подмножества  

while  do

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

существует 

return

Лемма 
Для всех многочленов , мы имеем

Теорема (без доказательства) 
Алгоритм  вычисляет базис Гребнера G в  

такой что 

Замечание

Если # для всех , тогда алгоритм  сводится к алгоритму Бухбергера. В этом случае функция Sel является эквивалентом стратегии выбора для алгоритма Бухбергера.

Функция выбора 
Вход:  список критических пар

Выход: список критических пар

return Назовём эту стратегию нормальной стратегией для .

Следовательно, если входные полиномы однородны, мы получаем в степени, и d -  базис Гребнера. 

На следующем шаге мы выбираем все критические пары, необходимые для вычисления базиса Гребнера в степени d+1.

Оптимизация алгоритма F4 
Существует несколько путей оптимизации алгоритма: 

 включение критерия Бухбергера (или критерия F5);

 повторное использование всех строк в приведённых матрицах.

Критерии Бухбергера Алгоритм - реализация:Вход: 

Выход: конечное подмножество в  обновлённый список критических пар

Пседвокод алгоритма F4 (с критерием) 
Вход: 

Выход: конечное подмножество .

while  do

while  do

for 

return

F4 и его отличия от Алгоритма Бухбергера 
Пусть есть некоторое конечное множество многочленов . По этому множеству строится большая разреженная матрица, строки которой соответствуют многочленам из , а столбцы — мономам. В матрице записаны коэффициенты многочленов при соответствующих мономах. Столбцы матрицы отсортированы согласно выбранному мономиальному упорядочению (старший моном соответствует первому столбцу). Приведение такой матрицы к ступенчатому виду позволяет узнать базис линейной оболочки многочленов из  в пространстве многочленов. 

Пусть в классическом алгоритме Бухбергера требуется провести шаг редукции многочлена  относительно , и при этом  должен быть домножен на моном . В алгоритме F4 в матрицу будут специально помещены  и . Утверждается, что можно заранее подготовить множество всех потенциальных домноженных редукторов, которые могут потребоваться, и поместить их заранее в  матрицу.

Обобщим алгоритм F4:

пусть нам требуется отредуцировать многочлен  относительно множества . Для этого мы

(1) добавляем  в матрицу; 

(2) строим носитель  многочлена  (множество мономов); 

(3) если  пусто, то заканчиваем процедуру; 

(4) выбираем максимальный моном  в  (и выкидываем его из ); 

(5) если  не делится ни на один старший моном элементов , то переходим к шагу (3); 

(6) иначе выбираем редуктор  ∈  (и дополнительный множитель ): тогда  ; 

(7) добавляем  в матрицу; 

(8) добавляем мономы многочлена  (кроме старшего ) ко множеству ; 

(9) переходим к шагу (3).

Эта процедура пополнения матрицы домноженными редукторами называется символьным препроцессингом. Кроме того, вместо S-полиномов можно поместить в матрицу их левые и правые части (при редукции одной строки по другой автоматически получится S-полином). 

Наконец, третьим отличием от алгоритма Бухбергера является то, что в алгоритме F4 разрешается поместить в одну матрицу части сразу нескольких S-полиномов, выбранных согласно какой-либо стратегии. Так, если на каждом шаге выбирается один S-полином, то он повторяет классический алгоритм Бухбергера. 

Другая крайность — когда на очередном шаге редуцируется множество всех имеющихся S-полиномов. Это тоже не очень эффективно из-за больших размеров матриц. Автор алгоритма Ж.-Ш. Фожер предложил нормальную стратегию выбора S-полиномов для редукции, согласно которой выбираются S-полиномы с наименьшей степенью левых и правых частей. Она даёт хорошие эмпирические результаты для упорядочения DegRevLex и ее выбор является естественным для однородных идеалов.

В алгоритм можно внести несколько естественных усовершенствований. Как и в классическом алгоритме вычисления базиса Грёбнера, можно применять критерии Бухбергера для отсеивания заведомо ненужных S-полиномов.

Реализации 
Реализован алгоритм F4 

 в FGb - собственная реализация Фожера, которая включает интерфейсы для его использования из C/C ++ или Maple;
 в системе компьютерной алгебры Maple в качестве опции method = fgb функции Groebner [gbasis];
 в системе компьютерной алгебры Magma , в системе компьютерной алгебры SageMath.

Пример 
Задача: посчитать базис Грёбнера для многочленов В начале присваиваем    

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

 уже готов.

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

 сверху сводится к .

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

 не сводится к .

4) 

Матричное представление полученного :

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

По этой матрице получаем:

А так как , то 

 и тогда  

Для следующего шага мы должны рассмотреть 

Отсюда 

В Символьном препроцессинге можно попытаться упростить   используя предыдущие вычисления: 

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

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

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

Опишем упрощение 
Цель: заменить любое произведение  на произведение , где  - ранее вычисленная строка, а  делит моном 

В первом варианте алгоритма: некоторые строки матрицы никогда не используются (строки в матрице ).

Новая версия алгоритма: мы сохраняем эти строки

SIMPLIFY пытается заменить произведение  произведением , где

уже вычисленная строка в гауссовой редукции, и u t делит моном m; Если мы нашли такое лучшее произведение, то рекурсивно вызываем функцию SIMPLIFY:Вход: 

Выход: Результат  эквивалентно 

for  do

if 

if  

return 

else return 

return Algorithm SYMBOLICPREPROCESSING  Вход: 

Выход: конечное подмножество .

while  do

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

существует 

return 

Теперь возвращаемся к примеру.

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

И так далее....

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

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

и 

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

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

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

 и 

После некоторых вычислений, получается, что ранг  составляет 5.

Это означает, что есть бесполезное сведение к нулю.

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

 и 

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

Ссылки 

 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.]

Алгоритмы