Алгоритм F5 вычисления базиса Грёбнера был предложен Ж.-Ш. Фожером в 2002 году. В данной работе рассмотрим его матричную версию, работающую для однородных многочленов. Основная процедура этого алгоритма вычисляет d-базис Грёбнера, то есть, подмножество базиса Грёбнера, относительно которого редуцируются к нулю все многочлены из идеала степени не выше, чем d.
В алгоритме F5 каждому полученному многочлену сопоставляется сигнатура (пара из монома и номера образующей), кодирующая информацию о происхождении этого многочлена. Основная идея - не включать по возможности в матрицы те строки, которые заведомо будут линейно зависимы с остальными (то есть, будут редуцироваться к нулю.)
Для этого редукции ограничиваются такими, которые не изменяют сигнатуру элементов, а также среди очередных обрабатываемых многочленов рассматриваются лишь те, моном сигнатуры которых не делится ни на один старший моном уже найденных элементов базиса.
Вход: однородные многочлены
со степенями
максимальная степень
.
Выход: элементы степени не выше
приведенного базиса Грёбнера из
для
.
Алгоритм:
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 {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44fd7c5200e7209f3f684f4f2e82e3b312141bbe)
Чтобы вычислить базис Грёбнера
мы задаем
,
и
и рассматриваем критические пары
и
. Как и в алгоритме
мы используем часть
для построения матрицы степени 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b92cb75974123b130c40c6ab95f3dd3340b25a96)
и после приведения матрицы
к треугольному виду:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d14f2ce630e38c843e9ef4bf6a0617efe99235d)
и появляются два "новых" многочлена:
и
, которые являются результатом понижения критических пар
и
. Обратите внимание, что сигнатура полинома
равна
, что соответствует метке слева от этой строки (подчеркнуто
в матрице
).
Также отметим, что подчеркнутая цифра 18 не уменьшается на
, так как подпись
равна
, которая меньше
. В то время как подчеркнутый 0 уменьшается, так как
. Это доказывает, что редукция в алгоритме
является односторонней редукцией.
Следующим шагом является рассмотрение новых критических пар:
и
. Мы выбираем пары по степени и строим матрицу
степени 3 для работы со следующими критическими парами
вместе. Нам нужно только рассмотреть части
, c частями
, которые являются перезаписываемыми
и
соответственно.
Как и алгоритм
, части
- это те строки, которые должны быть уменьшены в Матрице, и нам также нужно выбрать части, которые используются для уменьшения этих строк. Так как
являются частями
, мы должны добавить части
в матрицу
, чтобы устранить их.
Теперь у нас есть матрица
со степенью 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41e8cff6b4225d6d4918cba86e105b44fee61b74)
и после приведения к треугольному виду:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa2cca11823a7c48e7a8125a8bce4a47b102c154)
и полином
и
являются результатами редукции критических пар со степенью 3. Обратите внимание, что хотя
, помеченный полином
не является
- приводимым к
. Таким образом,
все еще является "новым" многочленом.
Теперь смысл написанного критерия гораздо яснее. При построении матрицы
, мы перечислим сигнатуры каждой строки (полинома) в круглых скобках. Помеченные многочлены с одинаковыми сигнатурами будут появляться в одной и той же строке матрицы, поэтому достаточно иметь дело с последними результатами (вот почему мы думаем о порядке создания помеченных многочленов). Также одностороннее сокращение очевидно в матрице
. Давайте посмотрим на строку
. Подчеркнутые 0, 0 уменьшаются на строчках
и
соответственно, а подчеркнутые 8,1,18 не исключены в строках
и
. причина заключается в том, что редукция в алгоритме
это односторонняя редукция. Более конкретно, сигнатуры строк
и
это
и
, которые оба меньше
строчки
.
Таким образом, строки
и
способны уменьшить строку
. Тем не менее, у нас есть
, так строки
и
не сократить строки
. Заметим, что поскольку только строки
и
требуют сохранения, другие строки не полностью уменьшаются в матрице
.
Однако мы должны понимать, что, хотя два новых критерия алгоритма
могут отбросить почти все бесполезные вычисления, одностороннее сокращение приводит к более низкой эффективности устранения матрицы, чем алгоритм
.
- 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