Алгоритм 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.
Это означает, что есть бесполезное сведение к нулю.
На следующем шаге имеем:
и
Символьный препроцессинг
Примечания
Литература 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.]
Категория:Алгоритмы