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

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

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

Информацию о других алгоритмах на основе Грёбнера см. в разделе «Базис Грёбнера § Алгоритмы и реализации» .

Алгоритм

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

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

I

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

I

Г := Ф
каждого f _i , f _j в G обозначим через gi _fi главный член относительно _Для заданного мономиального порядка , а aij _— наименьшее общее gi кратное _и g через _j .
Выберите два многочлена из G и пусть $S ij = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 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 относительно друг друга перед их добавлением. ведущие члены fi _будет и fj _всегда не имеют общих переменных, то Sij _Если . , используем для сокращения только $fi и$ уменьшаться до 0 (если мы $fj)$ поэтому нам вообще не нужно его вычислять

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

Сложность

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

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

,

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

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

d^{2^{\Omega (n)}}

,

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

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

См. также

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

Ссылки

^ Дюбе, Томас В. (1990). «Структура полиномиальных идеалов и базисов Грёбнера». SIAM Journal по вычислительной технике . 19 (4): 750–773. дои : 10.1137/0219053 .
^ Майр, Эрнст В; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов» . Достижения в математике . 46 (3): 305–329. дои : 10.1016/0001-8708(82)90048-2 .

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

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

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

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

[1] Дюбе, Томас В. (1990). «Структура полиномиальных идеалов и базисов Грёбнера». SIAM Journal по вычислительной технике . 19 (4): 750–773. дои : 10.1137/0219053 .

[2] Майр, Эрнст В; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов» . Достижения в математике . 46 (3): 305–329. дои : 10.1016/0001-8708(82)90048-2 .

[ 1 ]

[ 2 ]