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

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

• 1 Алгоритм
• 2 Сложность
• 3 См. Также
• 4 ссылки
• 5 Дальнейшее чтение
• 6 Внешние ссылки

Грубая версия этого алгоритма для поиска базиса идеала 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, и лемма Диксона (или теорема о базисе Гильберта ) гарантирует, что любая такая возрастающая цепочка в конечном итоге должна стать постоянной.

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

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

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

С другой стороны, есть примеры, когда базис Грёбнера содержит элементы степени

${\ 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.