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

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

Алгоритм

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

Входные данные Набор многочленов F , порождающий I

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

1. G  : = F
2. Для каждого е _I , ф _J в G , обозначим через г _я старший член е _I относительно данного заказа, и по _IJ в наименьшее общее кратное из г _я и г _J .
3. Выберите два многочлена в G и пусть S _ij = ( a _ij / g _i ) f _i - ( a _ij / g _j ) 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 , и лемма Диксона (или теорема о базисе Гильберта ) гарантирует, что любая такая возрастающая цепочка в конечном итоге должна стать постоянной.

Сложность

Вычислительная сложность алгоритма Бухбергер очень трудно оценить, из числа вариантов , которые могут существенно изменить время вычисления. Тем не менее Т.В. Дубе доказал ^[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^{\Omega (n)}}}$,

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

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

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

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

использованная литература

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

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

внешняя ссылка

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