F4 (алгоритм)

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

• Критическая пара ${\displaystyle (f_{i},f_{j})}$ является членом

${\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})}$

такое, что

${\displaystyle HOK(Pair(f_{i},f_{j}))=HOK_{ij}=LT(t_{i}f_{i})=LT(t_{j}f_{j})=HOK(f_{i},f_{j})}$

• Определим степень критической пары ${\displaystyle p_{i,j}=Pair(f_{i},f_{j}),deg(p_{i,j})}$ как ${\displaystyle deg(HOK_{i,j})}$.

• Определим следующие операторы: ${\displaystyle Left(p_{i,j}):=t_{i}\cdot f_{i}}$ and ${\displaystyle Right(p_{i,j}):=t_{j}\cdot f_{j}}$

Вход: ${\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}}}$

Выход: конечное подмножество ${\displaystyle K[X_{1},...,X_{n}]}$

${\displaystyle G:=F,{\tilde {F}}_{0}+:=F:=0{\text{ и }}P:=\{Pair(f,g)|(f,g)\in G^{2}{\text{ c }}f\neq g\}}$

While ${\displaystyle P\neq \varnothing }$ do

${\displaystyle d:=d+1}$

${\displaystyle P_{d}:=Sel(p)}$

${\displaystyle P:=P\backslash P_{d}}$

${\displaystyle L_{d}:=Left(P_{d})\cup Right(P_{d})}$

${\displaystyle {\tilde {F}}_{d}^{+}:=Reduction(L_{d},G)}$

for ${\displaystyle h\in {\tilde {F}}_{d}^{+}}$ do

${\displaystyle P:=P\cup \{Pair(h,g)|g\in G\}G:=G\cup \{h\}}$

return ${\displaystyle G}$

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

подмножества ${\displaystyle K[X_{1},...,X_{n}]}$, до редукции подмножества ${\displaystyle K[X_{1},...,X_{n}]}$ по

модулю другого подмножества ${\displaystyle K[X_{1},...,X_{n}]}$:

Вход: L, G конечные подмножества ${\displaystyle K[X_{1},...,X_{n}]}$

Выход: конечные подмножества ${\displaystyle K[X_{1},...,X_{n}]}$ (Может быть пустым)

${\displaystyle F:={\text{SymbolicPreprocessing}}(L,G)}$

${\displaystyle {\tilde {F}}:={\text{Редукция Гауса }}F{\text{ относительно}}<}$

${\displaystyle {\tilde {F}}^{+}:=\{f\in {\tilde {F}}|LT(f)\not \in LT(F)\}}$

return ${\displaystyle {\tilde {F^{+}}}}$

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

Вход: L, G конечные подмножества ${\displaystyle K[X_{1},...,X_{n}]}$

Выход: конечные подмножества ${\displaystyle K[X_{1},...,X_{n}]}$

${\displaystyle F:=L}$

${\displaystyle Done:=LT(F)}$

while ${\displaystyle T(F)\neq Done}$ do

${\displaystyle m\in T(F)\backslash Done}$

${\displaystyle Done:=Done\cup \{m\}}$

if ${\displaystyle m}$ приводим сверху по модулю ${\displaystyle G}$ then

существует ${\displaystyle g\in G{\text{ И }}m^{'}\in T:m=m^{'}\cdot LT(g)}$

${\displaystyle F:=F\cup \{m^{'}\cdot g\}}$

return ${\displaystyle F}$

Для всех многочленов ${\displaystyle p\in L_{d}}$, мы имеем ${\displaystyle p{\xrightarrow[{}]{G\cup {\tilde {F}}+}}0}$

Алгоритм ${\displaystyle F_{4}}$ вычисляет базис Гребнера G в ${\displaystyle K[X_{1},...,X_{n}]}$

такой что ${\displaystyle F\subseteq G{\text{ И }}Id(G)=Id(F).}$

Замечание

Если #${\displaystyle Sel(I)=1}$ для всех ${\displaystyle I\neq \varnothing }$, тогда алгоритм ${\displaystyle F_{4}}$ сводится к алгоритму Бухбергера. В этом случае функция Sel является эквивалентом стратегии выбора для алгоритма Бухбергера.

Вход: ${\displaystyle P}$ список критических пар

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

${\displaystyle d:=min\{deg(lcm(p))\}}$

${\displaystyle P_{d}:=\{p\in P|deg(lcm(p))=d\}}$

return ${\displaystyle P_{d}}$

Назовём эту стратегию нормальной стратегией для ${\displaystyle F_{4}}$.

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

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

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

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

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

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

${\displaystyle (G_{new},p_{new}):=Update(G_{old},P_{old},h)}$

Вход: ${\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}}}$

Выход: конечное подмножество в ${\displaystyle K[X_{1},...,X_{n}]}$ обновлённый список критических пар

Вход: ${\displaystyle {\begin{cases}F\subset K[X_{1},...,X_{n}]\\Sel{\text{ функция }}List(Pairs)\rightarrow List(Pairs)\end{cases}}}$

Выход: конечное подмножество ${\displaystyle K[X_{1},...,X_{n}]}$.

${\displaystyle G:=\varnothing {\text{ И }}P:=\varnothing {\text{ И }}d:=0}$

while ${\displaystyle F\neq \varnothing }$ do

${\displaystyle f:=first(F);F:F\backslash \{f\}}$

${\displaystyle (G,P):=Update(G,P,f)}$

while ${\displaystyle P\neq \varnothing }$ do

${\displaystyle d:=d+1}$

${\displaystyle P_{d}:=Sel(P);P:=P\backslash P_{d}}$

${\displaystyle L_{d}:=Left(P_{d})\cup Right(P_{d})}$

${\displaystyle ({\tilde {F}}_{d}^{+},F_{d}):=Reduction(L_{d},G,(F_{i})_{d=1,...,(d-1)})}$

for ${\displaystyle P\neq {\tilde {F}}_{d}^{+}}$

${\displaystyle P:=P\cup \{Pair(h,g)|g\in G\}}$

${\displaystyle (G,P):=Update(G,P,h)}$

return ${\displaystyle G}$

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

Пусть в классическом алгоритме Бухбергера требуется провести шаг редукции многочлена ${\displaystyle f}$ относительно ${\displaystyle g}$, и при этом ${\displaystyle g}$ должен быть домножен на моном ${\displaystyle M}$. В алгоритме F4 в матрицу будут специально помещены ${\displaystyle f}$ и ${\displaystyle M}$${\displaystyle g}$. Утверждается, что можно заранее подготовить множество всех потенциальных домноженных редукторов, которые могут потребоваться, и поместить их заранее в матрицу.^[2]

Обобщим алгоритм F4^[3]:

пусть нам требуется отредуцировать многочлен ${\displaystyle f}$ относительно множества ${\displaystyle F}$. Для этого мы

(1) добавляем ${\displaystyle f}$ в матрицу;

(2) строим носитель ${\displaystyle {\mathcal {M}}}$ многочлена ${\displaystyle f}$ (множество мономов);

(3) если ${\displaystyle {\mathcal {M}}}$ пусто, то заканчиваем процедуру;

(4) выбираем максимальный моном ${\displaystyle M}$ в ${\displaystyle {\mathcal {M}}}$ (и выкидываем его из ${\displaystyle {\mathcal {M}}}$);

(5) если ${\displaystyle M}$ не делится ни на один старший моном элементов ${\displaystyle F}$, то переходим к шагу (3);

(6) иначе выбираем редуктор ${\displaystyle r}$ ∈ ${\displaystyle F}$ (и дополнительный множитель ${\displaystyle t}$): тогда ${\displaystyle M}$${\displaystyle =LM}$ ${\displaystyle tr}$;

(7) добавляем ${\displaystyle tr}$ в матрицу;

(8) добавляем мономы многочлена ${\displaystyle tr}$ (кроме старшего ${\displaystyle M}$) ко множеству ${\displaystyle {\mathcal {M}}}$;

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

Задача: посчитать базис Грёбнера для многочленов ${\displaystyle \{f_{1}=abcd-1;f_{2}=abc+abd+acd+bcd;f_{3}=ab+bc+ad+cd;f_{4}=a+b+c+d\}}$В начале присваиваем ${\displaystyle G={f_{4}},}$ ${\displaystyle P_{1}={Pair(f_{3},f_{4})},}$ ${\displaystyle L_{1}=\{(1,f_{3}),(b,f_{4})\}}$

1) Символьный препроцессинг${\displaystyle (L_{1},G,\varnothing ):}$

${\displaystyle F_{1}=\{{f_{3},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\}}$

${\displaystyle ab}$ уже готов.

2) Символьный препроцессинг${\displaystyle (L_{1},G,\varnothing ):}$

${\displaystyle F_{1}=\{{f_{3},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\}}$

${\displaystyle ad}$ сверху сводится к ${\displaystyle f_{4}\in G}$.

3) Символьный препроцессинг${\displaystyle (L_{1},G,\varnothing ):}$

${\displaystyle F_{1}=\{{f_{3},bf_{4},df_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd,d^{2}\}}$

${\displaystyle b^{2}}$ не сводится к ${\displaystyle G}$.

4) ${\displaystyle F_{1}=\{{f_{3},bf_{4},df_{4}}\}.}$

Матричное представление полученного ${\displaystyle F_{1}}$:

${\displaystyle A_{1}=M(F_{1})={\begin{pmatrix}\{&ab&b^{2}&bc&ad&bd&cd&d^{2}\}\\(df_{4})&0&0&0&1&1&1&1\\(f_{3})&1&0&1&1&0&1&0\\(bf_{4})&1&1&1&0&1&0&0\end{pmatrix}}}$

Редукция Гаусса полученной матрицы ${\displaystyle A_{1}}$:

${\displaystyle {\tilde {A_{1}}}={\begin{pmatrix}\{&ab&b^{2}&bc&ad&bd&cd&d^{2}\}\\(df_{4})&0&0&0&1&1&1&1\\(f_{3})&1&0&1&0&-1&0&-1\\(bf_{4})&0&1&0&0&2&0&1\end{pmatrix}}}$

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

${\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}]}$

А так как ${\displaystyle ab,ad\in LT(F_{1})}$, то

${\displaystyle {\tilde {F_{1+}}}=[f_{7}]}$ и тогда ${\displaystyle G=\{f_{4},f_{7}\}.}$

Для следующего шага мы должны рассмотреть ${\displaystyle P_{2}=\{Pair(f_{2},f_{4})\}}$

Отсюда ${\displaystyle L_{2}=\{(1,f_{2}),(bc,f_{4})\}{\text{и}}{\mathcal {F}}=\{F_{1}\}.}$

В Символьном препроцессинге можно попытаться упростить ${\displaystyle 1\cdot f_{2}{\text{и}}bc\cdot f_{4}}$ используя предыдущие вычисления:

Например,${\displaystyle LT(bcf_{4})=abc=LT(cf_{6}){\text{ и поэтому вместо }}bc\cdot f_{4}{\text{ можно использовать }}c\cdot f_{6}}$1) Символьный препроцессинг

${\displaystyle F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2}\}}$

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

${\displaystyle F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2}\}}$

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

${\displaystyle F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2}\}}$${\displaystyle abd{\text{ сводится к }}bcf_{4}{\text{ а также к }}bf_{5}}$

Цель: заменить любое произведение ${\displaystyle m\cdot f}$ на произведение ${\displaystyle (uf)\cdot f'}$, где ${\displaystyle (t,f')}$ - ранее вычисленная строка, а ${\displaystyle uf}$ делит моном ${\displaystyle m}$

В первом варианте алгоритма: некоторые строки матрицы никогда не используются (строки в матрице ${\displaystyle {\tilde {F}}_{d}\backslash {\tilde {F}}_{d}^{+}}$).

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

${\displaystyle m\cdot f\in Rows(F)\rightarrow m^{'}\cdot f^{'}{\text{ c }}m\geq m^{'}}$

${\displaystyle m\cdot f\in Rows(F)\rightarrow X_{k}\cdot f^{'}}$

SIMPLIFY пытается заменить произведение ${\displaystyle m\cdot f}$ произведением ${\displaystyle (ut)\cdot f^{'}}$, где

${\displaystyle (t,f^{'})}$уже вычисленная строка в гауссовой редукции, и 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}}}$

Выход: Результат ${\displaystyle m^{'}*f^{'}}$ эквивалентно ${\displaystyle t*f}$

for ${\displaystyle u\in {\text{ список делителей }}t}$ do

if ${\displaystyle \exists j(1\leq j<d):(u\cdot f)\in F_{j}{\text{ then}}}$

${\displaystyle {\tilde {F}}_{j}{\text{Гауссова редукция}}F_{j}{\text{ Относительно}}<}$

${\displaystyle \exists !p\in {\tilde {F}}_{j}:LT(p)=LT(u*f)}$

if ${\displaystyle u\neq t{\text{ then}}}$

return ${\displaystyle Simplify({\frac {t}{u}},p,F)}$

else return ${\displaystyle 1*p}$

return ${\displaystyle t*f}$

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}}}$

Выход: конечное подмножество ${\displaystyle K[X_{1},...,X_{n}]}$.

${\displaystyle F:=L}$

${\displaystyle Done:=LT(F)}$

while ${\displaystyle T(F)\neq Done}$ do

${\displaystyle m\in T(F)\backslash Done}$

if ${\displaystyle m}$ приводим сверху по модулю ${\displaystyle G}$ then

существует ${\displaystyle g\in G{\text{ И }}m^{'}\in T:m=m^{'}\cdot LT(g)}$

${\displaystyle F:=F\cup \{Simplify(m^{'},g,F)\}}$

return ${\displaystyle F}$

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

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

${\displaystyle F_{2}=\{{f_{2},cf_{6},bf_{5}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2},b^{2}d,bd^{2}\}}$

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

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

${\displaystyle F_{2}=[cf_{5},df_{7},bf_{5},f_{2},cf_{6}]}$

${\displaystyle A_{2}=M(F_{2})={\begin{bmatrix}0&0&0&0&1&1&1&0&1&0&0\\0&0&0&1&0&0&0&2&0&1&0\\0&0&1&1&0&1&0&1&0&0&0\\1&0&1&0&1&1&0&0&0&0&0\\1&1&0&0&0&-1&0&0&-1&0&0\end{bmatrix}}}$

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

${\displaystyle {\tilde {A_{2}}}={\tilde {M(F_{2})}}={\begin{bmatrix}0&0&0&0&1&1&1&0&1&0\\0&0&0&1&0&0&0&2&0&1\\0&0&1&0&0&1&0&-1&0&-1\\1&0&0&0&0&-1&-1&1&-1&1\\0&1&0&0&0&0&1&-1&0&-1\end{bmatrix}}}$

${\displaystyle {\tilde {F_{2}}}={\begin{bmatrix}f_{9}=acd+bcd+c^{2}d+cd^{2},\\f_{10}=b^{2}d+2bd^{2}+d^{3},\\f_{11}=abd+bcd-bd^{2}-d^{3},\\f_{12}=abc-bcd-c^{2}d+bd^{2}-cd^{2}+d^{3},\\f_{13}=bc^{2}+c^{2}d-bd^{2}-d^{3}\end{bmatrix}}}$

и ${\displaystyle G=\{f_{4},f_{7},f_{13}\}}$

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

${\displaystyle L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\}}$

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

${\displaystyle Simplify(bcd,f_{4})=Simplify(cd,f_{6})=Simplify(d,f_{12})=(d,f_{12})}$

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

${\displaystyle L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\}}$ и ${\displaystyle F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13},df_{13},df_{10}]}$

После некоторых вычислений, получается, что ранг ${\displaystyle M(F_{3})}$ составляет 5.

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

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

${\displaystyle L_{3}=\{(1,f_{1}),(bcd,f_{4}),(c^{2},f_{7}),(b,f_{13})\}}$ и ${\displaystyle F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13}]}$

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

${\displaystyle F_{3}=[f_{1},df_{12},c^{2}f_{5},bf_{13},df_{13},df_{10}]}$

${\displaystyle {\tilde {F_{3}}}={\begin{bmatrix}f_{15}=c^{2}b^{2}-c^{2}d^{2}+2bd^{3}+2d^{4},\\f_{16}=abcd-1,\\f_{17}=-bcd^{2}-c^{2}d^{2}-bd^{3}-d^{4}+1,\\f_{18}=c^{2}bd+c^{2}d^{2}-bd^{3}-d^{4},\\f_{19}=b^{2}d^{2}+2bd^{3}+d^{4}\end{bmatrix}}}$

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