F4 (алгоритм) (F4 (glikjnmb))

Перейти к навигации Перейти к поиску

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

Определения

[править | править код]
  • Критическая пара является членом

такое, что

  • Определим степень критической пары как .
  • Определим следующие операторы: 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 в матрицу будут специально помещены и . Утверждается, что можно заранее подготовить множество всех потенциальных домноженных редукторов, которые могут потребоваться, и поместить их заранее в матрицу.[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

  1. в FGb - собственная реализация Фожера[4], которая включает интерфейсы для его использования из C/C ++ или Maple;
  2. в системе компьютерной алгебры Maple в качестве опции method = fgb функции Groebner [gbasis];
  3. в системе компьютерной алгебры 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.

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

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

и

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

  1. https://en.wikipedia.org/wiki/Magma_(computer_algebra_system)

Примечания

[править | править код]
  1. Jean-Charles Faugere. A new efficient algorithm for computing gr¨obner bases (f4). Journal of Pure and Applied Algebra. — 1999.
  2. Исследование базисов Грёбнера // msu. Архивировано 11 июля 2019 года.
  3. [http://www.broune.com/papers/f4.pdf THE F4 ALGORITHM SPEEDING UP GROBNER BASIS COMPUTATIONS USING LINEAR ALGEBRA] // BJARKE HAMMERSHOLT ROUNE. Архивировано 30 декабря 2019 года.
  4. 1 2 собственная реализация Фожер (англ.). Дата обращения: 1 декабря 2020. Архивировано 15 июня 2021 года.

Литература

[править | править код]
  • 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.]