Русская Википедия:F5 (алгоритм)
Алгоритм F5 вычисления базиса Грёбнера был предложен Ж.-Ш. Фожером в 2002 году. В данной работе рассмотрим его матричную версию, работающую для однородных многочленов. Основная процедура этого алгоритма вычисляет d-базис Грёбнера, то есть, подмножество базиса Грёбнера, относительно которого редуцируются к нулю все многочлены из идеала степени не выше, чем d.
В алгоритме F5 каждому полученному многочлену сопоставляется сигнатура (пара из монома и номера образующей), кодирующая информацию о происхождении этого многочлена. Основная идея - не включать по возможности в матрицы те строки, которые заведомо будут линейно зависимы с остальными (то есть, будут редуцироваться к нулю.)
Для этого редукции ограничиваются такими, которые не изменяют сигнатуру элементов, а также среди очередных обрабатываемых многочленов рассматриваются лишь те, моном сигнатуры которых не делится ни на один старший моном уже найденных элементов базиса.
Псевдокод матричного алгоритма F5
Вход: однородные многочлены <math>f_{1}, \dots ,f_{m} </math> со степенями <math>d_{1} \leqslant \dots \leqslant d_{m};</math> максимальная степень <math>D</math>.
Выход: элементы степени не выше <math>D </math> приведенного базиса Грёбнера из <math>f_{1}, \dots ,f_{i} </math> для <math>i = \overline{1,m} </math>.
Алгоритм:
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 строит матрицу <math>M_{d,i}</math>, содержащую все многочлены <math>x_{1}^{\alpha_{1}} \dots x_{n}^{\alpha_{n}}f_{i}</math> с <math>\alpha_{1} + \dots + \alpha_{n} = d - d_{i}</math> (кроме тех, которые тривиально сводятся к нулю). Чтобы избежать избыточных вычислений, они строятся из строк предыдущей матрицы <math>M_{d-1,i}</math>, то есть все строки умножаются на все переменные. Строка с индексом <math>(i, x_{1}^{\alpha_{1}} \dots x_{j}^{\alpha_{j}})</math> с <math>\alpha_{j} \neq 0</math> может возникать из нескольких строк в <math>M_{d-1,i}</math>, мы можем построить его из строки, проиндексированной <math>(i, u)</math> в <math>M_{d-1,i}</math>, с <math>u = x_{1}^{\alpha_{1}} \dots x_{j}^{\alpha_{j - 1}}</math>, и умножить ее на <math>x_{j}</math>, наибольшую переменную, встречающуюся в <math>u</math>. Это гарантирует, что каждая строка берется ровно из одной строки предыдущей матрицы.
Пример работы алгоритма F5
Рассмотрим однородную систему в <math>\mathbb{F}_{23}[x,y,z]</math> с градуированным обратным лексографическим порядком <math>(x \succ y \succ z)</math> по матричному алгоритму <math>F5</math>.
- <math>
\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} </math>
Чтобы вычислить базис Грёбнера <math>{f_{1}, f_{2}, f_{3}}</math> мы задаем <math>F_{1} = (e_{1}, f_{1})</math>, <math>F_{2} = (e_{2}, f_{2})</math> и <math>F_{3} = (e_{3}, f_{3})</math> и рассматриваем критические пары <math>[F_{1}, F_{2}] = (1, f_{1}, 1, f_{2}), [F_{1}, F_{3}] = (1, f_{1}, 1, f_{3})</math> и <math>[F_{2}, F_{3}] = (1, f_{2}, 1, f_{3})</math>. Как и в алгоритме <math>\mathbb{F}_{4}</math> мы используем часть <math>1xf_{1}, 1xf_{2}, 1xf_{3}</math> для построения матрицы степени 2, чтобы свести эти три критические пары вместе:
- <math>
\begin{array}{ll}
\begin{align}
\\ A_2 =
\begin{align}
f_3 \\
f_2 \\
f_1
\end{align}
\end{align}
& \begin{align}\\ \left(\begin{align}\\ \\ \\ \end{align}\right.\end{align} \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{align}\\ \left.\begin{align}\\ \\ \\ \end{align}\right)\end{align} \end{array} </math>
и после приведения матрицы <math>A_{2}</math> к треугольному виду:
- <math>
\begin{array}{ll}
\begin{align}
\\ B_2 =
\begin{align}
f_3 \\
\underline{f_2} \\
f_1
\end{align}
\end{align}
& \begin{align}\\ \left(\begin{align}\\ \\ \\ \end{align}\right.\end{align} \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{align}\\ \left.\begin{align}\\ \\ \\ \end{align}\right)\end{align} \end{array} </math>
и появляются два "новых" многочлена: <math>f_{4} = xy + 4yz + 2xz + 3y^{2} - z^{2} \ (F_{4} = (e_{2},f_{4}))</math> и <math>f_{5} = y_{2} - 11xz - 3yz - 5z^{2} \ (F_{5} = (e_{3},f_{5}))</math>, которые являются результатом понижения критических пар <math>[F_{1}, F_{2}], [F_{1}, F_{3}]</math> и <math>[F_{2}, F_{3}]</math>. Обратите внимание, что сигнатура полинома <math>f_{4}</math> равна <math>e_{2}</math>, что соответствует метке слева от этой строки (подчеркнуто <math>f_{2}</math> в матрице <math>B_{2}</math>).
Также отметим, что подчеркнутая цифра 18 не уменьшается на <math>f_{4}</math>, так как подпись <math>f_{3}</math> равна <math>e_{3}</math>, которая меньше <math>e_{2}</math>. В то время как подчеркнутый 0 уменьшается, так как <math>e_{1} \succ e_{2}</math>. Это доказывает, что редукция в алгоритме <math>\mathbb{F}_{5}</math> является односторонней редукцией.
Следующим шагом является рассмотрение новых критических пар: <math>[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})</math> и <math>[F_{5}, F_{3}] = (x^{2}, f_{5}, y^{2}, f_{3})</math>. Мы выбираем пары по степени и строим матрицу <math>A_{3}</math> степени 3 для работы со следующими критическими парами <math>[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})</math> вместе. Нам нужно только рассмотреть части <math>yf_{3}, yf_{4}, xf_{4}, xf_{5}</math>, c частями <math>yf_{2}, yf_{1}</math>, которые являются перезаписываемыми <math>F_{4}</math> и <math>F_{5}</math> соответственно.
Как и алгоритм <math>\mathbb{F}_{5}</math>, части <math>yf_{3} , yf_{4} , xf_{4}, xf_{5}</math> - это те строки, которые должны быть уменьшены в Матрице, и нам также нужно выбрать части, которые используются для уменьшения этих строк. Так как <math>y^{3}, x^{2}z, xyz, y^{2}z</math> являются частями <math>yf_{3}, yf_{4}, xf_{4}, xf_{5}</math>, мы должны добавить части <math>yf_{5}, xf_{3}, zf_{4}, zf_{5}</math> в матрицу <math>A_{3}</math>, чтобы устранить их.
Теперь у нас есть матрица <math>A_{3}</math> со степенью 3 (упорядоченная по сигнатуре):
- <math>
\begin{array}{ll}
\begin{align}
\\ A_3 =
\begin{align}
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{align}
\end{align}
& \begin{align}\\ \left(\begin{align}\\ \\ \\ \\ \\ \\ \\ \\ \end{align}\right.\end{align} \begin{matrix} x^2y & xy^2 & y^3 & x^2z & xyz & y^2z & 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{align}\\ \left.\begin{align}\\ \\ \\ \\ \\ \\ \\ \\ \end{align}\right)\end{align} \end{array} </math>
и после приведения к треугольному виду:
- <math>
\begin{array}{ll}
\begin{align}
\\ B_3 =
\begin{align}
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{align}
\end{align}
& \begin{align}\\ \left(\begin{align}\\ \\ \\ \\ \\ \\ \\ \\ \end{align}\right.\end{align} \begin{matrix} x^2y & xy^2 & y^3 & x^2z & xyz & y^2z & 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{align}\\ \left.\begin{align}\\ \\ \\ \\ \\ \\ \\ \\ \end{align}\right)\end{align} \end{array} </math>
и полином <math>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}))</math> и <math>f_{8} = yz^{2} +18z^{3} (F_{8}=(xe_{1},f_{8})</math> являются результатами редукции критических пар со степенью 3. Обратите внимание, что хотя <math>lpp(f_{6}) = y^{3} = ylpp(f_{5})</math>, помеченный полином <math>F_{6}</math> не является <math>\mathbb{F}_{5}</math> - приводимым к <math>F_{5}</math> . Таким образом, <math>f_{6}</math> все еще является "новым" многочленом.
Теперь смысл написанного критерия гораздо яснее. При построении матрицы <math>A_{3}</math>, мы перечислим сигнатуры каждой строки (полинома) в круглых скобках. Помеченные многочлены с одинаковыми сигнатурами будут появляться в одной и той же строке матрицы, поэтому достаточно иметь дело с последними результатами (вот почему мы думаем о порядке создания помеченных многочленов). Также одностороннее сокращение очевидно в матрице <math>B_{3}</math>. Давайте посмотрим на строку <math>xf_{4} (xe_{2})</math>. Подчеркнутые 0, 0 уменьшаются на строчках <math>zf_{3} (ze_{3})</math> и <math>zf_{4} (ze_{2})</math> соответственно, а подчеркнутые 8,1,18 не исключены в строках <math>zf_{5} (ze_{1}), yf_{5} (ye_{1})</math> и <math>xf_{5} (xe_{1})</math>. причина заключается в том, что редукция в алгоритме <math>\mathbb{F}_{5}</math> это односторонняя редукция. Более конкретно, сигнатуры строк <math>zf_{3} (ze_{3})</math> и <math>zf_{4} (ze_{2})</math> это <math>ze_{3}</math> и <math>ze_{2}</math>, которые оба меньше <math>xe_{2}</math> строчки <math>xf_{4} (xe_{2})</math>.
Таким образом, строки <math>zf_{3} (ze_{3})</math> и <math>zf_{4} (ze_{2})</math> способны уменьшить строку <math>xf_{4} (xe_{2})</math>. Тем не менее, у нас есть <math>ze_{1}, ye_{1}, xe_{1} \succ xe_{2}</math>, так строки <math>zf_{5} (ze_{1}), yf_{5} (ye_{1})</math> и <math>xf_{5} (xe_{1})</math> не сократить строки <math>xf_{4} (xe_{2})</math>. Заметим, что поскольку только строки <math>xf_{4} (xe_{2}), yf_{5} (ye_{1})</math> и <math>xf_{5} (xe_{1})</math> требуют сохранения, другие строки не полностью уменьшаются в матрице <math>B_{3}</math>.
Однако мы должны понимать, что, хотя два новых критерия алгоритма <math>\mathbb{F}_{5}</math> могут отбросить почти все бесполезные вычисления, одностороннее сокращение приводит к более низкой эффективности устранения матрицы, чем алгоритм <math>\mathbb{F}_{4}</math>.
Литература
- 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
