Алгоритм Бухбергера - Buchberger's algorithm

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

Алгоритм

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

Сложность

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

,

где 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

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