базис Грёбнера

Математическая конструкция в компьютерной алгебре

В математике , а точнее в компьютерной алгебре , вычислительной алгебраической геометрии и вычислительной коммутативной алгебре , базис Грёбнера — это особый вид порождающего набора идеала в кольце полиномов K [ x ₁ ,..., x _n ] над поле К. _ Базис Грёбнера позволяет легко вывести многие важные свойства идеала и связанного с ним алгебраического многообразия , такие как размерность и количество нулей, когда оно конечно. Вычисление в базисе Грёбнера — один из основных практических инструментов решения систем полиномиальных уравнений и вычисления образов алгебраических многообразий при проекциях или рациональных отображениях .

Вычисление базиса Грёбнера можно рассматривать как многомерное нелинейное обобщение как алгоритма Евклида для вычисления полиномиальных наибольших общих делителей , так и метода исключения Гаусса для линейных систем. ^[1]

Базы Грёбнера были представлены Бруно Бухбергером в его докторской диссертации 1965 года. диссертация, которая также включала алгоритм их вычисления ( алгоритм Бухбергера ). Он назвал их в честь своего советника Вольфганга Грёбнера . В 2007 году Бухбергер получил за эту работу премию Парижа Канеллакиса в области теории и практики от Ассоциации вычислительной техники . Однако русский математик Николай Гюнтер ввел подобное понятие в 1913 году и опубликовал его в различных российских математических журналах. Эти статьи в значительной степени игнорировались математическим сообществом до их повторного открытия в 1987 году Бодо Реншухом и др. ^[2] Аналогичная концепция многомерных степенных рядов была независимо разработана Хейсуке Хиронакой в ​​1964 году, который назвал их стандартными базисами . Некоторые авторы использовали этот термин для обозначения базисов Грёбнера.

Теория базисов Грёбнера развивалась многими авторами в различных направлениях. Он был обобщен на другие структуры, такие как многочлены над кольцами главных идеалов или кольцами полиномов , а также на некоторые классы некоммутативных колец и алгебр, таких как алгебры Оре .

Инструменты

Полиномиальное кольцо

Базисы Грёбнера в первую очередь определяются для идеалов в кольце полиномов над полем K . Хотя теория работает для любого поля, большинство вычислений по базису Грёбнера выполняются либо тогда, когда K является полем рациональных чисел , либо целыми числами по модулю простого числа. ${\displaystyle R=K[x_{1},\ldots ,x_{n}]}$

В контексте базисов Грёбнера ненулевой многочлен обычно представляется как сумма, где являются ненулевыми элементами K , называемыми коэффициентами , и являются мономами (называемыми степенными произведениями Бухбергером и некоторыми из его последователей) вида , где неотрицательные целые числа. Вектор называется вектором показателя монома. Когда список переменных фиксирован, обозначение мономов часто сокращается как ${\displaystyle R=K[x_{1},\ldots ,x_{n}]}$ ${\displaystyle c_{1}M_{1}+\cdots +c_{m}M_{m},}$ ${\displaystyle c_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}},}$ ${\displaystyle a_{i}}$ ${\displaystyle A=[a_{1},\ldots ,a_{n}]}$ ${\displaystyle X=[x_{1},\ldots ,x_{n}]}$ ${\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}=X^{A}.}$

Мономы однозначно определяются своими векторами экспоненты, и, когда мономиальный порядок (см. ниже) фиксирован, полином однозначно представляется упорядоченным списком упорядоченных пар , образованных вектором экспоненты и соответствующим коэффициентом. Такое представление полиномов особенно эффективно для вычислений на основе базиса Грёбнера в компьютерах, хотя оно менее удобно для других вычислений, таких как факторизация полинома и определение наибольшего общего делителя полинома .

Если – конечное множество многочленов в кольце полиномов R , то идеал, порожденный F , – это набор линейных комбинаций элементов F с коэффициентами из R ; это набор многочленов, которые можно записать с помощью ${\displaystyle F=\{f_{1},\ldots ,f_{k}\}}$ ${\textstyle \sum _{i=1}^{k}g_{i}f_{i}}$ ${\displaystyle g_{1},\ldots ,g_{k}\in R.}$

Мономиальный порядок

Все операции, связанные с базисами Грёбнера, требуют выбора полного порядка мономов со следующими свойствами совместимости с умножением. Для всех мономов M , N , P ,

1. ${\displaystyle M\leq N\Longleftrightarrow MP\leq NP}$
2. ${\displaystyle M\leq MP}$.

Полный порядок, удовлетворяющий этим условиям, иногда называют допустимым порядком .

Эти условия подразумевают, что порядок является хорошим порядком , то есть каждая строго убывающая последовательность мономов конечна.

Хотя базисная теория Грёбнера не зависит от конкретного выбора допустимого мономиального порядка, для приложений особенно важны три мономиальных порядка:

• Лексикографическое упорядочение , обычно называемое lex или plex (от чистого лексического упорядочения).
• Полная степень обратного лексикографического упорядочения , обычно называемая дегревлексом .
• Порядок исключения , lexdeg .

Базисная теория Грёбнера была первоначально введена для лексикографического упорядочения. Вскоре стало понятно, что базис Грёбнера для дегревлекса почти всегда гораздо проще вычислить, и что почти всегда легче вычислить базис Грёбнера, сначала вычислив базис дегревлекса, а затем используя «алгоритм изменения порядка». Когда необходимо устранение, дегревлекс неудобен; можно использовать и lex, и lexdeg, но, опять же, многие вычисления относительно просты с lexdeg и практически невозможны с lex.

Основные операции

Главный член, коэффициент и моном

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

Первый (наибольший) член полинома p для этого порядка и соответствующие моном и коэффициент называются соответственно старшим членом , старшим мономом и старшим коэффициентом и обозначаются в этой статье lt( p ), lm( p ) и lc( п ) .

Большинство полиномиальных операций, связанных с базисами Грёбнера, включают ведущие члены. Итак, представление полиномов в виде отсортированных списков делает эти операции особенно эффективными (чтение первого элемента списка занимает постоянное время, независимо от длины списка).

Полиномиальные операции

Другие полиномиальные операции, используемые в базисных вычислениях Грёбнера, также совместимы с мономиальным порядком; то есть их можно выполнить без изменения порядка результата:

• Добавление двух многочленов заключается в слиянии двух соответствующих списков терминов с особым подходом в случае конфликта (то есть, когда один и тот же моном появляется в двух многочленах).
• Умножение многочлена на скаляр состоит из умножения каждого коэффициента на этот скаляр без какого-либо другого изменения представления.
• Умножение многочлена на моном m состоит из умножения каждого монома многочлена на m . Это не меняет термин «упорядочение» по определению мономиального порядка.

Делимость одночленов

Пусть и - два монома с векторами показателей и ${\displaystyle M=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}}$ ${\displaystyle N=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}}$ ${\displaystyle A=[a_{1},\ldots ,a_{n}]}$ ${\displaystyle B=[b_{1},\ldots ,b_{n}].}$

Говорят, что M делит N или что N кратно M , если для каждого i ; то есть, если A покомпонентно не больше, чем B . В этом случае частное определяется как Другими словами, вектор экспоненты представляет собой покомпонентное вычитание векторов экспоненты N и M . ${\displaystyle a_{i}\leq b_{i}}$ ${\textstyle {\frac {N}{M}}}$ ${\textstyle {\frac {N}{M}}=x_{1}^{b_{1}-a_{1}}\cdots x_{n}^{b_{n}-a_{n}}.}$ ${\textstyle {\frac {N}{M}}}$

Наибольший общий делитель gcd( M , N ) чисел M и N - это моном , вектор показателя которого является покомпонентным минимумом A и B . Наименьшее общее кратное lcm( M , N ) определяется аналогично с max вместо min . ${\textstyle x_{1}^{\min(a_{1},b_{1})}\cdots x_{n}^{\min(a_{n},b_{n})}}$

Надо

${\displaystyle \operatorname {lcm} (M,N)={\frac {MN}{\gcd(M,N)}}.}$

Снижение

Сокращение полинома другими полиномами относительно мономиального порядка занимает центральное место в теории базиса Грёбнера . Это обобщение сокращения строк , происходящего при исключении Гаусса и этапах деления евклидова деления одномерных многочленов . ^[1] Когда оно выполнено в максимально возможной степени, его иногда называют многомерным делением , хотя его результат не определен однозначно.

Сокращение свинца — это особый случай сокращения, который легче вычислить. Это имеет фундаментальное значение для вычисления базиса Грёбнера, поскольку общая редукция необходима только в конце вычисления базиса Грёбнера, чтобы получить уменьшенный базис Грёбнера из нередуцированного.

Пусть фиксирован допустимый мономиальный порядок, к которому относится каждое мономиальное сравнение, которое будет происходить в этом разделе.

Многочлен f можно привести к другому многочлену g , если ведущий моном lm( f ) кратен lm( g ) . Многочлен f можно сократить с помощью g , если некоторый моном f кратен lm( g ) . (Итак, если f приводимо к свинцу с помощью g , оно также приводимо, но f может быть приводимо, не будучи приводимым при помощи свинца.)

Предположим, что f можно сократить с помощью g , и пусть cm — такой член f , что моном m кратен lm( g ) . Одношаговое уменьшение f на g состоит в замене f на

${\displaystyle \operatorname {red} _{1}(f,g)=f-{\frac {c}{\operatorname {lc} (g)}}\,{\frac {m}{\operatorname {lm} (g)}}\,g.}$

Эта операция удаляет моном m из f без изменения членов с мономом, большим, чем m (для мономиального порядка). В частности, одношаговое сокращение f дает полином , все мономы которого меньше lm( f ) .

Учитывая конечное множество G полиномов, говорят, что f приводимо или свинцово приводимо с помощью G , если оно приводимо или свинцово приводимо, соответственно, по крайней мере к одному элементу g из G . В этом случае одношаговое уменьшение (соответственно одношаговое уменьшение опережения) f с помощью G представляет собой любое одношаговое уменьшение (соответственно одношаговое уменьшение опережения) f элементом G .

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

Определение редукции сразу показывает, что если h является нормальной формой f по G , то имеет место

${\displaystyle f=h+\sum _{g\in G}q_{g}\,g,}$

где h неприводим с помощью G, а the - многочлены такие, что В случае одномерных многочленов, если G состоит из одного элемента g , то h - это остаток евклидова деления f на g , а q _g - частное. Более того, алгоритм деления — это именно процесс сокращения лидов. По этой причине некоторые авторы используют термин многомерное деление вместо редукции. ${\displaystyle q_{g}}$ ${\displaystyle \operatorname {lm} (q_{g}\,g)\leq \operatorname {lm} (f).}$

Неединственность приведения

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

В этом примере с двумя переменными используется мономиальный порядок - это лексикографический порядок с , и мы рассматриваем сокращение ${\displaystyle x>y,}$

$${\displaystyle f=2x^{3}-x^{2}y+y^{3}+3y}$$

${\displaystyle G=\{g_{1},g_{2}\},}$

$${\displaystyle {\begin{aligned}g_{1}&=x^{2}+y^{2}-1,\\g_{2}&=xy-2.\end{aligned}}}$$

На первом этапе сокращения либо первый, либо второй член f может быть уменьшен. Однако сокращение срока равнозначно удалению этого срока за счет добавления новых более низких сроков; если сокращается не первый сокращаемый член, то может случиться так, что дальнейшее сокращение добавит аналогичный член, который придется сокращать снова. Поэтому всегда лучше сначала уменьшить наибольший (для мономиального порядка) приводимый член; то есть, в частности, сначала уменьшить свинец, пока не будет получен неприводимый к свинцу полином.

Главный член f можно сократить на, а не на. Итак, первый шаг сокращения состоит из умножения на –2 x и добавления результата к f : ${\displaystyle 2x^{3}}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2}.}$ ${\displaystyle g_{1}}$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.}$

Главный член кратен ведущим мономам обоих и Итак, у нас есть два варианта второго шага сокращения. Если кто-то выберет, он получит полином, который можно снова уменьшить на ${\displaystyle -x^{2}y}$ ${\displaystyle f_{1}}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2},}$ ${\displaystyle g_{2},}$ ${\displaystyle g_{2}\colon }$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {xg_{2}}{\longrightarrow }}\;-2xy^{2}+y^{3}+3y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{2}=y^{3}-y.}$

Дальнейшее сокращение невозможно, как и полное уменьшение f . ${\displaystyle f_{2}}$

Один получает другой результат при другом выборе для второго шага:

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {yg_{1}}{\longrightarrow }}\;-2xy^{2}+2x+2y^{3}+2y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{3}=2x+2y^{3}-2y.}$

Опять же, результат неуменьшаемый, хотя было сделано только сокращение свинца. ${\displaystyle f_{3}}$

Таким образом, полное уменьшение f может привести либо к ${\displaystyle f_{2}=y^{3}-y}$ ${\displaystyle f_{3}=2x+2y^{3}-2y.}$

Именно для решения проблем, возникающих из-за этой неединственности, Бухбергер ввел базисы Грёбнера и S -полиномы. Интуитивно, 0 = f - f можно свести к Это означает, что принадлежит идеалу, порожденному G . Таким образом, этот идеал не меняется при добавлении к G , и это позволяет сделать больше сокращений. В частности, может быть сведено к и при этом восстанавливается единственность приведенной формы. ${\displaystyle f_{2}-f_{3}.}$ ${\displaystyle f_{2}-f_{3}}$ ${\displaystyle f_{3}-f_{2}}$ ${\displaystyle f_{3}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{3}-f_{2}}$

Здесь алгоритм Бухбергера для базисов Грёбнера начинается с добавления к G полинома

${\displaystyle g_{3}=yg_{1}-xg_{2}=2x+y^{3}-y.}$

Этот многочлен, названный Бухбергером S -полиномом, представляет собой разность одношаговых сокращений наименьшего общего кратного ведущих мономов и (в этом примере это не завершает алгоритм Бухбергера, поскольку xy дает разные результаты, когда уменьшено на или ${\displaystyle x^{2}y}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{3}=f_{3}-f_{2}).}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{3}.}$

S -полиномиальный

S -полином, также называемый критической парой , относительно данного мономиального порядка, двух многочленов f и g , является многочленом

${\displaystyle {\begin{aligned}S(f,g)&=\operatorname {red} _{1}(\mathrm {lcm} ,g)-\operatorname {red} _{1}(\mathrm {lcm} ,f)\\&={\frac {1}{\operatorname {lc} (f)}}\,{\frac {\operatorname {lm} (g)}{\mathrm {gcd} }}\,f-{\frac {1}{\operatorname {lc} (g)}}\,{\frac {\operatorname {lm} (f)}{\mathrm {gcd} }}\,g,\end{aligned}}}$

где lcm и gcd обозначают соответственно наименьшее общее кратное и наибольший общий делитель старших мономов f и g .

Поскольку мономы, которые можно сократить как с помощью f , так и с помощью g , в точности кратны lcm , можно справиться со всеми случаями неединственности приведения, рассматривая только S -полиномы. Это фундаментальный факт для теории базиса Грёбнера и всех алгоритмов их вычисления.

Определение

Пусть – кольцо многочленов над полем F . В этом разделе мы предполагаем, что допустимый мономиальный порядок зафиксирован. ${\displaystyle R=F[x_{1},\ldots ,x_{n}]}$

Пусть G — конечное множество полиномов из R , порождающее идеал I. Множество G является базисом Грёбнера (относительно мономиального порядка) или, точнее, базисом Грёбнера I , если

1. идеал, порожденный ведущими мономами многочленов из I , равен идеалу, порожденному ведущими мономами из G ,

или, что то же самое,

2. старший моном каждого многочлена из I кратен старшему моному некоторого многочлена из G .

Существует множество характеризующих свойств, каждое из которых можно рассматривать как эквивалентное определение базисов Грёбнера. Для краткости в следующем списке обозначение «одно слово/другое слово» означает, что можно взять либо «одно слово», либо «другое слово» за наличие двух разных характеристик базисов Грёбнера. Все следующие утверждения являются характеризациями базисов Грёбнера:

3. многочлен f находится в I тогда и только тогда, когда некоторая/каждая полная редукция/редукция f с помощью G дает нулевой полином;
4. для каждого S -полинома s элементов G некоторое/каждое полное сокращение/редукция s с помощью G дает ноль;
5. все полные сокращения элемента R дают один и тот же результат;
6. мономы, неприводимые G, образуют базис F -векторного пространства ${\displaystyle R/I.}$

С учетом приведенного выше определения это дает 12 характеристик базисов Грёбнера. Тот факт, что возможно так много характеризаций, делает базисы Грёбнера очень полезными. Например, условие 3 предоставляет алгоритм проверки идеального членства ; условие 4 обеспечивает алгоритм проверки того, является ли набор полиномов базисом Грёбнера, и составляет основу алгоритма Бухбергера для вычисления базисов Грёбнера; Условия 5 и 6 позволяют выполнять вычисления способом, очень похожим на модульную арифметику . ${\displaystyle R/I}$

Существование базисов Грёбнера. Для любого допустимого мономиального порядка и любого конечного множества G многочленов существует базис Грёбнера, содержащий G и порождающий тот же идеал. Более того, такой базис Грёбнера можно вычислить с помощью алгоритма Бухбергера .

Этот алгоритм использует условие 4 и действует примерно следующим образом: добавляет к G все ненулевые результаты полной редукции G S -полинома из двух элементов G ; повторяйте эту операцию с включенными новыми элементами G до тех пор, пока в конечном итоге все сокращения не дадут ноль. Алгоритм всегда завершается из-за леммы Диксона или из-за того, что кольца многочленов нётеровы ( базисная теорема Гильберта ). Условие 4 гарантирует, что результат является базисом Грёбнера.

Уменьшенные основания Грёбнера

Базис Грёбнера - этоминимальна , если все ведущие мономы ее элементов неприводимы к остальным элементам базиса. Учитывая базис Грёбнера идеалаI, можно получить минимальный базис ГрёбнераI, удалив многочлены, ведущие мономы которых кратны старшему моному другого элемента базиса Грёбнера. Однако если два многочлена базиса имеют один и тот же ведущий моном, удалить нужно только один. Итак, каждый базис Грёбнера содержит в качестве подмножества минимальный базис Грёбнера.

Все минимальные базы Грёбнера данного идеала (при фиксированном мономиальном порядке) имеют одинаковое количество элементов и одинаковые ведущие мономы, а неминимальные базы Грёбнера имеют больше элементов, чем минимальные.

Базис Грёбнера - этоуменьшен , если каждый многочлен в нем неприводим к другим элементам базиса и имеет1в качестве старшего коэффициента. Итак, каждый приведенный базис Грёбнера минимален, но минимальный базис Грёбнера не обязательно редуцировать.

Учитывая базис Грёбнера идеала I , можно получить уменьшенный базис Грёбнера I , сначала удалив полиномы, которые можно привести с помощью других элементов базиса (для получения минимального базиса); затем замена каждого элемента базиса результатом полной редукции другими элементами базиса; и, наконец, делением каждого элемента базиса на его старший коэффициент.

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

Иногда приведенные базисы Грёбнера определяются без условия на старшие коэффициенты. В этом случае единственность приведенных базисов Грёбнера справедлива лишь с точностью до умножения многочленов на ненулевую константу.

При работе с многочленами над полем рациональных чисел полезно работать только с многочленами с целыми коэффициентами. В этом случае условие о старших коэффициентах при определении приведенного базиса можно заменить условием, что все элементы базиса являются примитивными многочленами с целыми коэффициентами, с положительными старшими коэффициентами. Это восстанавливает уникальность приведенных баз. ${\displaystyle \mathbb {Q} }$

В большинстве реализаций вычислений по базису Грёбнера выходные базы Грёбнера всегда сокращаются. ^{[ нужна цитата ]}

Особые случаи

Для любого мономиального порядка пустой набор многочленов является единственным базисом Грёбнера нулевого идеала .

Для любого мономиального порядка набор многочленов, содержащий ненулевую константу, является базисом Грёбнера единичного идеала (всего кольца полиномов). И наоборот, каждый базис Грёбнера единичного идеала содержит ненулевую константу. Приведенный базис Грёбнера единицы формируется одним полиномом 1 .

В случае полиномов от одной переменной существует единственный допустимый мономиальный порядок — порядок по степени. Минимальные базисы Грёбнера — это синглтоны , состоящие из одного многочлена. Приведенные базисы Грёбнера представляют собой монические полиномы .

Пример и контрпример

Нули образуют красную параболу; нули образуют три синие вертикальные линии. Их пересечение состоит из трёх точек. ${\displaystyle f}$ ${\displaystyle g}$

Пусть – кольцо двумерных многочленов с рациональными коэффициентами и рассмотрим идеал, порожденный многочленами ${\displaystyle R=\mathbb {Q} [x,y]}$ ${\displaystyle I=\langle f,g\rangle }$

${\displaystyle f=x^{2}-y}$,

${\displaystyle g=x^{3}-x}$.

Уменьшая g на f , можно получить новый многочлен k такой, что ${\displaystyle I=\langle f,k\rangle :}$

${\displaystyle k=g-xf=xy-x.}$

Ни одно из f и k не может быть сокращено другим, но xk можно сократить с помощью f , что дает еще один полином от I :

${\displaystyle h=xk-(y-1)f=y^{2}-y.}$

При лексикографическом упорядочении имеем ${\displaystyle x>y}$

lt( ж ) = х ²

lt( k ) = xy

lt( час ) = y ²

Поскольку f , k и h принадлежат I , и ни один из них не редуцируем другим, ни один из них не является базисом Грёбнера I . ${\displaystyle \{f,k\},}$ ${\displaystyle \{f,h\},}$ ${\displaystyle \{h,k\}}$

С другой стороны, { f , k , h } является базисом Грёбнера I , поскольку S-полиномы

${\displaystyle {\begin{aligned}yf-xk&=y(x^{2}-y)-x(xy-x)=f-h\\yk-xh&=y(xy-x)-x(y^{2}-y)=0\\y^{2}f-x^{2}h&=y(yf-xk)+x(yk-xh)\end{aligned}}}$

может быть сведено к нулю с помощью f , k и h .

Метод, который использовался здесь для нахождения h и k и доказательства того, что { f , k , h } является базисом Грёбнера, является прямым применением алгоритма Бухбергера . Таким образом, его можно механически применить к любому подобному примеру, хотя, как правило, необходимо учитывать множество полиномов и S-полиномов, а вычисления, как правило, слишком велики, чтобы их можно было выполнить без компьютера.

Свойства и приложения базисов Грёбнера.

Если не оговорено явно, все последующие результаты из ^[3] верны для любого мономиального порядка (определения различных порядков, упомянутых ниже, см. в этой статье).

Распространено заблуждение, что для некоторых из этих результатов необходим лексикографический порядок. Напротив, лексикографический порядок почти всегда сложнее всего вычислить, и его использование делает непрактичными многие вычисления, которые относительно просты с помощью градуированного обратного лексикографического порядка (grevlex) или, когда необходимо исключение, порядка исключения (lexdeg ), который ограничивается grevlex для каждого блока переменных.

Равенство идеалов

Приведенные базисы Грёбнера уникальны для любого данного идеала и любого мономиального порядка. Таким образом, два идеала равны тогда и только тогда, когда они имеют один и тот же (редуцированный) базис Грёбнера (обычно программное обеспечение для базиса Грёбнера всегда создаёт уменьшенные базисы Грёбнера).

Членство и включение идеалов

Сокращение многочлена f базисом Грёбнера G идеала I дает 0 тогда и только тогда, когда f находится в I . Это позволяет проверить принадлежность элемента идеалу. Другой метод состоит в проверке того, что базис Грёбнера группы G ∪{ f } равен G .

Чтобы проверить, содержится ли идеал I, порожденный f ₁ , ..., f _k, в идеале J , достаточно проверить, что каждый f _I находится в J . Можно также проверить равенство приведенных базисов Грёбнера J и J ∪ { f ₁ , ..., f _k } .

Решения системы алгебраических уравнений

Любой набор полиномов можно рассматривать как систему полиномиальных уравнений , приравнивая полиномы нулю. Множество решений такой системы зависит только от порожденного идеала и поэтому не меняется при замене данного порождающего набора базисом Грёбнера при любом упорядочении порожденного идеала. Такое решение с координатами в алгебраически замкнутом поле , содержащем коэффициенты многочленов, называется нулем идеала . В обычном случае рациональных коэффициентов это алгебраически замкнутое поле выбирается в качестве комплексного поля .

Идеал не имеет нуля (система уравнений несовместна ) тогда и только тогда, когда 1 принадлежит идеалу (это Nullstellensatz Гильберта ), или, что то же самое, если его базис Грёбнера (для любого мономиального порядка) содержит 1, или, также, если соответствующий приведенный базис Грёбнера равен [1].

Учитывая базис Грёбнера G идеала I , он имеет только конечное число нулей тогда и только тогда, когда для каждой переменной x G содержит многочлен со старшим мономом, являющимся степенью x (без какой-либо другой переменной, появляющейся в ведущий термин). Если это так, то количество нулей, подсчитанных с кратностью, равно количеству мономов, не кратных ни одному ведущему моному группы G . Это число называется степенью идеала.

Когда число нулей конечно, базис Грёбнера для лексикографического мономиального упорядочения теоретически обеспечивает решение: первая координата решения является корнем наибольшего общего делителя полиномов базиса, которые зависят только от первой переменной. После подстановки этого корня в базис вторая координата этого решения является корнем наибольшего общего делителя полученных многочленов, зависящих только от второй переменной, и так далее. Этот процесс решения является только теоретическим, поскольку он предполагает вычисление НОД и поиск корней многочленов с приблизительными коэффициентами, что практически невозможно из-за числовой нестабильности. Поэтому были разработаны другие методы решения полиномиальных систем с помощью базисов Грёбнера ( подробнее см. В Системе полиномиальных уравнений ).

Размерность, степень и ряд Гильберта

Размерность идеала I в кольце полиномов R равна размерности Крулля кольца R / I и равна размерности алгебраического множества нулей I. Он также равен числу гиперплоскостей общего положения , которые необходимы для пересечения с алгебраическим множеством, состоящим из конечного числа точек. Степень идеала и связанного с ним алгебраического множества — это количество точек этого конечного пересечения, подсчитанное с кратностью . В частности, степень гиперповерхности равна степени ее полинома определения.

И степень, и размерность зависят только от набора ведущих мономов базиса Грёбнера идеала при любом мономиальном порядке.

Размерность — это максимальный размер подмножества S переменных такого, что не существует старшего монома, зависящего только от переменных из S . Таким образом, если идеал имеет размерность 0, то для каждой переменной x существует старший моном в базисе Грёбнера, являющийся степенью x .

И размерность, и степень могут быть выведены из ряда Гильберта идеала, который представляет собой ряд , где - количество мономов степени i , которые не кратны любому ведущему моному в базисе Грёбнера. Ряд Гильберта можно сложить в рациональную дробь. ${\textstyle \sum _{i=0}^{\infty }d_{i}t^{i}}$ ${\displaystyle d_{i}}$

${\displaystyle \sum _{i=0}^{\infty }d_{i}t^{i}={\frac {P(t)}{(1-t)^{d}}},}$

где d — размерность идеала и — полином, являющийся степенью идеала. ${\displaystyle P(t)}$ ${\displaystyle P(1)}$

Хотя размерность и степень не зависят от выбора мономиального порядка, ряд Гильберта и полином изменяются при изменении мономиального порядка. ${\displaystyle P(t)}$

Большинство систем компьютерной алгебры , которые предоставляют функции для вычисления базисов Грёбнера, также предоставляют функции для вычисления ряда Гильберта, а, следовательно, и размерности и степени.

Устранение

Вычисление базисов Грёбнера для мономиального порядка исключения позволяет использовать вычислительную теорию исключения . Это основано на следующей теореме.

Рассмотрим кольцо полиномов , в котором переменные разбиты на два подмножества X и Y. Давайте также выберем мономиальный порядок исключения, «исключающий» X , то есть мономиальный порядок, при котором два монома сравниваются путем сравнения сначала X -частей, а, только в случае равенства, рассмотрения Y -частей. Это означает, что моном, содержащий X -переменную, больше, чем любой моном, не зависящий от X . Если G является базисом Грёбнера идеала I для этого мономиального порядка, то он является базисом Грёбнера (этот идеал часто называют идеалом исключения ). Более того, состоит в точности из полиномов G , старшие члены которых принадлежат K [ Y ] (это очень упрощает вычисление , поскольку необходимо проверять только старшие мономы). ${\displaystyle K[x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}]=K[X,Y],}$ ${\displaystyle G\cap K[Y]}$ ${\displaystyle I\cap K[Y]}$ ${\displaystyle G\cap K[Y]}$ ${\displaystyle G\cap K[Y]}$

Это свойство исключения имеет множество применений, некоторые из которых описаны в следующих разделах.

Другое применение в алгебраической геометрии заключается в том, что исключение реализует геометрическую операцию проекции аффинного алгебраического множества в подпространство окружающего пространства: в приведенных выше обозначениях ( замыкание Зарисского ) проекция алгебраического множества, определенного идеалом I в Y -подпространство определяется идеалом ${\displaystyle I\cap K[Y].}$

Лексикографическое упорядочение, такое как порядок исключения для каждого раздела. Таким образом, базис Грёбнера для этого упорядочения несет гораздо больше информации, чем обычно необходимо. Это может объяснить, почему базы Грёбнера для лексикографического упорядочения обычно труднее всего вычислить. ${\displaystyle x_{1}>\cdots >x_{n}}$ ${\displaystyle \{x_{1},\ldots ,x_{k}\},\{x_{k+1},\ldots ,x_{n}\}.}$

Пересекающиеся идеалы

Если I и J — два идеала, порожденные соответственно { f ₁ , ..., f _m } и { g ₁ , ..., g _k }, то одно вычисление базиса Грёбнера дает базис Грёбнера их пересечения I ∩ J . Для этого вводится новая неопределенная t и используется порядок исключения, так что первый блок содержит только t , а другой блок содержит все остальные переменные (это означает, что моном, содержащий t , больше, чем любой моном, который не содержит т ). При таком мономиальном порядке базис Грёбнера I ∩ J состоит из полиномов, не содержащих t , в базисе Грёбнера идеала

${\displaystyle K=\langle tf_{1},\ldots ,tf_{m},(1-t)g_{1},\ldots ,(1-t)g_{k}\rangle .}$

Другими словами, I  ∩  J получается удалением t из K . Это можно доказать, заметив, что идеал K состоит из полиномов таких, что и . Такой полином не зависит от t тогда и только тогда, когда a = b , что означает, что ${\displaystyle (a-b)t+b}$ ${\displaystyle a\in I}$ ${\displaystyle b\in J}$ ${\displaystyle b\in I\cap J.}$

Имплицитизация рациональной кривой

Рациональная кривая — это алгебраическая кривая , имеющая систему параметрических уравнений вида

${\displaystyle {\begin{aligned}x_{1}&={\frac {f_{1}(t)}{g_{1}(t)}}\\&\;\;\vdots \\x_{n}&={\frac {f_{n}(t)}{g_{n}(t)}},\end{aligned}}}$

где и — одномерные полиномы для 1 ≤ i ≤ n . Можно (и будет) предполагать, что и взаимно просты (у них нет непостоянных общих факторов). ${\displaystyle f_{i}(t)}$ ${\displaystyle g_{i}(t)}$ ${\displaystyle f_{i}(t)}$ ${\displaystyle g_{i}(t)}$

Имплицитизация заключается в вычислении неявных уравнений такой кривой. В случае n = 2, то есть для плоских кривых, это можно вычислить с помощью результирующего . Неявное уравнение представляет собой следующий результат:

${\displaystyle {\text{Res}}_{t}(g_{1}x_{1}-f_{1},g_{2}x_{2}-f_{2}).}$

Исключение с помощью базисов Грёбнера позволяет выполнять неявное определение для любого значения n , просто исключая t в идеале. Если n = 2, результат тот же, что и с результирующим, если отображение инъективно почти для каждого t . В другом случае равнодействующая является степенью результата исключения. ${\displaystyle \langle g_{1}x_{1}-f_{1},\ldots ,g_{n}x_{n}-f_{n}\rangle .}$ ${\displaystyle t\mapsto (x_{1},x_{2})}$

Насыщенность

При моделировании задачи полиномиальными уравнениями часто предполагается, что некоторые величины отличны от нуля, чтобы избежать вырожденных случаев. Например, при работе с треугольниками многие свойства становятся ложными, если треугольник вырождается в отрезок прямой, т. е. длина одной стороны равна сумме длин других сторон. В таких ситуациях невозможно вывести соответствующую информацию из полиномиальной системы, если не игнорировать вырожденные решения. Точнее, система уравнений определяет алгебраическое множество , которое может иметь несколько неприводимых компонент , причем необходимо удалить те компоненты, на которых условия вырождения всюду равны нулю.

Это достигается путем насыщения уравнений условиями вырождения, что можно сделать с помощью свойства исключения базисов Грёбнера.

Определение насыщенности

Локализация кольца состоит в присоединении к нему формальных обратных некоторых элементов. В этом разделе рассматривается только случай одного элемента или, что то же самое, конечного числа элементов (присоединение обратных значений нескольких элементов эквивалентно присоединению обратного их произведения). Локализация кольца R элементом f — это кольцо , где t — новая неопределенная величина, представляющая обратную величину f . Локализация идеала I кольца R является идеалом Когда R — кольцо многочленов, вычисления в нем неэффективны из-за необходимости управлять знаменателями. Поэтому локализацию обычно заменяют операцией насыщения . ${\displaystyle R_{f}=R[t]/(1-ft),}$ ${\displaystyle R_{f}I}$ ${\displaystyle I_{f}.}$ ${\displaystyle R_{f}}$

The насыщение поfидеалаIвRявляется обратным образомпри каноническом отображении изRв.Это идеал,состоящий из всех элементовR, произведение которых с некоторой степеньюfпринадлежитI. ${\displaystyle R_{f}I}$ ${\displaystyle R_{f}.}$ ${\displaystyle I:f^{\infty }=\{g\in R\mid (\exists k\in \mathbb {N} )f^{k}g\in I\}}$

Если J - идеал, порожденный I и 1− ft в R [ t ], то из этого следует, что, если R - кольцо многочленов, вычисление базиса Грёбнера, исключающее t , дает базис Грёбнера насыщения идеала многочленом. ${\displaystyle I:f^{\infty }=J\cap R.}$

Важным свойством насыщения, обеспечивающим удаление из алгебраического множества, определяемого идеалом I , неприводимых компонент , на которых многочлен f равен нулю, является следующее: первичное разложение состоит из компонент первичного разложения I. которые не содержат никакой степени f . ${\displaystyle I:f^{\infty }}$

Расчет насыщения

Базис Грёбнера насыщения f полиномиального идеала, порожденного конечным набором многочленов F , может быть получен путем исключения t , то есть путем сохранения полиномов независимыми от t в базисе Грёбнера для порядка исключения, исключающего t . ${\displaystyle F\cup \{1-tf\},}$ ${\displaystyle F\cup \{1-tf\}}$

Вместо использования F можно также начать с базиса Грёбнера F. Какой метод наиболее эффективен, зависит от проблемы. Однако, если насыщение не удаляет какой-либо компонент, то есть если идеал равен своему насыщенному идеалу, сначала вычисление базиса Грёбнера F обычно происходит быстрее. С другой стороны, если при насыщении удаляются некоторые компоненты, прямое вычисление может оказаться значительно быстрее.

Если кто-то хочет провести насыщение по отношению к нескольким полиномам или по отношению к одному многочлену, который является произведением, есть три способа действовать, которые дают один и тот же результат, но могут иметь очень разное время вычислений (это зависит от проблемы, какой из них является наиболее эффективным). ). ${\displaystyle f_{1},\ldots ,f_{k}}$ ${\displaystyle f=f_{1}\cdots f_{k},}$

• Насыщение за одно вычисление в базисе Грёбнера. ${\displaystyle f=f_{1}\cdots f_{k}}$
• Насыщение, затем насыщение результата и так далее. ${\displaystyle f_{1},}$ ${\displaystyle f_{2},}$
• Добавление полиномов к F или к его базису Грёбнера и исключение их за одно вычисление базиса Грёбнера. ${\displaystyle 1-t_{1}f_{1},\ldots ,1-t_{k}f_{k},}$ ${\displaystyle t_{i}}$

Эффективный Nullstellensatz

Nullstellensatz Гильберта имеет две версии. Первый утверждает, что набор многочленов не имеет общих нулей над алгебраическим замыканием поля коэффициентов тогда и только тогда, когда 1 принадлежит порожденному идеалу. Это легко проверить с помощью вычисления базиса Грёбнера, потому что 1 принадлежит идеалу тогда и только тогда, когда 1 принадлежит базису Грёбнера идеала для любого мономиального порядка.

Вторая версия утверждает, что множество общих нулей (в алгебраическом замыкании поля коэффициентов) идеала содержится в гиперповерхности нулей многочлена f тогда и только тогда, когда степень f принадлежит идеалу . Это можно проверить, насытив идеал f ; на самом деле, степень f принадлежит идеалу тогда и только тогда, когда насыщение f обеспечивает базис Грёбнера, содержащий 1.

Имплицитизация в более высоком измерении

По определению аффинное рациональное многообразие размерности k можно описать параметрическими уравнениями вида

${\displaystyle {\begin{aligned}x_{1}&={\frac {p_{1}}{p_{0}}}\\&\;\;\vdots \\x_{n}&={\frac {p_{n}}{p_{0}}},\end{aligned}}}$

где – n +1 полиномов от k переменных (параметры параметризации). Таким образом, параметры и координаты точек многообразия являются нулями идеала ${\displaystyle p_{0},\ldots ,p_{n}}$ ${\displaystyle t_{1},\ldots ,t_{k}.}$ ${\displaystyle t_{1},\ldots ,t_{k}}$ ${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle I=\left\langle p_{0}x_{1}-p_{1},\ldots ,p_{0}x_{n}-p_{n}\right\rangle .}$

Можно предположить, что достаточно исключить параметры, чтобы получить неявные уравнения многообразия, как это было сделано в случае кривых. К сожалению, это не всегда так. Если у них есть общий нуль (иногда называемый базовой точкой ), каждый неприводимый компонент непустого алгебраического набора, определяемого I, является неприводимым компонентом алгебраического набора, определенного I. Отсюда следует, что в этом случае прямое исключение дает пустой набор многочленов. ${\displaystyle p_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle t_{i}}$

Следовательно, если k > 1, необходимы два базисных вычисления Грёбнера, чтобы импликировать:

1. Насыщайте , чтобы получить базис Грёбнера ${\displaystyle I}$ ${\displaystyle p_{0}}$ ${\displaystyle G}$
2. Устраните из, чтобы получить базис Грёбнера идеала (неявных уравнений) многообразия. ${\displaystyle t_{i}}$ ${\displaystyle G}$

Алгоритмы и реализации

Алгоритм Бухбергера — старейший алгоритм вычисления базисов Грёбнера. Она была разработана Бруно Бухбергером вместе с базисной теорией Грёбнера. Его несложно реализовать, но вскоре выяснилось, что необработанные реализации могут решить только тривиальные проблемы. Основными проблемами являются следующие:

1. Даже если результирующий базис Грёбнера мал, промежуточные полиномы могут быть огромными. В результате большая часть вычислительного времени может быть потрачена на управление памятью . Таким образом, специализированные алгоритмы управления памятью могут стать фундаментальной частью эффективной реализации.
2. Целые числа , возникающие во время вычислений, могут быть достаточно большими, чтобы сделать полезными быстрые алгоритмы умножения и многомодульную арифметику . По этой причине большинство оптимизированных реализаций используют GMPlibrary . Кроме того, в оптимизированных реализациях используются модульная арифметика , китайская теорема об остатках и лифтинг Гензеля.
3. Выбор S-полиномов для приведения и полиномов, используемых для их приведения, посвящен эвристике . Как и во многих вычислительных задачах, эвристика не может обнаружить большинство скрытых упрощений, и если избегать эвристического выбора, можно добиться значительного повышения эффективности алгоритма.
4. В большинстве случаев большинство вычисляемых S-полиномов сводятся к нулю; то есть большая часть вычислительного времени тратится на вычисление нуля.
5. Мономиальный порядок , который чаще всего необходим для приложений (чисто лексикографический), не является тем порядком, который приводит к самым простым вычислениям, обычно это порядок degrevlex .

Для решения 3. до введения алгоритмов F4 и F5 Жаном -Шарлем Фожером было предложено множество улучшений, вариантов и эвристик . Поскольку эти алгоритмы разработаны для целых коэффициентов или с коэффициентами в целых числах по модулю простого числа , алгоритм Бухбергера остается полезным для более общих коэффициентов.

Грубо говоря, алгоритм F4 решает 3. путем замены множества S-полиномиальных сокращений на сокращение строк одной большой матрицы, для чего можно использовать передовые методы линейной алгебры . Это частично решает проблему 4., так как приведения к нулю в алгоритме Бухбергера соответствуют отношениям между строками сокращаемой матрицы, а нулевые строки приведенной матрицы соответствуют базису векторного пространства этих отношений.

Алгоритм F5 улучшает F4, вводя критерий, позволяющий уменьшить размер сокращаемых матриц. Этот критерий почти оптимален, поскольку приводимые матрицы имеют полный ранг в достаточно регулярных случаях (в частности, когда входные полиномы образуют регулярную последовательность ). Настройка F5 для общего использования сложна, поскольку его характеристики зависят от порядка входных полиномов и баланса между приращением степени рабочего полинома и количеством рассматриваемых входных полиномов. На сегодняшний день (2022 г.) не существует распределенной реализации, которая была бы значительно более эффективной, чем F4, но над модульными целыми числами F5 успешно использовался для решения нескольких криптографических задач ; например, за нарушение задачи HFE .

Проблема 5. была решена открытием алгоритмов преобразования базиса, которые начинаются с базиса Грёбнера для одного мономиального порядка для вычисления базиса Грёбнера для другого мономиального порядка. Алгоритм FGLM — это такой алгоритм преобразования базиса, который работает только в нульмерном случае (когда многочлены имеют конечное число комплексных общих нулей) и имеет полиномиальную сложность по числу общих нулей. Алгоритм преобразования базиса, который работает в общем случае, — это алгоритм обхода Грёбнера . ^[4] В своей первоначальной форме FGLM может быть решающим шагом для решения систем полиномиальных уравнений, поскольку FGML не учитывает разреженность задействованных матриц . Это было исправлено введением разреженных алгоритмов FGLM . ^[5]

Большинство систем компьютерной алгебры общего назначения имеют реализации одного или нескольких алгоритмов для базисов Грёбнера, часто также встроенных в другие функции, например, для решения систем полиномиальных уравнений или для упрощения тригонометрических функций; так обстоит дело, например, с CoCoA , GAP , Macaulay 2 , Magma , Maple , Mathematica , SINGULAR , SageMath и SymPy . Когда доступна F4, она обычно намного эффективнее алгоритма Бухбергера. Методы реализации и варианты алгоритмов не всегда документируются, хотя они могут существенно повлиять на эффективность.

По состоянию на 2022 год ^[update]самыми быстрыми реализациями F4 и (sparse)-FGLM являются реализации библиотеки Msolve . ^[6] Помимо алгоритмов Грёбнера, Msolve содержит быстрые алгоритмы изоляции вещественных корней и объединяет все эти функции в алгоритм для вещественных решений систем полиномиальных уравнений , который значительно превосходит другие программы для этой задачи (Maple и Magma). ^[6] Msolve доступен на GitHub и взаимодействует с Julia , Maple и SageMath; это означает, что Msolve можно использовать непосредственно из этих программных сред.

Сложность

Сложность вычислений в базисе Грёбнера обычно оценивается с точки зрения количества n переменных и максимальной степени d входных полиномов.

В худшем случае основным параметром сложности является максимальная степень элементов результирующего приведенного базиса Грёбнера. Точнее, если базис Грёбнера содержит элемент большой степени D , этот элемент может содержать ненулевые члены, вычисление которых требует времени С другой стороны, если все многочлены в приведенном базисе Грёбнера однородный идеал имеют степень не более D базис Грёбнера может быть вычислен с помощью линейной алгебры в векторном пространстве полиномов степени меньше 2 D , которое имеет размерность. Итак, сложность этого вычисления равна ${\displaystyle \Omega (D^{n})}$ ${\displaystyle \Omega (D^{n})>D^{\Omega (n)}.}$ ${\displaystyle O(D^{n}).}$ ${\displaystyle O(D^{n})^{O(1)}=D^{O(n)}.}$

Наихудшая сложность вычисления базиса Грёбнера является дважды экспоненциальной по n . Точнее, сложность сверху ограничена полиномом в Используя небольшие обозначения o , поэтому она ограничена С другой стороны, были приведены примеры приведенных базисов Грёбнера, содержащих полиномы степени или содержащие элементы. Поскольку каждый алгоритм вычисления базиса Грёбнера должен записывать свой результат, это обеспечивает нижнюю оценку сложности. ${\textstyle d^{2^{n}}.}$ ${\textstyle d^{2^{n+o(n)}}.}$ ${\textstyle d^{2^{\Omega (n)}},}$ ${\textstyle d^{2^{\Omega (n)}}}$

Базис Грёбнера EXPSPACE-полный . ^[7]

Обобщения

Концепция и алгоритмы базисов Грёбнера обобщены на подмодули свободных модулей над кольцом полиномов. Фактически, если L — свободный модуль над кольцом R , то можно рассматривать прямую сумму как кольцо, определив произведение двух элементов L равным 0 . Это кольцо можно отождествить с , где – базис L . Это позволяет отождествить подмодуль L , порожденный с идеалом, порожденным и произведениями , . Если R — кольцо полиномов, то это сводит теорию и алгоритмы базисов Грёбнера модулей к теории и алгоритмам базисов Грёбнера идеалов. ${\displaystyle R\oplus L}$ ${\displaystyle R[e_{1},\ldots ,e_{l}]/\left\langle \{e_{i}e_{j}|1\leq i\leq j\leq l\}\right\rangle }$ ${\displaystyle e_{1},\ldots ,e_{l}}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle R[e_{1},\ldots ,e_{l}]}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle e_{i}e_{j}}$ ${\displaystyle 1\leq i\leq j\leq l}$

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

Области применения

Коды, исправляющие ошибки

Базис Грёбнера был применен в теории кодов, исправляющих ошибки, для алгебраического декодирования. Используя базисные вычисления Грёбнера для различных форм уравнений, исправляющих ошибки, были разработаны методы декодирования для исправления ошибок циклических кодов, ^[8] кодов аффинного многообразия, ^[9] алгебро-геометрических кодов и даже общих линейных блочных кодов. ^[10] Применение базиса Грёбнера в алгебраическом декодировании до сих пор остается областью исследований теории канального кодирования.

Смотрите также

• Основа Грейвера
• Джанет базис
• Регулярные цепочки , альтернативный способ представления алгебраических множеств

Рекомендации

1. Лазард, Дэниел (1983). «Базисы Грёбнера, гауссово исключение и разрешение систем алгебраических уравнений». Компьютерная алгебра . Конспекты лекций по информатике. Том. 162. стр. 146–156. дои : 10.1007/3-540-12868-9_99. ISBN 978-3-540-12868-7.
2. Реншух, Бодо; Ролофф, Хартмут; Распутин Георгий Григорьевич; Абрамсон, Майкл (июнь 2003 г.). «Вклад в конструктивную полиномиальную теорию идеала XXIII: забытые работы ленинградского математика Н. М. Гюнтера по полиномиальной теории идеала» (PDF) . СИГСАМ Бык . 37 (2): 35–48. дои : 10.1145/944567.944569. S2CID  1819694.
3. Кокс, Дэвид А .; Литтл, Джон; О'Ши, Донал (1997). Идеалы, разновидности и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру . Спрингер. ISBN 0-387-94680-2.
4. Коллар, Стефан; Калькбренер, Майкл; Молл, Дэниел (1997). «Преобразование оснований с помощью прогулки Грёбнера». Журнал символических вычислений . Эльзевир. 24 (3–4): 465–469. дои : 10.1006/jsco.1996.0145 .
5. Фожер, Жан-Шарль ; Чэньци, Моу (2017). «Разреженные алгоритмы FGLM». Журнал символических вычислений . Эльзевир. 80 : 538–569. arXiv : 1304.1238 . дои : 10.1016/j.jsc.2016.07.025 . S2CID  149627.
6. Бертомье \first1=Жереми; Эдер, Кристиан; Сейфей Эль Дин, Мохав (2021). Msolve: библиотека для решения полиномиальных систем. Международный симпозиум по символьным и алгебраическим вычислениям 2021 года. 46-й Международный симпозиум по символьным и алгебраическим вычислениям. Россия, Санкт-Петербург. arXiv : 2104.03572 . дои : 10.1145/3452143.3465545.{{cite conference}}: CS1 maint: numeric names: authors list (link)
7. Майр, Эрнст В. (сентябрь 1997 г.), «Некоторые результаты по сложности для полиномиальных идеалов», Journal of Complexity , 13 (3): 303–325, doi : 10.1006/jcom.1997.0447
8. Чен, X.; Рид, И.С.; Хеллесет, Т.; Труонг, ТК (1994). «Использование баз Грёбнера для декодирования двоичных циклических кодов до истинного минимального расстояния». Транзакции IEEE по теории информации . 40 (5): 1654–61. дои : 10.1109/18.333885.
9. Фицджеральд, Дж.; Лакс, РФ (1998). «Декодирование аффинных кодов разновидностей с использованием базисов Грёбнера». Проекты, коды и криптография . 13 (2): 147–158. дои : 10.1023/А: 1008274212057. S2CID  2515114.
10. Булыгин, С.; Пелликаан, Р. (2009). «Декодирование линейных кодов с исправлением ошибок на расстоянии до половины минимального расстояния с помощью баз Грёбнера». Базы Грёбнера, кодирование и криптография . Спрингер . стр. 361–5. ISBN 978-3-540-93805-7.

дальнейшее чтение

• Адамс, Уильям В.; Лустаунау, Филипп (1994). Введение в базисы Грёбнера . Аспирантура по математике . Том. 3. Американское математическое общество . ISBN 0-8218-3804-0.
• Ли, Хуэйши (2011). Базисы Грёбнера в теории колец . Всемирная научная . ISBN 978-981-4365-13-0.
• Беккер, Томас; Вайспфеннинг, Волкер (1998). Базисы Грёбнера: вычислительный подход к коммутативной алгебре . Тексты для аспирантов по математике. Том. 141. Спрингер. ISBN 0-387-97971-9.
• Бухбергер, Бруно (1965). Алгоритм поиска базисных элементов кольца классов вычетов нульмерного полиномиального идеала (PDF) (доктор философии). Университет Инсбрука. — (2006). Перевод Абрамсона М. «Докторская диссертация Бруно Бухбергера, 1965 год: Алгоритм поиска базисных элементов кольца классов вычетов нульмерного полиномиального идеала». Журнал символических вычислений . 41 (3–4): 471–511. дои : 10.1016/j.jsc.2005.09.007 . [Это диссертация Бухбергера, посвященная созданию базисов Грёбнера.]
• Бухбергер, Бруно (1970). «Алгоритмический критерий разрешимости системы алгебраических уравнений» (PDF) . Математические уравнения . 4 : 374–383. дои : 10.1007/BF01844169. S2CID  189834323. (Это журнальная публикация диссертации Бухбергера.) Бурхбергер, Б.; Винклер Ф., ред. (26 февраля 1998 г.). «Алгоритмический критерий разрешимости системы алгебраических уравнений». Базисы и приложения Грёбнера . Серия лекций Лондонского математического общества. Том. 251. Издательство Кембриджского университета. стр. 535–545. ISBN 978-0-521-63298-0.
• Бухбергер, Бруно; Кауэрс, Мануэль (2010). «Базы Грёбнера». Схоларпедия . 5 (10): 7763. Бибкод : 2010SchpJ...5.7763B. doi : 10.4249/scholarpedia.7763 .
• Фрёберг, Ральф (1997). Введение в базисы Грёбнера . Уайли. ISBN 0-471-97442-0.
• Штурмфельс, Бернд (ноябрь 2005 г.). «Что такое… базис Грёбнера?» (PDF) . Уведомления Американского математического общества . 52 (10): 1199–1200, краткое введение.{{cite journal}}: CS1 maint: postscript (link)
• Ширшов, Анатолий И. (1999). «Некоторые алгоритмические проблемы для алгебр Ли» (PDF) . Бюллетень ACM SIGSAM . 33 (2): 3–6. дои : 10.1145/334714.334715. S2CID  37070503.(перевод из Сиб. Матем. Ж. Сибирский математический журнал 3 (1962), 292–296).
• Ашенбреннер, Матиас ; Хиллар, Кристофер (2007). «Конечное порождение симметричных идеалов». Труды Американского математического общества . 359 (11): 5171–92. arXiv : math/0411514 . дои : 10.1090/S0002-9947-07-04116-5 . S2CID  5656701.(о бесконечномерных базисах Грёбнера для колец многочленов от бесконечного числа неопределённых).

Внешние ссылки

• Собственная реализация Фожером его алгоритма F4.
• «Базис Грёбнера», Математическая энциклопедия , EMS Press , 2001 [1994]
• Бухбергер, Б. (2003). «Базы Грёбнера: краткое введение для системных теоретиков» (PDF) . В Морено-Диас, Р.; Бухбергер, Б.; Фрейре, Дж. (ред.). Теория компьютерных систем - EUROCAST 2001: Подборка статей с 8-го международного семинара по теории компьютерных систем. Спрингер. стр. 1–19. ISBN 978-3-540-45654-4.
• Бухбергер, Б.; Заплетал, А. «Библиография по основам Грёбнера».
• Страница сравнения таймингов для программного обеспечения Gröbner Bases
• Профессор Бруно Бухбергер Бруно Бухбергер
• Вайсштейн, Эрик В. «Базис Грёбнера». Математический мир .
• Введение в основу Грёбнера в Scholarpedia