F4 (алгоритм)

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

АлгоритмПравить

ОпределенияПравить

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

$T\cdot <!--\; \cdot \; -->T\cdot <!--\; \cdot \; -->K[x_1,...,x_n]\cdot <!--\; \cdot \; -->T\cdot <!--\; \cdot \; -->K[x_1,...,x_n],Pair(f_i,f_j):=(HO{K}_{ij},t_i,f_i,t_j,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))=HO{K}_{ij}=LT(t_i{f}_i)=LT(t_j{f}_j)=HOK(f_i,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})$$p_{i,j}=Pair(f_{i},f_{j}),deg(p_{i,j})$  как $deg(HO{K}_{i,j})$$deg(HOK_{i,j})$ .

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

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

Вход: $\{\begin{array}{l}F\text{ конечное подмножество }K[X_1,...,X_n]\\ Sel\text{ функция }List(Pairs)\to <!--\; \to \; -->List(Pairs)\\ \text{такое, что }Sel(I)\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}\text{ если }I\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}\end{array}$${\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]$$K[X_{1},...,X_{n}]$ 

$G:=F,{\stackrel{~<!--\; ~\; -->}{F}}_0+:=F:=0\text{ и }P:=\{Pair(f,g)|(f,g)\in <!--\; \in \; -->G^2\text{ c }f\ne <!--\; \ne \; -->g\}$$G:=F,{\tilde {F}}_{0}+:=F:=0{\text{ и }}P:=\{Pair(f,g)|(f,g)\in G^{2}{\text{ c }}f\neq g\}$ 

While $P\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}$$P\neq \varnothing$  do

$d:=d+1$$d:=d+1$ 

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

$P:=P\mathrm{\setminus <!--\; \setminus \; -->}{P}_d$$P:=P\backslash P_{d}$ 

$L_d:=Left(P_d)\cup <!--\; \cup \; -->Right(P_d)$$L_{d}:=Left(P_{d})\cup Right(P_{d})$ 

${\stackrel{~<!--\; ~\; -->}{F}}_d^{+}:=Reduction(L_d,G)$${\tilde {F}}_{d}^{+}:=Reduction(L_{d},G)$ 

for $h\in <!--\; \in \; -->{\stackrel{~<!--\; ~\; -->}{F}}_d^{+}$$h\in {\tilde {F}}_{d}^{+}$  do

$P:=P\cup <!--\; \cup \; -->\{Pair(h,g)|g\in <!--\; \in \; -->G\}G:=G\cup <!--\; \cup \; -->\{h\}$$P:=P\cup \{Pair(h,g)|g\in G\}G:=G\cup \{h\}$ 

return $G$$G$ 

Алгоритм редукцииПравить

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

подмножества $K[X_1,...,X_n]$$K[X_{1},...,X_{n}]$ , до редукции подмножества $K[X_1,...,X_n]$$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}]$ 

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

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

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

${\stackrel{~<!--\; ~\; -->}{F}}^{+}:=\{f\in <!--\; \in \; -->\stackrel{~<!--\; ~\; -->}{F}|LT(f)\notin LT(F)\}$${\tilde {F}}^{+}:=\{f\in {\tilde {F}}|LT(f)\not \in LT(F)\}$ 

return $\stackrel{~<!--\; ~\; -->}{F^{+}}$${\tilde {F^{+}}}$ 

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

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

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

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

$F:=L$$F:=L$ 

$Done:=LT(F)$$Done:=LT(F)$ 

while $T(F)\ne <!--\; \ne \; -->Done$$T(F)\neq Done$  do

$m\in <!--\; \in \; -->T(F)\mathrm{\setminus <!--\; \setminus \; -->}Done$$m\in T(F)\backslash Done$ 

$Done:=Done\cup <!--\; \cup \; -->\{m\}$$Done:=Done\cup \{m\}$ 

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

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

$F:=F\cup <!--\; \cup \; -->\{m^{{}^{\prime }}\cdot <!--\; \cdot \; -->g\}$$F:=F\cup \{m^{'}\cdot g\}$ 

return $F$$F$ 

ЛеммаПравить

Для всех многочленов $p\in <!--\; \in \; -->L_d$$p\in L_{d}$ , мы имеем $p\underset{}{\overset{G\cup <!--\; \cup \; -->\stackrel{~<!--\; ~\; -->}{F}+}{\to }}0$$p{\xrightarrow[{}]{G\cup {\tilde {F}}+}}0$ 

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

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

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

Замечание

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

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

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

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

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

$P_d:=\{p\in <!--\; \in \; -->P|deg(lcm(p))=d\}$$P_{d}:=\{p\in P|deg(lcm(p))=d\}$ 

return $P_d$$P_d$ 

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

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

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

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

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

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

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

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

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

Вход: $\{\begin{array}{l}\text{конечное подмножество }{G}_{old}\text{ в }K[X_1,...,X_n]\\ \text{конечное подмножество }{P}_{old}\text{ критических пар в }K[X_1,...,X_n]\\ 0\ne <!--\; \ne \; -->h\in <!--\; \in \; -->K[x_1,...,X_n]\end{array}$${\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]$$K[X_{1},...,X_{n}]$  обновлённый список критических пар

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

Вход: $\{\begin{array}{l}F\subset <!--\; \subset \; -->K[X_1,...,X_n]\\ Sel\text{ функция }List(Pairs)\to <!--\; \to \; -->List(Pairs)\end{array}$${\begin{cases}F\subset K[X_{1},...,X_{n}]\\Sel{\text{ функция }}List(Pairs)\rightarrow List(Pairs)\end{cases}}$ 

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

$G:=\mathrm{\varnothing <!--\; \varnothing \; -->}\text{ И }P:=\mathrm{\varnothing <!--\; \varnothing \; -->}\text{ И }d:=0$$G:=\varnothing {\text{ И }}P:=\varnothing {\text{ И }}d:=0$ 

while $F\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}$$F\neq \varnothing$  do

$f:=first(F);F:F\mathrm{\setminus <!--\; \setminus \; -->}\{f\}$$f:=first(F);F:F\backslash \{f\}$ 

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

while $P\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}$$P\neq \varnothing$  do

$d:=d+1$$d:=d+1$ 

$P_d:=Sel(P);P:=P\mathrm{\setminus <!--\; \setminus \; -->}{P}_d$$P_{d}:=Sel(P);P:=P\backslash P_{d}$ 

$L_d:=Left(P_d)\cup <!--\; \cup \; -->Right(P_d)$$L_{d}:=Left(P_{d})\cup Right(P_{d})$ 

$({\stackrel{~<!--\; ~\; -->}{F}}_d^{+},F_d):=Reduction(L_d,G,(F_i{)}_{d=1,...,(d-<!--\; -\; -->1)})$$({\tilde {F}}_{d}^{+},F_{d}):=Reduction(L_{d},G,(F_{i})_{d=1,...,(d-1)})$ 

for $P\ne <!--\; \ne \; -->{\stackrel{~<!--\; ~\; -->}{F}}_d^{+}$$P\neq {\tilde {F}}_{d}^{+}$ 

$P:=P\cup <!--\; \cup \; -->\{Pair(h,g)|g\in <!--\; \in \; -->G\}$$P:=P\cup \{Pair(h,g)|g\in G\}$ 

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

return $G$$G$ 

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

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

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

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

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

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

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

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

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

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

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

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

(8) добавляем мономы многочлена $tr$$tr$  (кроме старшего $M$$M$ ) ко множеству $\mathcal{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\}$$\{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,$$G={f_{4}},$  $P_1=Pair(f_3,f_4),$$P_{1}={Pair(f_{3},f_{4})},$  $L_1=\{(1,f_3),(b,f_4)\}$$L_{1}=\{(1,f_{3}),(b,f_{4})\}$ 

1) Символьный препроцессинг$(L_1,G,\mathrm{\varnothing <!--\; \varnothing \; -->}):$$(L_{1},G,\varnothing ):$ 

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

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

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

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

$ad$$ad$  сверху сводится к $f_4\in <!--\; \in \; -->G$$f_{4}\in G$ .

3) Символьный препроцессинг$(L_1,G,\mathrm{\varnothing <!--\; \varnothing \; -->}):$$(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\}$$F_{1}=\{{f_{3},bf_{4},df_{4}}\},T(F_{1})=\{ab,ad,b^{2},bc,bd,cd,d^{2}\}$ 

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

4) $F_1=\{f_3,b{f}_4,d{f}_4\}.$$F_{1}=\{{f_{3},bf_{4},df_{4}}\}.$ 

Матричное представление полученного $F_1$$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$$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}}$ 

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

$\stackrel{~<!--\; ~\; -->}{F_1}=[f_5=ad+bd+cd+d^2,f_6=ab+bc-<!--\; -\; -->bd-<!--\; -\; -->d^2,f_7=b^2+2bd+d^2]$${\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 <!--\; \in \; -->LT(F_1)$$ab,ad\in LT(F_{1})$ , то

$\stackrel{~<!--\; ~\; -->}{F_{1+}}=[f_7]$${\tilde {F_{1+}}}=[f_{7}]$  и тогда $G=\{f_4,f_7\}.$$G=\{f_{4},f_{7}\}.$ 

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

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

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

Например,$LT(bc{f}_4)=abc=LT(c{f}_6)\text{ и поэтому вместо }bc\cdot <!--\; \cdot \; -->f_4\text{ можно использовать }c\cdot <!--\; \cdot \; -->f_6$$LT(bcf_{4})=abc=LT(cf_{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\}$$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2}\}$ 

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

$F_2=\{f_2,c{f}_6\},T(F_2)=\{abc,b{c}^2,abd,acd,bcd,c{d}^2\}$$F_{2}=\{{f_{2},cf_{6}}\},T(F_{2})=\{abc,bc^{2},abd,acd,bcd,cd^{2}\}$ 

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

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

Опишем упрощениеПравить

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

В первом варианте алгоритма: некоторые строки матрицы никогда не используются (строки в матрице ${\stackrel{~<!--\; ~\; -->}{F}}_d\mathrm{\setminus <!--\; \setminus \; -->}{\stackrel{~<!--\; ~\; -->}{F}}_d^{+}$${\tilde {F}}_{d}\backslash {\tilde {F}}_{d}^{+}$ ).

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

$m\cdot <!--\; \cdot \; -->f\in <!--\; \in \; -->Rows(F)\to <!--\; \to \; -->m^{{}^{\prime }}\cdot <!--\; \cdot \; -->f^{{}^{\prime }}\text{ c }m\ge <!--\; \ge \; -->m^{{}^{\prime }}$$m\cdot f\in Rows(F)\rightarrow m^{'}\cdot f^{'}{\text{ c }}m\geq m^{'}$ 

$m\cdot <!--\; \cdot \; -->f\in <!--\; \in \; -->Rows(F)\to <!--\; \to \; -->X_k\cdot <!--\; \cdot \; -->f^{{}^{\prime }}$$m\cdot f\in Rows(F)\rightarrow X_{k}\cdot f^{'}$ 

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

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

Вход: $\{\begin{array}{l}t\in <!--\; \in \; -->T\text{ моном}\\ t\in <!--\; \in \; -->K[X_1,...,X_n]\text{ многочлен}\\ F=(F_i{)}_{d=1,...,(d-<!--\; -\; -->1)},\text{ Где }{F}_k\in <!--\; \in \; -->K[X_1,...,X_n]\end{array}$${\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^{{}^{\prime }}\ast <!--\; \ast \; -->f^{{}^{\prime }}$$m^{'}*f^{'}$  эквивалентно $t\ast <!--\; \ast \; -->f$$t*f$ 

for $u\in <!--\; \in \; -->\text{ список делителей }t$$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{ Относительно}}<$ 

$\mathrm{\exists <!--\; \exists \; -->}!p\in <!--\; \in \; -->{\stackrel{~<!--\; ~\; -->}{F}}_j:LT(p)=LT(u\ast <!--\; \ast \; -->f)$$\exists !p\in {\tilde {F}}_{j}:LT(p)=LT(u*f)$ 

if $u\ne <!--\; \ne \; -->t\text{ then}$$u\neq t{\text{ then}}$ 

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

else return $1\ast <!--\; \ast \; -->p$$1*p$ 

return $t\ast <!--\; \ast \; -->f$$t*f$ 

Algorithm SYMBOLICPREPROCESSING  

Вход: $\{\begin{array}{l}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}$${\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]$$K[X_{1},...,X_{n}]$ .

$F:=L$$F:=L$ 

$Done:=LT(F)$$Done:=LT(F)$ 

while $T(F)\ne <!--\; \ne \; -->Done$$T(F)\neq Done$  do

$m\in <!--\; \in \; -->T(F)\mathrm{\setminus <!--\; \setminus \; -->}Done$$m\in T(F)\backslash Done$ 

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

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

$F:=F\cup <!--\; \cup \; -->\{Simplify(m^{{}^{\prime }},g,F)\}$$F:=F\cup \{Simplify(m^{'},g,F)\}$ 

return $F$$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\}$$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=[c{f}_5,d{f}_7,b{f}_5,f_2,c{f}_6]$$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}}$ 

$\stackrel{~<!--\; ~\; -->}{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]$${\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}\}$$G=\{f_{4},f_{7},f_{13}\}$ 

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

$L_3=\{(1,f_1),(bcd,f_4),(c^2,f_7),(b,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})$$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})\}$$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}]$$F_{3}=[f_{1},df_{12},c^{2}f_{7},bf_{13},df_{13},df_{10}]$ 

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

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

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

$L_3=\{(1,f_1),(bcd,f_4),(c^2,f_7),(b,f_{13})\}$$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},df_{12},c^{2}f_{7},bf_{13}]$ 

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

$F_3=[f_1,d{f}_{12},c^2{f}_5,b{f}_{13},d{f}_{13},d{f}_{10}]$$F_{3}=[f_{1},df_{12},c^{2}f_{5},bf_{13},df_{13},df_{10}]$ 

$\stackrel{~<!--\; ~\; -->}{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]$${\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.]