F4 (алгоритм)

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

Алгоритм

Определения

• Критическая пара $(f_i,f_j)$ является членом

$T\cdot T\cdot K[x_1,...,x_n]\cdot T\cdot K[x_1,...,x_n],Pair(f_i,f_j):=(HO{K}_{ij},t_i,f_i,t_j,f_j)$

такое, что

$HOK(Pair(f_i,f_j))=HO{K}_{ij}=LT(t_i{f}_i)=LT(t_j{f}_j)=HOK(f_i,f_j)$

• Определим степень критической пары $p_{i,j}=Pair(f_i,f_j),deg(p_{i,j})$ как $deg(HO{K}_{i,j})$.

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

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

Вход:

$\{\begin{array}{c}F\text{ конечное подмножество }K[X_1,...,X_n]\\ Sel\text{ функция }List(Pairs)\to List(Pairs)\\ \text{такое, что }Sel(I)\ne \varnothing \text{ если }I\ne \varnothing \end{array}$

Выход: конечное подмножество $K[X_1,...,X_n]$

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

While $P\ne \varnothing$ do

$d:=d+1$

$P_d:=Sel(p)$

$P:=P\mathrm{\setminus }{P}_d$

$L_d:=Left(P_d)\cup Right(P_d)$

${\tilde{F}}_d^{+}:=Reduction(L_d,G)$

for $h\in {\tilde{F}}_d^{+}$ do

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

return

$G$

Алгоритм редукции

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

подмножества $K[X_1,...,X_n]$, до редукции подмножества $K[X_1,...,X_n]$ по

модулю другого подмножества

$K[X_1,...,X_n]$

:

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

$K[X_1,...,X_n]$

Выход: конечные подмножества $K[X_1,...,X_n]$ (Может быть пустым)

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

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

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

return

$\widetilde{F^{+}}$

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

Алгоритм Символьного Препроцессинга

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

$K[X_1,...,X_n]$

Выход: конечные подмножества $K[X_1,...,X_n]$

$F:=L$

$Done:=LT(F)$

while $T(F)\ne Done$ do

$m\in T(F)\mathrm{\setminus }Done$

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

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

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

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

return

$F$

Лемма

Для всех многочленов $p\in L_d$, мы имеем $p\underset{}{\overset{G\cup \tilde{F}+}{\to }}0$

Теорема (без доказательства)

Алгоритм $F_4$ вычисляет базис Гребнера G в $K[X_1,...,X_n]$

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

Замечание

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

Функция выбора

Вход:

$P$

список критических пар

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

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

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

return

$P_d$

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

$F_4$

.

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

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

Оптимизация алгоритма F4

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

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

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

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

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

Вход: $\{\begin{array}{c}\text{конечное подмножество }{G}_{old}\text{ в }K[X_1,...,X_n]\\ \text{конечное подмножество }{P}_{old}\text{ критических пар в }K[X_1,...,X_n]\\ 0\ne h\in K[x_1,...,X_n]\end{array}$

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

$K[X_1,...,X_n]$

обновлённый список критических пар

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

Вход:

$\{\begin{array}{c}F\subset K[X_1,...,X_n]\\ Sel\text{ функция }List(Pairs)\to List(Pairs)\end{array}$

Выход: конечное подмножество $K[X_1,...,X_n]$.

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

while $F\ne \varnothing$ do

$f:=first(F);F:F\mathrm{\setminus }\{f\}$

$(G,P):=Update(G,P,f)$

while $P\ne \varnothing$ do

$d:=d+1$

$P_d:=Sel(P);P:=P\mathrm{\setminus }{P}_d$

$L_d:=Left(P_d)\cup Right(P_d)$

$({\tilde{F}}_d^{+},F_d):=Reduction(L_d,G,(F_i{)}_{d=1,...,(d-1)})$

for $P\ne {\tilde{F}}_d^{+}$

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

$(G,P):=Update(G,P,h)$

return

$G$

F4 и его отличия от Алгоритма Бухбергера

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализации

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

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

Пример

Задача: посчитать базис Грёбнера для многочленов $\{f_1=abcd-1;f_2=abc+abd+acd+bcd;f_3=ab+bc+ad+cd;f_4=a+b+c+d\}$В начале присваиваем $G=f_4,$ $P_1=Pair(f_3,f_4),$ $L_1=\{(1,f_3),(b,f_4)\}$

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

$F_1=\{f_3,b{f}_4\},T(F_1)=\{ab,ad,b^2,bc,bd,cd\}$

$ab$ уже готов.

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

$F_1=\{f_3,b{f}_4\},T(F_1)=\{ab,ad,b^2,bc,bd,cd\}$

$ad$ сверху сводится к $f_4\in G$.

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

$F_1=\{f_3,b{f}_4,d{f}_4\},T(F_1)=\{ab,ad,b^2,bc,bd,cd,d^2\}$

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

4) $F_1=\{f_3,b{f}_4,d{f}_4\}.$

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

$A_1=M(F_1)=\left(\begin{array}{cccccccc}\{& ab& b^2& bc& ad& bd& cd& d^2\}\\ (d{f}_4)& 0& 0& 0& 1& 1& 1& 1\\ (f_3)& 1& 0& 1& 1& 0& 1& 0\\ (b{f}_4)& 1& 1& 1& 0& 1& 0& 0\end{array}\right)$

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

$\widetilde{A_1}=\left(\begin{array}{cccccccc}\{& ab& b^2& bc& ad& bd& cd& d^2\}\\ (d{f}_4)& 0& 0& 0& 1& 1& 1& 1\\ (f_3)& 1& 0& 1& 0& -1& 0& -1\\ (b{f}_4)& 0& 1& 0& 0& 2& 0& 1\end{array}\right)$

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

$\widetilde{F_1}=[f_5=ad+bd+cd+d^2,f_6=ab+bc-bd-d^2,f_7=b^2+2bd+d^2]$

А так как $ab,ad\in LT(F_1)$, то

$\widetilde{F_{1+}}=[f_7]$ и тогда $G=\{f_4,f_7\}.$

Для следующего шага мы должны рассмотреть $P_2=\{Pair(f_2,f_4)\}$

Отсюда $L_2=\{(1,f_2),(bc,f_4)\}\text{и}ℱ=\{F_1\}.$

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

Например,$LT(bc{f}_4)=abc=LT(c{f}_6)\text{ и поэтому вместо }bc\cdot f_4\text{ можно использовать }c\cdot f_6$1) Символьный препроцессинг

$F_2=\{f_2,c{f}_6\},T(F_2)=\{abc,b{c}^2,abd,acd,bcd,c{d}^2\}$

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

$F_2=\{f_2,c{f}_6\},T(F_2)=\{abc,b{c}^2,abd,acd,bcd,c{d}^2\}$

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

$F_2=\{f_2,c{f}_6\},T(F_2)=\{abc,b{c}^2,abd,acd,bcd,c{d}^2\}$$abd\text{ сводится к }bc{f}_4\text{ а также к }b{f}_5$

Опишем упрощение

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

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

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

$m\cdot f\in Rows(F)\to m^{\text{'}}\cdot f^{\text{'}}\text{ c }m\ge m^{\text{'}}$

$m\cdot f\in Rows(F)\to X_k\cdot f^{\text{'}}$

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

$(t,f^{\text{'}})$

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

Вход:

$\{\begin{array}{c}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{array}$

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

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

if $\mathrm{\exists }j(1\le j<d):(u\cdot f)\in F_j\text{ then}$

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

$\mathrm{\exists }!p\in {\tilde{F}}_j:LT(p)=LT(u*f)$

if $u\ne t\text{ then}$

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

else return $1*p$

return

$t*f$

Algorithm SYMBOLICPREPROCESSING

Вход:

$\{\begin{array}{c}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{array}$

Выход: конечное подмножество $K[X_1,...,X_n]$.

$F:=L$

$Done:=LT(F)$

while $T(F)\ne Done$ do

$m\in T(F)\mathrm{\setminus }Done$

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

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

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

return

$F$

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

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

$F_2=\{f_2,c{f}_6,b{f}_5\},T(F_2)=\{abc,b{c}^2,abd,acd,bcd,c{d}^2,b^{2}d,b{d}^2\}$

И так далее….

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

$F_2=[c{f}_5,d{f}_7,b{f}_5,f_2,c{f}_6]$

$A_2=M(F_2)=\left[\begin{array}{ccccccccccc}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{array}\right]$

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

$\widetilde{A_2}=\widetilde{M(F_2)}=\left[\begin{array}{cccccccccc}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{array}\right]$

$\widetilde{F_2}=\left[\begin{array}{c}{f}_9=acd+bcd+c^{2}d+c{d}^2,\\ f_{10}=b^{2}d+2b{d}^2+d^3,\\ f_{11}=abd+bcd-b{d}^2-d^3,\\ f_{12}=abc-bcd-c^{2}d+b{d}^2-c{d}^2+d^3,\\ f_{13}=b{c}^2+c^{2}d-b{d}^2-d^3\end{array}\right]$

и $G=\{f_4,f_7,f_{13}\}$

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

$L_3=\{(1,f_1),(bcd,f_4),(c^2,f_7),(b,f_{13})\}$

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

$Simplify(bcd,f_4)=Simplify(cd,f_6)=Simplify(d,f_{12})=(d,f_{12})$

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

$L_3=\{(1,f_1),(bcd,f_4),(c^2,f_7),(b,f_{13})\}$ и $F_3=[f_1,d{f}_{12},c^2{f}_7,b{f}_{13},d{f}_{13},d{f}_{10}]$

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

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

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

$L_3=\{(1,f_1),(bcd,f_4),(c^2,f_7),(b,f_{13})\}$ и $F_3=[f_1,d{f}_{12},c^2{f}_7,b{f}_{13}]$

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

$F_3=[f_1,d{f}_{12},c^2{f}_5,b{f}_{13},d{f}_{13},d{f}_{10}]$

$\widetilde{F_3}=\left[\begin{array}{c}{f}_{15}=c^2{b}^2-c^2{d}^2+2b{d}^3+2d^4,\\ f_{16}=abcd-1,\\ f_{17}=-bc{d}^2-c^2{d}^2-b{d}^3-d^4+1,\\ f_{18}=c^{2}bd+c^2{d}^2-b{d}^3-d^4,\\ f_{19}=b^2{d}^2+2b{d}^3+d^4\end{array}\right]$

Литература

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