Русская Википедия:F4 (алгоритм)

Алгоритм F4 был предложен Жан-Шарль Фожером (Jean-Charles Faugerе) в 1999 г как новый эффективный алгоритм вычисления базиса Грёбнера^[1]. Этот алгоритм вычисляет базис Грёбнера идеала в кольце многочленов с помощью серии стандартной процедуры линейной алгебры: приведений матриц к ступенчатому виду. Он является одним из самых быстрых на сегодняшний день.

Алгоритм

Определения

Критическая пара <math>(f_i,f_j)</math> является членом

такое, что

Определим степень критической пары <math>p_{i,j}= Pair(f_i,f_j), deg(p_{i,j})</math> как <math>deg(HOK_{i,j})</math>.

Определим следующие операторы: <math>Left(p_{i,j}):= t_i \cdot f_i</math> and <math>Right(p_{i,j}):= t_j \cdot f_j</math>

Псевдокод алгоритма F4 (упрощённая версия)

Вход: <math>\begin{cases} F \text{ конечное подмножество } K[X_1,...,X_n]
\\ Sel \text{ функция } List(Pairs) \rightarrow List(Pairs) \\ \text{такое, что } Sel(I) \neq \varnothing \text{ если } I \neq \varnothing \end{cases}</math>
Выход: конечное подмножество <math>K[X_1,...,X_n]</math>

<math>G:=F,\tilde{F}_0+:=F:=0 \text{ и } P:=\{Pair(f,g) | (f,g) \in G^2 \text{ c } f \neq g\}</math>
While <math>P\neq \varnothing </math> do
<math>d:=d+1</math>
<math>P_d := Sel(p)</math>
<math>P:=P \backslash P_d</math>
<math>L_d:=Left(P_d) \cup Right(P_d)</math>
<math>\tilde{F}_d^+:=Reduction(L_d,G)</math>
for <math>h \in \tilde{F}_d^+</math> do
<math>P:=P\cup\{Pair(h,g)| g\in G\} G:=G\cup\{h\}</math>

return <math>G</math>

Алгоритм редукции

Теперь мы можем расширить определение редукции полинома по модулю

подмножества <math>K[X_1,...,X_n]</math>, до редукции подмножества <math>K[X_1,...,X_n]</math> по

модулю другого подмножества <math>K[X_1,...,X_n]</math>:

Вход: L, G конечные подмножества <math>K[X_1,...,X_n]</math>
Выход: конечные подмножества <math>K[X_1,...,X_n]</math> (Может быть пустым)

<math>F:= \text{SymbolicPreprocessing} (L,G) </math>
<math>\tilde F := \text{Редукция Гауса } F \text{ относительно} < </math>
<math>\tilde F^+ := \{f\in \tilde F | LT(f) \not\in LT(F) \}</math>

return <math> \tilde{ F^+}</math>

Арифметическая операция не используется: это символьный препроцессинг.

Алгоритм Символьного Препроцессинга

Вход: L, G конечные подмножества <math>K[X_1,...,X_n]</math>
Выход: конечные подмножества <math>K[X_1,...,X_n]</math>
<math>F:=L</math>
<math>Done:=LT(F)</math>
while <math>T(F)\neq Done</math> do
<math>m \in T(F)\backslash Done</math>
<math>Done:=Done\cup\{m\}</math>
if <math>m</math> приводим сверху по модулю <math>G</math> then
существует <math>g \in G \text{ И } m^' \in T : m = m^' \cdot LT(g) </math>
<math>F:=F \cup \{m^'\cdot g\}</math>

return <math>F</math>

Лемма

Для всех многочленов <math>p \in L_d</math>, мы имеем <math>p \xrightarrow[]{G\cup \tilde F +} 0</math>

Теорема (без доказательства)

Алгоритм <math>F_4</math> вычисляет базис Гребнера G в <math>K[X_1,...,X_n]</math>

такой что <math>F \subseteq G \text{ И } Id(G) = Id(F). </math>

Замечание

Если #<math> Sel(I) = 1 </math> для всех <math>I \neq \varnothing </math>, тогда алгоритм <math>F_4</math> сводится к алгоритму Бухбергера. В этом случае функция Sel является эквивалентом стратегии выбора для алгоритма Бухбергера.

Функция выбора

Вход: <math>P</math> список критических пар
Выход: список критических пар
<math>d := min\{deg(lcm(p))\}</math>
<math>P_d:=\{p\in P | deg(lcm(p)) = d\}</math>

return <math>P_d</math>

Назовём эту стратегию нормальной стратегией для <math>F_4</math>.

Следовательно, если входные полиномы однородны, мы получаем в степени, и d - базис Гребнера.

На следующем шаге мы выбираем все критические пары, необходимые для вычисления базиса Гребнера в степени d+1.

Оптимизация алгоритма F4

Существует несколько путей оптимизации алгоритма:

включение критерия Бухбергера (или критерия F5);

повторное использование всех строк в приведённых матрицах.

Критерии Бухбергера Алгоритм - реализация:

<math>(G_{new},p_{new}):= Update(G_{old},P_{old},h)
</math>
Вход: <math>\begin{cases} \text{конечное подмножество } G_{old} \text{ в } K[X_{1},...,X_{n}] \\ \text{конечное подмножество } P_{old} \text{ критических пар в } K[X_{1},...,X_{n}] \\ 0 \neq h \in K[x_1,...,X_n] \end{cases}</math>

Выход: конечное подмножество в <math>K[X_1,...,X_n]</math> обновлённый список критических пар

Пседвокод алгоритма F4 (с критерием)

Вход: <math>\begin{cases}
F \subset K[X_1,...,X_n] \\ Sel \text{ функция } List(Pairs) \rightarrow List(Pairs) \end{cases}</math>
Выход: конечное подмножество <math>K[X_1,...,X_n]</math>.
<math>G:= \varnothing \text{ И } P:= \varnothing \text{ И } d:= 0</math>
while <math>F \neq \varnothing</math> do
<math>f:=first(F); F:F \backslash \{f\} </math>
<math>(G,P) := Update(G,P,f) </math>
while <math>P \neq \varnothing</math> do
<math>d:=d+1</math>
<math>P_d:=Sel(P); P:=P \backslash P_d</math>
<math>L_d := Left(P_d) \cup Right(P_d)</math>
<math>(\tilde F_d^+,F_d):= Reduction(L_d,G,(F_i)_{d=1,...,(d-1)})</math>
for <math>P \neq \tilde F_d^+</math>
<math>P:=P \cup \{ Pair(h,g) | g \in G\}</math>
<math>(G,P):=Update(G,P,h)</math>

return <math>G</math>

F4 и его отличия от Алгоритма Бухбергера

Пусть есть некоторое конечное множество многочленов <math>F</math>. По этому множеству строится большая разреженная матрица, строки которой соответствуют многочленам из <math>F</math>, а столбцы — мономам. В матрице записаны коэффициенты многочленов при соответствующих мономах. Столбцы матрицы отсортированы согласно выбранному мономиальному упорядочению (старший моном соответствует первому столбцу). Приведение такой матрицы к ступенчатому виду позволяет узнать базис линейной оболочки многочленов из <math>F</math> в пространстве многочленов.

Пусть в классическом алгоритме Бухбергера требуется провести шаг редукции многочлена <math>f</math> относительно <math>g</math>, и при этом <math>g</math> должен быть домножен на моном <math>M</math>. В алгоритме F4 в матрицу будут специально помещены <math>f</math> и <math>M</math><math>g</math>. Утверждается, что можно заранее подготовить множество всех потенциальных домноженных редукторов, которые могут потребоваться, и поместить их заранее в матрицу.^[2]

Обобщим алгоритм F4^[3]:

пусть нам требуется отредуцировать многочлен <math>f</math> относительно множества <math>F</math>. Для этого мы

(1) добавляем <math>f</math> в матрицу;

(2) строим носитель <math>\mathcal{M}</math> многочлена <math>f</math> (множество мономов);

(3) если <math>\mathcal{M}</math> пусто, то заканчиваем процедуру;

(4) выбираем максимальный моном <math>M</math> в <math>\mathcal{M}</math> (и выкидываем его из <math>\mathcal{M}</math>);

(5) если <math>M</math> не делится ни на один старший моном элементов <math>F</math>, то переходим к шагу (3);

(6) иначе выбираем редуктор <math>r</math> ∈ <math>F</math> (и дополнительный множитель <math>t </math>): тогда <math>M</math><math>=LM</math> <math>tr</math>;

(7) добавляем <math>tr</math> в матрицу;

(8) добавляем мономы многочлена <math>tr</math> (кроме старшего <math>M</math>) ко множеству <math>\mathcal{M}</math>;

(9) переходим к шагу (3).

Эта процедура пополнения матрицы домноженными редукторами называется символьным препроцессингом. Кроме того, вместо S-полиномов можно поместить в матрицу их левые и правые части (при редукции одной строки по другой автоматически получится S-полином).

Наконец, третьим отличием от алгоритма Бухбергера является то, что в алгоритме F4 разрешается поместить в одну матрицу части сразу нескольких S-полиномов, выбранных согласно какой-либо стратегии. Так, если на каждом шаге выбирается один S-полином, то он повторяет классический алгоритм Бухбергера.

Другая крайность — когда на очередном шаге редуцируется множество всех имеющихся S-полиномов. Это тоже не очень эффективно из-за больших размеров матриц. Автор алгоритма Ж.-Ш. Фожер предложил нормальную стратегию выбора S-полиномов для редукции^[4], согласно которой выбираются S-полиномы с наименьшей степенью левых и правых частей. Она даёт хорошие эмпирические результаты для упорядочения DegRevLex и ее выбор является естественным для однородных идеалов.

В алгоритм можно внести несколько естественных усовершенствований. Как и в классическом алгоритме вычисления базиса Грёбнера, можно применять критерии Бухбергера для отсеивания заведомо ненужных S-полиномов.

Реализации

Реализован алгоритм F4

в FGb - собственная реализация Фожера^[4], которая включает интерфейсы для его использования из C/C ++ или Maple;
в системе компьютерной алгебры Maple в качестве опции method = fgb функции Groebner [gbasis];
в системе компьютерной алгебры Magma , в системе компьютерной алгебры SageMath.

Пример

Задача: посчитать базис Грёбнера для многочленов <math>\{f_1=abcd-1;f_2=abc+abd+acd+bcd;f_3=ab+bc+ad+cd;f_4=a+b+c+d\}</math>В начале присваиваем <math>G={f_4},</math> <math>P_1={Pair(f_3,f_4)},</math> <math>L_1=\{(1,f_3),(b,f_4)\}</math>

1) Символьный препроцессинг<math>(L_1,G,\varnothing):</math>

<math>ab</math> уже готов.

2) Символьный препроцессинг<math>(L_1,G,\varnothing):</math>

<math>ad</math> сверху сводится к <math>f_4 \in G</math>.

3) Символьный препроцессинг<math>(L_1,G,\varnothing):</math>

<math>b^2</math> не сводится к <math> G</math>.

4) <math>F_1=\{{f_3,bf_4, df_4}\}.</math>

Матричное представление полученного <math>F_1</math>:

<math>A_1=M(F_1)=\begin{pmatrix}\{& ab & b^2 & bc & ad & bd & cd & d^2\} \\ ( df_4) & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ ( f_3) & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ ( bf_4) &1 & 1 & 1 & 0 & 1 & 0 & 0

\end{pmatrix}</math>

Редукция Гаусса полученной матрицы <math>A_1</math>:

<math>\tilde{A_1}=\begin{pmatrix}\{& ab & b^2 & bc & ad & bd & cd & d^2\} \\ ( df_4) & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ ( f_3) & 1 & 0 & 1 & 0 & -1 & 0 & -1 \\ ( bf_4) &0 & 1 & 0 & 0 & 2 & 0 & 1

\end{pmatrix}</math>

По этой матрице получаем:

<math>\tilde{F_1} =[f_5 = ad +bd +cd +d^2, f_6 = ab + bc - bd - d^2, f_7 = b^2 + 2bd +d^2 ]</math>

А так как <math>ab, ad \in LT(F_1)</math>, то

<math>\tilde{F_{1+}} = [f_7]</math> и тогда <math>G = \{f_4,f_7\}.</math>

Для следующего шага мы должны рассмотреть <math>P_2 = \{Pair(f_2,f_4)\}</math>

Отсюда <math>L_2 = \{(1,f_2),(bc,f_4)\} \text{и} \mathcal{F} =\{F_1\}.</math>

В Символьном препроцессинге можно попытаться упростить <math>1\cdot f_2 \text{и} bc\cdot f_4</math> используя предыдущие вычисления:

Например,<math>LT (bcf_4)= abc = LT(cf_6) \text{ и поэтому вместо } bc \cdot f_4 \text{ можно использовать }c \cdot f_6 </math>1) Символьный препроцессинг

2) Символьный препроцессинг

3) Символьный препроцессинг

<math>F_2=\{{f_2,cf_6}\}, T(F_2)=\{abc,bc^2,abd, acd,bcd, c d^2\}</math><math>abd \text{ сводится к } bcf_4 \text{ а также к } bf_5 </math>

Опишем упрощение

Цель: заменить любое произведение <math>m \cdot f</math> на произведение <math>(uf) \cdot f'</math>, где <math>(t,f')</math> - ранее вычисленная строка, а <math>uf</math> делит моном <math>m</math>

В первом варианте алгоритма: некоторые строки матрицы никогда не используются (строки в матрице <math>\tilde F_d \backslash \tilde F_d^+ </math>).

Новая версия алгоритма: мы сохраняем эти строки

<math>m \cdot f \in Rows(F) \rightarrow m^' \cdot f ^' \text{ c } m \geq m^' </math>

<math>m \cdot f \in Rows(F) \rightarrow X_k\cdot f^' </math>

SIMPLIFY пытается заменить произведение <math>m\cdot f </math> произведением <math>(ut)\cdot f^' </math>, где

<math>(t,f^') </math>уже вычисленная строка в гауссовой редукции, и u t делит моном m; Если мы нашли такое лучшее произведение, то рекурсивно вызываем функцию SIMPLIFY:

Вход: <math>\begin{cases}
t \in T \text{ моном} \\ t \in K[X_1,...,X_n] \text { многочлен}\\ F = (F_i)_{d=1,...,(d-1)}, \text{ Где } F_k \in K[X_1,...,X_n] \end{cases} </math>
Выход: Результат <math>m^'*f^' </math> эквивалентно <math>t*f </math>
for <math>u \in \text{ список делителей } t </math> do
if <math>\exist j (1\leq j < d) : (u\cdot f)\in F_j \text{ then} </math>
<math>\tilde F_j \text{Гауссова редукция} F_j \text{ Относительно} < </math>
<math>\exists ! p \in \tilde F_j : LT(p) = LT(u*f) </math>
if <math>u \neq t \text{ then} </math>
return <math> Simplify(\frac{t}{u},p,F) </math>
else return <math>1*p </math>

return <math>t*f </math>

Algorithm SYMBOLICPREPROCESSING

Вход: <math>\begin{cases}
L, G \text{ конечные подмножества } K[X_{1},...,X_{n}] \\ F = (F_i)_{d=1,...,(d-1)}, \text{ Где } F_k \\ \text{конечное подмножество} K[X_{1},...,X_{n}] \end{cases}</math>
Выход: конечное подмножество <math>K[X_1,...,X_n]</math>.
<math>F:=L</math>
<math>Done:=LT(F)</math>
while <math>T(F) \neq Done </math> do
<math>m \in T(F)\backslash Done</math>
if <math>m</math> приводим сверху по модулю <math>G</math> then
существует <math>g \in G \text{ И } m^' \in T : m = m^' \cdot LT(g) </math>
<math>F:=F \cup \{Simplify(m^', g, F)\}</math>

return <math>F</math>

Теперь возвращаемся к примеру.

4) Символьный препроцессинг

И так далее....

5) Символьный препроцессинг

<math>A_2 = M(F_2)= \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 \end{bmatrix}</math>

После редукции Гаусса:

<math>\tilde{A_2} = \tilde{M(F_2)}= \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & -1 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0& -1 & -1 & 1 & -1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 0 & -1 \end{bmatrix}</math>

<math>\tilde{F_2} =\begin{bmatrix} f_9 = acd +bcd +c^2d +cd^2, \\ f_{10} = b^2d +2bd^2 +d^3, \\ f_{11} = abd +bcd - bd^2 - d^3, \\ f_{12} = abc -bcd -c^2d +bd^2 -cd^2 +d^3, \\ f_{13} = bc^2 +c^2d -bd^2 - d^3 \end{bmatrix}</math>

и <math>G =\{f_4,f_7,f_{13}\}</math>

На следующем шаге имеем:

и рекурсивно вызываем упрощение:

<math>Simplify(bcd,f_4)=Simplify(cd,f_6)=Simplify(d,f_{12})=(d,f_{12}) </math>

На следующем шаге имеем:

После некоторых вычислений, получается, что ранг <math>M(F_3) </math> составляет 5.

Это означает, что есть бесполезное сведение к нулю.

На следующем шаге имеем:

Символьный препроцессинг

<math>\tilde{F_3} =\begin{bmatrix} f_{15} = c^2b^2 - c^2d^2 + 2bd^3 +2d^4, \\ f_{16} = abcd - 1 , \\ f_{17} = -bcd^2 -c^2d^2 - bd^3 - d^4 +1, \\ f_{18} = c^2bd + c^2d^2 -bd^3 - d^4, \\ f_{19} = b^2d^2 + 2bd^3 + d^4 \end{bmatrix}</math>

Ссылки

https://en.wikipedia.org/wiki/Magma_(computer_algebra_system)

Примечания

Шаблон:Примечания

Литература

J.-C. Faug`ere. A new efficient algorithm for computing Gr¨obner bases without reduction to zero (F5).
J.-C. Faug`ere A New Efficient Algorithm for Computing Gr¨obner Bases (F4). Journal of Pure and Applied Algebra, 139 (1999), 61–88.
Cox D., Little J., O’Shea D., Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, New York, NY: Springer, 1998. [Имеется перевод: Кокс Д., Литтл Дж., О’Ши Д., Идеалы, многообразия и алгоритмы, М., Мир, 2000.]

[:0-1] Шаблон:Книга

[2] Шаблон:Статья

[3] Шаблон:Статья

[:1-4] 4,0 ^4,1 Шаблон:Cite web

[1]

[2]

[3]

[4]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:F4 (алгоритм)

Содержание

Алгоритм

Определения

Псевдокод алгоритма F4 (упрощённая версия)

Алгоритм редукции

Алгоритм Символьного Препроцессинга

Лемма

Теорема (без доказательства)

Функция выбора

Оптимизация алгоритма F4

Пседвокод алгоритма F4 (с критерием)

F4 и его отличия от Алгоритма Бухбергера

Реализации

Пример

Опишем упрощение

Ссылки

Примечания

Литература

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты