Алгоритм Бухбергера - Buchberger's algorithm
В вычислительной алгебраической геометрии и вычислительная коммутативная алгебра , алгоритм Бухбергер является методом преобразования данного набора генераторов для полиномиального идеала в основу Грёбнера относительно некоторого одночлена порядка . Его изобрел австрийский математик Бруно Бухбергер . Его можно рассматривать как обобщение алгоритма Евклида для одномерного вычисления НОД и исключения Гаусса для линейных систем .
Алгоритм
Грубая версия этого алгоритма для поиска базиса идеала I кольца многочленов R работает следующим образом:
- Входные данные Набор многочленов F , порождающий I
-
Выведите A базис Грёбнера G для I
- G : = F
- Для каждого е I , ф J в G , обозначим через г я старший член е I относительно данного заказа, и по IJ в наименьшее общее кратное из г я и г J .
- Выберите два многочлена в G и пусть S ij = ( a ij / g i ) f i - ( a ij / g j ) f j (обратите внимание, что главные члены здесь сокращаются по построению) .
- Уменьшайте S ij с помощью алгоритма многомерного деления относительно множества G до тех пор, пока результат не перестанет приводиться к дальнейшему уменьшению. Если результат не равен нулю, добавьте его в G .
- Повторяйте шаги 2–4, пока не будут рассмотрены все возможные пары, включая те, которые включают новые полиномы, добавленные на шаге 4.
- Выход G
Многочлен S ij обычно называют S -полиномом, где S относится к вычитанию (Бухбергера) или сизигии (другие). Пара многочленов, с которой он связан, обычно называется критической парой .
Существует множество способов улучшить этот алгоритм помимо того, что было указано выше. Например, можно уменьшить все новые элементы F относительно друг друга перед их добавлением. Если главные члены f i и f j не имеют общих переменных, то S ij всегда будет уменьшаться до 0 (если мы используем только f i и f j для сокращения), поэтому нам вообще не нужно его вычислять.
Алгоритм завершается, потому что он последовательно увеличивает размер мономиального идеала, порожденного главными членами нашего множества F , и лемма Диксона (или теорема о базисе Гильберта ) гарантирует, что любая такая возрастающая цепочка в конечном итоге должна стать постоянной.
Сложность
Вычислительная сложность алгоритма Бухбергер очень трудно оценить, из числа вариантов , которые могут существенно изменить время вычисления. Тем не менее Т.В. Дубе доказал, что степени элементов редуцированного базиса Грёбнера всегда ограничены
- ,
где n - количество переменных, а d - максимальная суммарная степень входных многочленов. Это позволяет теоретически использовать линейную алгебру над векторным пространством многочленов степени, ограниченной этим значением, для получения алгоритма сложности .
С другой стороны, есть примеры, когда базис Грёбнера содержит элементы степени
- ,
и указанная выше верхняя граница сложности является оптимальной. Тем не менее такие примеры крайне редки.
С момента его открытия было введено множество вариантов Бухбергера для повышения его эффективности. Алгоритмы Фогера 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 .