Алгоритм F4 был предложен Жан-Шарль Фожером (Jean-Charles Faugerе) в 1999 г как новый эффективный алгоритм вычисления базиса Грёбнера[1]. Этот алгоритм вычисляет базис Грёбнера идеала в кольце многочленов с помощью серии стандартной процедуры линейной алгебры: приведений матриц к ступенчатому виду. Он является одним из самых быстрых на сегодняшний день.
- Критическая пара
является членом
такое, что
- Определим степень критической пары
как
.
- Определим следующие операторы:
and ![{\displaystyle Right(p_{i,j}):=t_{j}\cdot f_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e5410be0bc8539d6ea586379a5afcf8e930516c)
Вход:
Выход: конечное подмножество
While
do
for
do
return ![{\displaystyle G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
Теперь мы можем расширить определение редукции полинома по модулю
подмножества
, до редукции подмножества
по
модулю другого подмножества
:
Вход: L, G конечные подмножества
Выход: конечные подмножества
(Может быть пустым)
return ![{\displaystyle {\tilde {F^{+}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d6c0780d628f25baa73b730c56c8bbb89f4acc0)
Арифметическая операция не используется: это символьный препроцессинг.
Вход: L, G конечные подмножества
Выход: конечные подмножества
while
do
if
приводим сверху по модулю
then
существует
return ![{\displaystyle F}](https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57)
Для всех многочленов
, мы имеем
Алгоритм
вычисляет базис Гребнера G в
такой что
Замечание
Если #
для всех
, тогда алгоритм
сводится к алгоритму Бухбергера. В этом случае функция Sel является эквивалентом стратегии выбора для алгоритма Бухбергера.
Вход:
список критических пар
Выход: список критических пар
return ![{\displaystyle P_{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31cee957b3cb231d64331beb1d8d398eab758c0b)
Назовём эту стратегию нормальной стратегией для
.
Следовательно, если входные полиномы однородны, мы получаем в степени, и d - базис Гребнера.
На следующем шаге мы выбираем все критические пары, необходимые для вычисления базиса Гребнера в степени d+1.
Существует несколько путей оптимизации алгоритма:
- включение критерия Бухбергера (или критерия F5);
- повторное использование всех строк в приведённых матрицах.
Критерии Бухбергера Алгоритм - реализация:
Вход:
Выход: конечное подмножество в
обновлённый список критических пар
Вход:
Выход: конечное подмножество
.
while
do
while
do
for
return ![{\displaystyle G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
Пусть есть некоторое конечное множество многочленов
. По этому множеству строится большая разреженная матрица, строки которой соответствуют многочленам из
, а столбцы — мономам. В матрице записаны коэффициенты многочленов при соответствующих мономах. Столбцы матрицы отсортированы согласно выбранному мономиальному упорядочению (старший моном соответствует первому столбцу). Приведение такой матрицы к ступенчатому виду позволяет узнать базис линейной оболочки многочленов из
в пространстве многочленов.
Пусть в классическом алгоритме Бухбергера требуется провести шаг редукции многочлена
относительно
, и при этом
должен быть домножен на моном
. В алгоритме F4 в матрицу будут специально помещены
и ![{\displaystyle M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
. Утверждается, что можно заранее подготовить множество всех потенциальных домноженных редукторов, которые могут потребоваться, и поместить их заранее в матрицу.[2]
Обобщим алгоритм F4[3]:
пусть нам требуется отредуцировать многочлен
относительно множества
. Для этого мы
(1) добавляем
в матрицу;
(2) строим носитель
многочлена
(множество мономов);
(3) если
пусто, то заканчиваем процедуру;
(4) выбираем максимальный моном
в
(и выкидываем его из
);
(5) если
не делится ни на один старший моном элементов
, то переходим к шагу (3);
(6) иначе выбираем редуктор
∈
(и дополнительный множитель
): тогда ![{\displaystyle M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
;
(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)
Матричное представление полученного
:
Редукция Гаусса полученной матрицы
:
По этой матрице получаем:
А так как
, то
и тогда
Для следующего шага мы должны рассмотреть
Отсюда
В Символьном препроцессинге можно попытаться упростить
используя предыдущие вычисления:
Например,
1) Символьный препроцессинг
2) Символьный препроцессинг
3) Символьный препроцессинг
![{\displaystyle F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed0c7292385e02472846913d81fa2a30820cd5bf)
Цель: заменить любое произведение
на произведение
, где
- ранее вычисленная строка, а
делит моном
В первом варианте алгоритма: некоторые строки матрицы никогда не используются (строки в матрице
).
Новая версия алгоритма: мы сохраняем эти строки
SIMPLIFY пытается заменить произведение
произведением
, где
уже вычисленная строка в гауссовой редукции, и u t делит моном m; Если мы нашли такое лучшее произведение, то рекурсивно вызываем функцию SIMPLIFY:
Вход:
Выход: Результат
эквивалентно
for
do
if
if
return
else return
return ![{\displaystyle t*f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df1a4228e326445ea49d27683019b70e26b25e43)
Algorithm SYMBOLICPREPROCESSING
Вход:
Выход: конечное подмножество
.
while
do
if
приводим сверху по модулю
then
существует
return ![{\displaystyle F}](https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57)
Теперь возвращаемся к примеру.
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.]