F5 (алгоритм)

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

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

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

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

Вход: однородные многочлены $f_{1},\dots ,f_{m}$ со степенями $d_{1}\leqslant \dots \leqslant 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}\neq 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

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

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

Чтобы вычислить базис Грёбнера ${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})$. Как и в алгоритме $\mathbb {F} _{4}$ мы используем часть $1xf_{1},1xf_{2},1xf_{3}$ для построения матрицы степени 2, чтобы свести эти три критические пары вместе:

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

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

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

и появляются два "новых" многочлена: $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}$. Это доказывает, что редукция в алгоритме $\mathbb {F} _{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})$ вместе. Нам нужно только рассмотреть части $yf_{3},yf_{4},xf_{4},xf_{5}$, c частями $yf_{2},yf_{1}$, которые являются перезаписываемыми $F_{4}$ и $F_{5}$ соответственно.

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

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

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

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

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

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

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

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

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