Алгоритм Бухбергерса - Buchbergers algorithm - Wikipedia

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

Алгоритм

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

Вход Набор полиномов F что порождает я
Выход А Основа Грёбнера грамм за я
  1. грамм := F
  2. Для каждого жя, жj в грамм, обозначим через граммя ведущий срок жя относительно данного порядка, и аij то наименьший общий множитель из граммя и граммj.
  3. Выберите два многочлена от грамм и разреши Sij = (аij / граммя) жя − (аij / граммj) жj (Обратите внимание, что главные термины здесь отменяются по конструкции).
  4. Уменьшать Sij, с алгоритм многомерного деления относительно множества грамм до тех пор, пока результат не станет более заметным. Если результат отличен от нуля, добавьте его к грамм.
  5. Повторяйте шаги 1–4, пока не будут рассмотрены все возможные пары, включая те, которые включают новые полиномы, добавленные на шаге 4.
  6. Выход грамм

Полином Sij обычно называют S-полином, где S относится к вычитание (Бухбергер) или Сизигий (другие). Пара многочленов, с которой он связан, обычно называется критическая пара.

Существует множество способов улучшить этот алгоритм помимо того, что было указано выше. Например, можно сократить все новые элементы F относительно друг друга перед их добавлением. Если ведущие условия жя и жj не имеют общих переменных, тогда Sij буду всегда уменьшить до 0 (если использовать только fя и еj для сокращения), поэтому нам вообще не нужно его вычислять.

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

Сложность

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

,

куда п - количество переменных, а d максимальный общая степень входных полиномов. Теоретически это позволяет использовать линейная алгебра над векторное пространство полиномов степени, ограниченной этим значением, для получения алгоритма сложности.

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

,

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

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

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

Рекомендации

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

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

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

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