F5 (алгоритм)

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

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

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

Вход: однородные многочлены ${\displaystyle f_{1},\dots ,f_{m}}$ со степенями ${\displaystyle d_{1}\leqslant \dots \leqslant d_{m};}$ максимальная степень ${\displaystyle D}$.

Выход: элементы степени не выше ${\displaystyle D}$ приведенного базиса Грёбнера из ${\displaystyle f_{1},\dots ,f_{i}}$ для ${\displaystyle 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 строит матрицу ${\displaystyle M_{d,i}}$, содержащую все многочлены ${\displaystyle x_{1}^{\alpha _{1}}\dots x_{n}^{\alpha _{n}}f_{i}}$ с ${\displaystyle \alpha _{1}+\dots +\alpha _{n}=d-d_{i}}$ (кроме тех, которые тривиально сводятся к нулю). Чтобы избежать избыточных вычислений, они строятся из строк предыдущей матрицы ${\displaystyle M_{d-1,i}}$, то есть все строки умножаются на все переменные. Строка с индексом ${\displaystyle (i,x_{1}^{\alpha _{1}}\dots x_{j}^{\alpha _{j}})}$ с ${\displaystyle \alpha _{j}\neq 0}$ может возникать из нескольких строк в ${\displaystyle M_{d-1,i}}$, мы можем построить его из строки, проиндексированной ${\displaystyle (i,u)}$ в ${\displaystyle M_{d-1,i}}$, с ${\displaystyle u=x_{1}^{\alpha _{1}}\dots x_{j}^{\alpha _{j-1}}}$, и умножить ее на ${\displaystyle x_{j}}$, наибольшую переменную, встречающуюся в ${\displaystyle u}$. Это гарантирует, что каждая строка берется ровно из одной строки предыдущей матрицы.

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

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

Чтобы вычислить базис Грёбнера ${\displaystyle {f_{1},f_{2},f_{3}}}$ мы задаем ${\displaystyle F_{1}=(e_{1},f_{1})}$, ${\displaystyle F_{2}=(e_{2},f_{2})}$ и ${\displaystyle F_{3}=(e_{3},f_{3})}$ и рассматриваем критические пары ${\displaystyle [F_{1},F_{2}]=(1,f_{1},1,f_{2}),[F_{1},F_{3}]=(1,f_{1},1,f_{3})}$ и ${\displaystyle [F_{2},F_{3}]=(1,f_{2},1,f_{3})}$. Как и в алгоритме ${\displaystyle \mathbb {F} _{4}}$ мы используем часть ${\displaystyle 1xf_{1},1xf_{2},1xf_{3}}$ для построения матрицы степени 2, чтобы свести эти три критические пары вместе:

${\displaystyle {\begin{array}{ll}{\begin{aligned}\\A_{2}={\begin{aligned}f_{3}\\f_{2}\\f_{1}\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\end{aligned}}\right.\end{aligned}}{\begin{matrix}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{matrix}}{\begin{aligned}\\\left.{\begin{aligned}\\\\\\\end{aligned}}\right)\end{aligned}}\end{array}}}$

и после приведения матрицы ${\displaystyle A_{2}}$ к треугольному виду:

${\displaystyle {\begin{array}{ll}{\begin{aligned}\\B_{2}={\begin{aligned}f_{3}\\{\underline {f_{2}}}\\f_{1}\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\end{aligned}}\right.\end{aligned}}{\begin{matrix}x^{2}&xy&y^{2}&xz&yz&z^{2}\\1&{\underline {18}}&19&8&5&7\\0&1&3&2&4&-1\\0&{\underline {0}}&1&-11&-3&-5\end{matrix}}{\begin{aligned}\\\left.{\begin{aligned}\\\\\\\end{aligned}}\right)\end{aligned}}\end{array}}}$

и появляются два "новых" многочлена: ${\displaystyle f_{4}=xy+4yz+2xz+3y^{2}-z^{2}\ (F_{4}=(e_{2},f_{4}))}$ и ${\displaystyle f_{5}=y_{2}-11xz-3yz-5z^{2}\ (F_{5}=(e_{3},f_{5}))}$, которые являются результатом понижения критических пар ${\displaystyle [F_{1},F_{2}],[F_{1},F_{3}]}$ и ${\displaystyle [F_{2},F_{3}]}$. Обратите внимание, что сигнатура полинома ${\displaystyle f_{4}}$ равна ${\displaystyle e_{2}}$, что соответствует метке слева от этой строки (подчеркнуто ${\displaystyle f_{2}}$ в матрице ${\displaystyle B_{2}}$).

Также отметим, что подчеркнутая цифра 18 не уменьшается на ${\displaystyle f_{4}}$, так как подпись ${\displaystyle f_{3}}$ равна ${\displaystyle e_{3}}$, которая меньше ${\displaystyle e_{2}}$. В то время как подчеркнутый 0 уменьшается, так как ${\displaystyle e_{1}\succ e_{2}}$. Это доказывает, что редукция в алгоритме ${\displaystyle \mathbb {F} _{5}}$ является односторонней редукцией.

Следующим шагом является рассмотрение новых критических пар: ${\displaystyle [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})}$ и ${\displaystyle [F_{5},F_{3}]=(x^{2},f_{5},y^{2},f_{3})}$. Мы выбираем пары по степени и строим матрицу ${\displaystyle A_{3}}$ степени 3 для работы со следующими критическими парами ${\displaystyle [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})}$ вместе. Нам нужно только рассмотреть части ${\displaystyle yf_{3},yf_{4},xf_{4},xf_{5}}$, c частями ${\displaystyle yf_{2},yf_{1}}$, которые являются перезаписываемыми ${\displaystyle F_{4}}$ и ${\displaystyle F_{5}}$ соответственно.

Как и алгоритм ${\displaystyle \mathbb {F} _{5}}$, части ${\displaystyle yf_{3},yf_{4},xf_{4},xf_{5}}$ - это те строки, которые должны быть уменьшены в Матрице, и нам также нужно выбрать части, которые используются для уменьшения этих строк. Так как ${\displaystyle y^{3},x^{2}z,xyz,y^{2}z}$ являются частями ${\displaystyle yf_{3},yf_{4},xf_{4},xf_{5}}$, мы должны добавить части ${\displaystyle yf_{5},xf_{3},zf_{4},zf_{5}}$ в матрицу ${\displaystyle A_{3}}$, чтобы устранить их.

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

${\displaystyle {\begin{array}{ll}{\begin{aligned}\\A_{3}={\begin{aligned}zf_{3}(ze_{3})\\yf_{3}(ye_{3})\\zf_{4}(ze_{2})\\yf_{4}(ye_{2})\\xf_{4}(xe_{2})\\zf_{5}(ze_{1})\\yf_{5}(ye_{1})\\xf_{5}(xe_{1})\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\\\\\\\\\\\end{aligned}}\right.\end{aligned}}{\begin{matrix}x^{2}y&xy^{2}&y^{3}&x^{2}z&xyz&y^{2}z&xz^{2}&yz^{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{matrix}}{\begin{aligned}\\\left.{\begin{aligned}\\\\\\\\\\\\\\\\\end{aligned}}\right)\end{aligned}}\end{array}}}$

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

${\displaystyle {\begin{array}{ll}{\begin{aligned}\\B_{3}={\begin{aligned}yf_{3}(ye_{3})\\yf_{4}(ye_{2})\\{\underline {xf_{4}}}(xe_{2})\\zf_{3}(ze_{3})\\zf_{4}(ze_{2})\\zf_{5}(ze_{1})\\{\underline {yf_{5}}}(ye_{1})\\{\underline {xf_{5}}}(xe_{1})\end{aligned}}\end{aligned}}&{\begin{aligned}\\\left({\begin{aligned}\\\\\\\\\\\\\\\\\end{aligned}}\right.\end{aligned}}{\begin{matrix}x^{2}y&xy^{2}&y^{3}&x^{2}z&xyz&y^{2}z&xz^{2}&yz^{2}&z^{3}\\1&18&19&0&8&5&0&7&0\\0&1&3&0&2&4&0&22&0\\0&0&\mathbf {1} &{\underline {0}}&{\underline {0}}&{\underline {8}}&{\underline {1}}&{\underline {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&\mathbf {1} &11&13\\0&0&0&0&0&0&0&\mathbf {1} &18\end{matrix}}{\begin{aligned}\\\left.{\begin{aligned}\\\\\\\\\\\\\\\\\end{aligned}}\right)\end{aligned}}\end{array}}}$

и полином ${\displaystyle f_{6}=y^{3}+8y^{2}+xz^{2}+18yz^{2}+15z^{3}(F_{6}=(xe_{2},f_{6})),f_{7}=xz^{2}+11yz^{2}+13z^{2}(F_{3}=(ye_{1},f_{7}))}$ и ${\displaystyle f_{8}=yz^{2}+18z^{3}(F_{8}=(xe_{1},f_{8})}$ являются результатами редукции критических пар со степенью 3. Обратите внимание, что хотя ${\displaystyle lpp(f_{6})=y^{3}=ylpp(f_{5})}$, помеченный полином ${\displaystyle F_{6}}$ не является ${\displaystyle \mathbb {F} _{5}}$ - приводимым к ${\displaystyle F_{5}}$ . Таким образом, ${\displaystyle f_{6}}$ все еще является "новым" многочленом.

Теперь смысл написанного критерия гораздо яснее. При построении матрицы ${\displaystyle A_{3}}$, мы перечислим сигнатуры каждой строки (полинома) в круглых скобках. Помеченные многочлены с одинаковыми сигнатурами будут появляться в одной и той же строке матрицы, поэтому достаточно иметь дело с последними результатами (вот почему мы думаем о порядке создания помеченных многочленов). Также одностороннее сокращение очевидно в матрице ${\displaystyle B_{3}}$. Давайте посмотрим на строку ${\displaystyle xf_{4}(xe_{2})}$. Подчеркнутые 0, 0 уменьшаются на строчках ${\displaystyle zf_{3}(ze_{3})}$ и ${\displaystyle zf_{4}(ze_{2})}$ соответственно, а подчеркнутые 8,1,18 не исключены в строках ${\displaystyle zf_{5}(ze_{1}),yf_{5}(ye_{1})}$ и ${\displaystyle xf_{5}(xe_{1})}$. причина заключается в том, что редукция в алгоритме ${\displaystyle \mathbb {F} _{5}}$ это односторонняя редукция. Более конкретно, сигнатуры строк ${\displaystyle zf_{3}(ze_{3})}$ и ${\displaystyle zf_{4}(ze_{2})}$ это ${\displaystyle ze_{3}}$ и ${\displaystyle ze_{2}}$, которые оба меньше ${\displaystyle xe_{2}}$ строчки ${\displaystyle xf_{4}(xe_{2})}$.

Таким образом, строки ${\displaystyle zf_{3}(ze_{3})}$ и ${\displaystyle zf_{4}(ze_{2})}$ способны уменьшить строку ${\displaystyle xf_{4}(xe_{2})}$. Тем не менее, у нас есть ${\displaystyle ze_{1},ye_{1},xe_{1}\succ xe_{2}}$, так строки ${\displaystyle zf_{5}(ze_{1}),yf_{5}(ye_{1})}$ и ${\displaystyle xf_{5}(xe_{1})}$ не сократить строки ${\displaystyle xf_{4}(xe_{2})}$. Заметим, что поскольку только строки ${\displaystyle xf_{4}(xe_{2}),yf_{5}(ye_{1})}$ и ${\displaystyle xf_{5}(xe_{1})}$ требуют сохранения, другие строки не полностью уменьшаются в матрице ${\displaystyle B_{3}}$.

Однако мы должны понимать, что, хотя два новых критерия алгоритма ${\displaystyle \mathbb {F} _{5}}$ могут отбросить почти все бесполезные вычисления, одностороннее сокращение приводит к более низкой эффективности устранения матрицы, чем алгоритм ${\displaystyle \mathbb {F} _{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