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

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

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

Для других алгоритмов базиса Грёбнера см. Базис Грёбнера § Алгоритмы и реализации .

Грубая версия этого алгоритма для нахождения базиса идеала I полиномиального кольца R выполняется следующим образом:

Входные данные Набор полиномов F , который генерирует I

Вывод A Базис Грёбнера G для I

1. Г  := Ф
2. Для каждого f _i , f _j из G обозначим через g i _{старший} член f _i относительно данного мономиального порядка , а через a _{ij —} наименьшее общее кратное g i _и g _j .
3. Выберите два многочлена в G и пусть S _ij = ⁠а _ij/ г _я⁠ ф _и − ⁠а _ij/ г _дж⁠ f _j (Обратите внимание, что ведущие члены здесь будут сокращаться по построению) .
4. Уменьшаем S _ij , используя алгоритм многомерного деления относительно множества G до тех пор , пока результат не станет несократимым. Если результат не равен нулю, добавляем его к G .
5. Повторяйте шаги 2–4, пока не будут рассмотрены все возможные пары, включая те, в которых используются новые многочлены, добавленные на шаге 4.
6. Выход G

Полином S _ij обычно называют S -полиномом, где S относится к вычитанию (Бухбергер) или сизигии (другие). Пара полиномов, с которой он связан, обычно называется критической парой .

Существует множество способов улучшить этот алгоритм сверх того, что было указано выше. Например, можно сократить все новые элементы F относительно друг друга перед их добавлением. Если ведущие члены f _i и f _j не имеют общих переменных, то S _ij всегда будет сокращаться до 0 (если мы используем только f _i и f _j для сокращения), поэтому нам вообще не нужно его вычислять.

Алгоритм завершается, поскольку он последовательно увеличивает размер мономиального идеала, порожденного ведущими членами нашего множества F , а лемма Диксона (или теорема Гильберта о базисе ) гарантирует, что любая такая возрастающая цепочка в конечном итоге должна стать постоянной.

Вычислительную сложность алгоритма Бухбергера очень трудно оценить из-за количества выборов, которые могут кардинально изменить время вычислений. Тем не менее, TW Dubé доказал ^[1] , что степени элементов редуцированного базиса Грёбнера всегда ограничены

${\displaystyle 2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}}$,

где n — число переменных, а d — максимальная суммарная степень входных полиномов. Это позволяет, в теории, использовать линейную алгебру над векторным пространством полиномов степени, ограниченной этим значением, для получения алгоритма сложности .${\displaystyle d^{2^{n+o(1)}}}$

С другой стороны, существуют примеры ^[2] , где базис Грёбнера содержит элементы степени

${\displaystyle d^{2^{\Омега (n)}}}$,

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

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

• Алгоритм завершения Кнута-Бендикса
• Алгоритм Куайна–Маккласки – аналогичный алгоритм для булевой алгебры

• Бухбергер, Б. (август 1976 г.). «Теоретическая основа приведения многочленов к каноническим формам». ACM SIGSAM Bulletin . 10 (3). ACM: 19–29. doi :10.1145/1088216.1088219. MR  0463136. S2CID  15179417.
• Дэвид Кокс, Джон Литтл и Дональд О'Ши (1997). Идеалы, многообразия и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру , Springer. ISBN 0-387-94680-2 . 
• Владимир П. Гердт, Юрий А. Блинков (1998). Инволютивные базисы полиномиальных идеалов , Математика и компьютеры в моделировании, 45:519 и далее

• «Алгоритм Бухбергера», Энциклопедия математики , EMS Press , 2001 [1994]
• Алгоритм Бухбергера на Scholarpedia
• Вайсштейн, Эрик В. «Алгоритм Бухбергера». Математический мир .