F5 (алгоритм)

Алгоритм F5 вычисления базиса Грёбнера был предложен Ж.-Ш. Фожером в 2002 году. В данной работе рассмотрим его матричную версию, работающую для однородных многочленов. Основная процедура этого алгоритма вычисляет d-базис Грёбнера, то есть, подмножество базиса Грёбнера, относительно которого редуцируются к нулю все многочлены из идеала степени не выше, чем d.

В алгоритме F5 каждому полученному многочлену сопоставляется сигнатура (пара из монома и номера образующей), кодирующая информацию о происхождении этого многочлена. Основная идея - не включать по возможности в матрицы те строки, которые заведомо будут линейно зависимы с остальными (то есть, будут редуцироваться к нулю.)

Для этого редукции ограничиваются такими, которые не изменяют сигнатуру элементов, а также среди очередных обрабатываемых многочленов рассматриваются лишь те, моном сигнатуры которых не делится ни на один старший моном уже найденных элементов базиса.

Псевдокод матричного алгоритма F5

Вход: однородные многочлены $f_1,\dots ,f_m$ со степенями $d_1⩽\dots ⩽d_m;$ максимальная степень $D$.

Выход: элементы степени не выше $D$ приведенного базиса Грёбнера из $f_1,\dots ,f_i$ для $i=\overline{1,m}$.

Алгоритм:

for i from 1 to n do Gᵢ := 0; end for // initialise the Gröbner Bases Gᵢ of (f, …, fᵢ).
for d₁ from d to D do
    ℳ_{d,0} := 0, ℳ̅_{d,0} := 0
    for i from 1 to m do
        if d < dᵢ then ℳ_{d,i} := ℳ_{d,i-1}
        else if d = dᵢ then
           ℳ_{d,i} := add the new row fᵢ to ℳ̅_{dᵢ,i-1} with index (i,1)
        else
           ℳ_{d,i} := ℳ̅_{d,i-1}
           Crit := LT(ℳ̅_{d-dᵢ,i-1})
           for f in Rows(ℳ_{d-1,i}) \ Rows(ℳ_{d-1,i-1}) do
               (i,u) := index(f), with u = x_{j₁}, …, x_{jd-dᵢ-1},
                                  and 1 ≤ j₁ ≤ … ≤ j_{d-dᵢ-1} ≤ n
               for j from j_{d-dᵢ-1} to n do
                   if uxⱼ ∉ Crit then
                       add the new row xⱼf with index (i,uxⱼ) in ℳ_{d,i}
                   end if
               end for
           end for
        end if
        Compute ℳ̅_{d,i} by Gaussian elimination from ℳ_{d,i}
        Add to Gᵢ all rows of ℳ̅_{d,i} not reducible by LT(Gᵢ)
    end for
end for
return [Gᵢ|i = 1, …, m]

Цикл for в строке 14 строит матрицу $M_{d,i}$, содержащую все многочлены $x_1^{{\alpha }_1}\dots x_n^{{\alpha }_n}{f}_i$ с ${\alpha }_1+\dots +{\alpha }_n=d-d_i$ (кроме тех, которые тривиально сводятся к нулю). Чтобы избежать избыточных вычислений, они строятся из строк предыдущей матрицы $M_{d-1,i}$, то есть все строки умножаются на все переменные. Строка с индексом $(i,x_1^{{\alpha }_1}\dots x_j^{{\alpha }_j})$ с ${\alpha }_j\ne 0$ может возникать из нескольких строк в $M_{d-1,i}$, мы можем построить его из строки, проиндексированной $(i,u)$ в $M_{d-1,i}$, с $u=x_1^{{\alpha }_1}\dots x_j^{{\alpha }_{j-1}}$, и умножить ее на $x_j$, наибольшую переменную, встречающуюся в $u$. Это гарантирует, что каждая строка берется ровно из одной строки предыдущей матрицы.

Пример работы алгоритма F5

Рассмотрим однородную систему в ${𝔽}_{23}[x,y,z]$ с градуированным обратным лексографическим порядком $(x\succ y\succ z)$ по матричному алгоритму $F5$.

$\{\begin{array}{c}{f}_3=x^2+18xy+19y^2+8xz+5yz+7z^2\\ f_2=3x^2+7xy+22xz+11yz+22z^2+8y^2\\ f_1=6x^2+12xy+4y^2+14xz+9yz+7z^2\end{array}$

Чтобы вычислить базис Грёбнера $f_1,f_2,f_3$ мы задаем $F_1=(e_1,f_1)$, $F_2=(e_2,f_2)$ и $F_3=(e_3,f_3)$ и рассматриваем критические пары $[F_1,F_2]=(1,f_1,1,f_2),[F_1,F_3]=(1,f_1,1,f_3)$ и $[F_2,F_3]=(1,f_2,1,f_3)$. Как и в алгоритме ${𝔽}_4$ мы используем часть $1x{f}_1,1x{f}_2,1x{f}_3$ для построения матрицы степени 2, чтобы свести эти три критические пары вместе:

$\begin{array}{cc}\begin{array}{c}\\ A_2=\begin{array}{c}{f}_3\\ f_2\\ f_1\end{array}\end{array}& \begin{array}{c}\\ (\begin{array}{c}\\ \\ \\ \end{array}\end{array}\begin{array}{cccccc}{x}^2& xy& y^2& xz& yz& z^2\\ 1& 18& 19& 8& 5& 7\\ 3& 7& 8& 22& 11& 22\\ 6& 12& 4& 14& 9& 7\end{array}\begin{array}{c}\\ \begin{array}{c}\\ \\ \\ \end{array})\end{array}\end{array}$

и после приведения матрицы $A_2$ к треугольному виду:

$\begin{array}{cc}\begin{array}{c}\\ B_2=\begin{array}{c}{f}_3\\ \underset{\_}{f_2}\\ f_1\end{array}\end{array}& \begin{array}{c}\\ (\begin{array}{c}\\ \\ \\ \end{array}\end{array}\begin{array}{cccccc}{x}^2& xy& y^2& xz& yz& z^2\\ 1& \underset{\_}{18}& 19& 8& 5& 7\\ 0& 1& 3& 2& 4& -1\\ 0& \underset{\_}{0}& 1& -11& -3& -5\end{array}\begin{array}{c}\\ \begin{array}{c}\\ \\ \\ \end{array})\end{array}\end{array}$

и появляются два "новых" многочлена: $f_4=xy+4yz+2xz+3y^2-z^2(F_4=(e_2,f_4))$ и $f_5=y_2-11xz-3yz-5z^2(F_5=(e_3,f_5))$, которые являются результатом понижения критических пар $[F_1,F_2],[F_1,F_3]$ и $[F_2,F_3]$. Обратите внимание, что сигнатура полинома $f_4$ равна $e_2$, что соответствует метке слева от этой строки (подчеркнуто $f_2$ в матрице $B_2$).

Также отметим, что подчеркнутая цифра 18 не уменьшается на $f_4$, так как подпись $f_3$ равна $e_3$, которая меньше $e_2$. В то время как подчеркнутый 0 уменьшается, так как $e_1\succ e_2$. Это доказывает, что редукция в алгоритме ${𝔽}_5$ является односторонней редукцией.

Следующим шагом является рассмотрение новых критических пар: $[F_1,F_4]=(y,f_1,x,f_4),[F_4,F_2]=(x,f_4,y,f_2),[F_4,F_3]=(x,f_4,y,f_3),[F_5,F_4]=(x,f_5,y,f_4),[F_5,F_1]=(x^2,f_5,y^2,f_1),[F_5,F_2]=(x^2,f_5,y^2,f_2)$ и $[F_5,F_3]=(x^2,f_5,y^2,f_3)$. Мы выбираем пары по степени и строим матрицу $A_3$ степени 3 для работы со следующими критическими парами $[F_1,F_4]=(y,f_1,x,f_4),[F_4,F_2]=(x,f_4,y,f_2),[F_4,F_3]=(x,f_4,y,f_3),[F_5,F_4]=(x,f_5,y,f_4)$ вместе. Нам нужно только рассмотреть части $y{f}_3,y{f}_4,x{f}_4,x{f}_5$, c частями $y{f}_2,y{f}_1$, которые являются перезаписываемыми $F_4$ и $F_5$ соответственно.

Как и алгоритм ${𝔽}_5$, части $y{f}_3,y{f}_4,x{f}_4,x{f}_5$ - это те строки, которые должны быть уменьшены в Матрице, и нам также нужно выбрать части, которые используются для уменьшения этих строк. Так как $y^3,x^{2}z,xyz,y^{2}z$ являются частями $y{f}_3,y{f}_4,x{f}_4,x{f}_5$, мы должны добавить части $y{f}_5,x{f}_3,z{f}_4,z{f}_5$ в матрицу $A_3$, чтобы устранить их.

Теперь у нас есть матрица $A_3$ со степенью 3 (упорядоченная по сигнатуре):

$\begin{array}{cc}\begin{array}{c}\\ A_3=\begin{array}{c}z{f}_3(z{e}_3)\\ y{f}_3(y{e}_3)\\ z{f}_4(z{e}_2)\\ y{f}_4(y{e}_2)\\ x{f}_4(x{e}_2)\\ z{f}_5(z{e}_1)\\ y{f}_5(y{e}_1)\\ x{f}_5(x{e}_1)\end{array}\end{array}& \begin{array}{c}\\ (\begin{array}{c}\\ \\ \\ \\ \\ \\ \\ \\ \end{array}\end{array}\begin{array}{ccccccccc}{x}^{2}y& x{y}^2& y^3& x^{2}z& xyz& y^{2}z& x{z}^2& y{z}^2& z^3\\ 0& 0& 0& 1& 18& 19& 8& 5& 7\\ 1& 18& 19& 0& 8& 5& 0& 7& 0\\ 0& 0& 0& 0& 1& 3& 2& 4& 22\\ 0& 1& 3& 0& 2& 4& 0& 22& 0\\ 1& 3& 0& 2& 4& 0& 22& 0& 0\\ 0& 0& 0& 0& 0& 1& 12& 20& 18\\ 0& 0& 1& 0& 12& 20& 0& 18& 0\\ 0& 1& 0& 12& 20& 0& 18& 0& 0\end{array}\begin{array}{c}\\ \begin{array}{c}\\ \\ \\ \\ \\ \\ \\ \\ \end{array})\end{array}\end{array}$

и после приведения к треугольному виду:

$\begin{array}{cc}\begin{array}{c}\\ B_3=\begin{array}{c}y{f}_3(y{e}_3)\\ y{f}_4(y{e}_2)\\ \underset{\_}{x{f}_4}(x{e}_2)\\ z{f}_3(z{e}_3)\\ z{f}_4(z{e}_2)\\ z{f}_5(z{e}_1)\\ \underset{\_}{y{f}_5}(y{e}_1)\\ \underset{\_}{x{f}_5}(x{e}_1)\end{array}\end{array}& \begin{array}{c}\\ (\begin{array}{c}\\ \\ \\ \\ \\ \\ \\ \\ \end{array}\end{array}\begin{array}{ccccccccc}{x}^{2}y& x{y}^2& y^3& x^{2}z& xyz& y^{2}z& x{z}^2& y{z}^2& z^3\\ 1& 18& 19& 0& 8& 5& 0& 7& 0\\ 0& 1& 3& 0& 2& 4& 0& 22& 0\\ 0& 0& \mathrm{𝟏}& \underset{\_}{0}& \underset{\_}{0}& \underset{\_}{8}& \underset{\_}{1}& \underset{\_}{18}& 15\\ 0& 0& 0& 1& 18& 19& 8& 5& 7\\ 0& 0& 0& 0& 1& 3& 2& 4& 22\\ 0& 0& 0& 0& 0& 1& 12& 20& 18\\ 0& 0& 0& 0& 0& 0& \mathrm{𝟏}& 11& 13\\ 0& 0& 0& 0& 0& 0& 0& \mathrm{𝟏}& 18\end{array}\begin{array}{c}\\ \begin{array}{c}\\ \\ \\ \\ \\ \\ \\ \\ \end{array})\end{array}\end{array}$

и полином $f_6=y^3+8y^2+x{z}^2+18y{z}^2+15z^3(F_6=(x{e}_2,f_6)),f_7=x{z}^2+11y{z}^2+13z^2(F_3=(y{e}_1,f_7))$ и $f_8=y{z}^2+18z^3(F_8=(x{e}_1,f_8)$ являются результатами редукции критических пар со степенью 3. Обратите внимание, что хотя $lpp(f_6)=y^3=ylpp(f_5)$, помеченный полином $F_6$ не является ${𝔽}_5$ - приводимым к $F_5$ . Таким образом, $f_6$ все еще является "новым" многочленом.

Теперь смысл написанного критерия гораздо яснее. При построении матрицы $A_3$, мы перечислим сигнатуры каждой строки (полинома) в круглых скобках. Помеченные многочлены с одинаковыми сигнатурами будут появляться в одной и той же строке матрицы, поэтому достаточно иметь дело с последними результатами (вот почему мы думаем о порядке создания помеченных многочленов). Также одностороннее сокращение очевидно в матрице $B_3$. Давайте посмотрим на строку $x{f}_4(x{e}_2)$. Подчеркнутые 0, 0 уменьшаются на строчках $z{f}_3(z{e}_3)$ и $z{f}_4(z{e}_2)$ соответственно, а подчеркнутые 8,1,18 не исключены в строках $z{f}_5(z{e}_1),y{f}_5(y{e}_1)$ и $x{f}_5(x{e}_1)$. причина заключается в том, что редукция в алгоритме ${𝔽}_5$ это односторонняя редукция. Более конкретно, сигнатуры строк $z{f}_3(z{e}_3)$ и $z{f}_4(z{e}_2)$ это $z{e}_3$ и $z{e}_2$, которые оба меньше $x{e}_2$ строчки $x{f}_4(x{e}_2)$.

Таким образом, строки $z{f}_3(z{e}_3)$ и $z{f}_4(z{e}_2)$ способны уменьшить строку $x{f}_4(x{e}_2)$. Тем не менее, у нас есть $z{e}_1,y{e}_1,x{e}_1\succ x{e}_2$, так строки $z{f}_5(z{e}_1),y{f}_5(y{e}_1)$ и $x{f}_5(x{e}_1)$ не сократить строки $x{f}_4(x{e}_2)$. Заметим, что поскольку только строки $x{f}_4(x{e}_2),y{f}_5(y{e}_1)$ и $x{f}_5(x{e}_1)$ требуют сохранения, другие строки не полностью уменьшаются в матрице $B_3$.

Однако мы должны понимать, что, хотя два новых критерия алгоритма ${𝔽}_5$ могут отбросить почти все бесполезные вычисления, одностороннее сокращение приводит к более низкой эффективности устранения матрицы, чем алгоритм ${𝔽}_4$.

Литература

• J.-C. Faug`ere.A new efficient algorithm for computing Grobner bases without reduction to zero (F5).

• M. Bardet, J.-C. Faug`ere, B. Salvy.On the Complexity of the F5 Grobner basis Algorithm.

• C. Eder, J.-C. Faug`ere.A survey on signature-based Grobner basis computations.

• Stegers, T., 2005. Faug`ere’s F5 Algorithm Revisited. Thesis for the degree of Diplom-Mathematiker