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}):=(HOK_{ij},t_{i},f_{i},t_{j},f_{j})$

такое, что

$HOK(Pair(f_{i},f_{j}))=HOK_{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(HOK_{i,j})$.

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

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

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

Выход: конечное подмножество $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\neq g\}$

While $P\neq \varnothing$ do

$d:=d+1$

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

$P:=P\backslash 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)\not \in LT(F)\}$

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

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

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

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

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

$F:=L$

$Done:=LT(F)$

while $T(F)\neq Done$ do

$m\in T(F)\backslash Done$

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

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

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

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

return $F$

Лемма

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

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

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

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

Замечание

Если #$Sel(I)=1$ для всех $I\neq \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{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}}$

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

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

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

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

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

while $F\neq \varnothing$ do

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

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

while $P\neq \varnothing$ do

$d:=d+1$

$P_{d}:=Sel(P);P:=P\backslash 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\neq {\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) строим носитель ${\mathcal {M}}$ многочлена $f$ (множество мономов);

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

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

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

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

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

(8) добавляем мономы многочлена $tr$ (кроме старшего $M$) ко множеству ${\mathcal {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},bf_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd\}$

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

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

$F_{1}=\{{f_{3},bf_{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},bf_{4},df_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd,d^{2}\}$

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

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

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

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

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

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

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

${\tilde {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})$, то

${\tilde {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{и}}{\mathcal {F}}=\{F_{1}\}.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

else return $1*p$

return $t*f$

Algorithm SYMBOLICPREPROCESSING  

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

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

$F:=L$

$Done:=LT(F)$

while $T(F)\neq Done$ do

$m\in T(F)\backslash Done$

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

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

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

return $F$

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

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

$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) Символьный препроцессинг

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

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

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

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

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

и $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},df_{12},c^{2}f_{7},bf_{13},df_{13},df_{10}]$

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

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

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

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

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

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

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