ПРОГРАММИРОВАНИЕ, 2013, N° 2, с. 38-50
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ОБ ИСПОЛЬЗОВАНИИ КРИТЕРИЕВ БУХБЕРГЕРА В АЛГОРИТМЕ в2У ВЫЧИСЛЕНИЯ БАЗИСОВ ГРЁБНЕРА
© 2013 г. В, П. Гердт*, А, Хошеми* * Лаборатория информационных технологий Объединенный институт ядерных исследований 14-1980 Дубна, Россия дегШЩтг. ги
**
Исфаханский технологический университет 84-156-83111, Исфахан, Иран
Атгг.На8кетг@сс. Ш. ас. гг Поступила в редакцию 10.07.2012
Как было экспериментально продемонстированно Фожером, его алгоритм Г5 является самым быстрым среди алгоритмов вычисления базисов Грёбнера. Вычислительная эффективность Г 5 обусловлена не только использованием линейной алгебры но и применением авторского критерия Г 5 для выявления бесполезных нулевых редукций. На конференции ЮБАС 2010 Гао, Гуан и Вольны представили С2У, вариант алгоритма Г5, который является более простым по своей структуре, чем
оригинальная версия алгоритма. Однако инкрементальная структура С2У, используемая в алго-
5
2
югцая использовать оба критерия Бухбергера. Для экспериментального анализа вычислительного
эффекта от предложенной модификации мы реализовали модифицированный алгоритм на языке
2
1. ВВЕДЕНИЕ
Метод базисов Грёбнера является универсальным алгоритмическим инструментом решения задач коммутативной алгебры и алгебраической геометрии. Понятие базиса Грёбнера было введено Бухбергером [1] в 1965 г. в его кандидатской диссертации, где он также предложил алгоритм вычисления данного базиса для идеалов в кольцах многочленов многих переменных. Затем
* Исследования, представленные в настоящей работе были начаты во время трёхмесячного пребывания второго автора (А.Х.) в Дубне. Он благодарит первого автора (В.П.Г.) за приглашение поработать в Объединенном институте ядерных исследований и за поддержку. Вклад первого автора был частично поддержан грантами РФФИ 01-01-00200 и 12-07-00294, а также грантом 3810.2010.2 Министерства образования и науки Российской Федерации. Авторы благодарят Веньямина Ализа-деха за полезные обсуждения.
в работе [2] Бухбергер установил два критерия для выявления нулевых и поэтому бесполезных редукций, что сделало метод базисов Грёбнера практическим инструментом решения широкого класса задач не только в теории полиномиальных идеалов и модулей, но и во многих других областях науки и техники [3]. Однако для достаточно больших по числу переменных и степени систем многочленов алгоритм Бухбергера является слишком затратным по времени счёта и требуемой памяти.
В 1983 г. Лазар [4] предложил подход к вычислению базисов Грёбнера, основанный на использовании методов линейной алгебры. Через пять лет Гебауэр и Мёллер [5] нашли более эффективную форму использования критериев Бухбергера, чем в его оригинальной работе. В 1999 г. Фожер [6] разработал эффективный ал-
горитм вычисления базисов Грёбиера, названный им F4. Этот алгоритм использует результаты работ [4, 5] и применяет линейную алгебру разреженных матриц. Он встроен в системы компьютерной алгебры Maple и Magma. Три года спустя, в 2002 г. Фожер предложил [7] новый алгоритм F5, который строит базис Грёбне-ра инкрементальным и, поэтому, зависящим от того, в каком порядке задаются исходные многочлены, образом. Данный алгоритм использует 5
редукций, основанный на добавлении к многочленам дополнительной структурной части, названной сигнатурой. Аре и Хашеми [8] предло-
5
ющуюся на использовании подходящего порядка на сигнатурах, что сделало алгоритм независимым от порядка многочленов на входе алгоритма. Эдер и Перри в [9] упростили некото-
5
числения редуцированного базиса Грёбнера на
каждом шаге алгоритма. Соответствующая мо-
5
зованная в системе Singular, повышает вычислительную эффективность алгоритма. Гао, Гуан и Вольны представили в [10] алгоритм, получивший название G2V и являющийся инкременталь-55
рый можно рассматривать как один из вариан-5
55
на тестовых примерах, вычислительно более эффективным, чем указанные алгоритмы (см. также [11]).
Первый критерий Бухбергера, применимый ко взаимно простым старшим мономам S—многочлена, можно легко задействовать в алгоритме G2V. Мы покажем, что S—многочлен, удовлетворяющий этому критерию может быть
5
не приводит к трудностям при совместном
использовании обоих этих критериев в рамках 2
2
использованию в нём второго критерий Бухбергера. Таким образом, возникает естественный
вопрос: как включить второй критерий Бух-
2
мы дадим ответ на этот вопрос, предложив
соответствующую модификацию алгоритма G2V, позволяющую применять оба критерия Бухбергера. Чтобы увидеть вычислительный эффект от предлагаемой модификации мы реализовали наш алгоритм (а также оригинальный 2
версии на тестовых примерах. Стоит отметить, что в 2004 году Аре [12] использовал критерии Бухбергера для получения оценки на степень базиса Грёбнера при некоторых дополнительных предположениях. Однако он не применял эти критерии для обнаружения бесполезных редукций при выполнении алгоритма F5. В 2008 г. Гэш
предложил [13] модификацию критериев Бух-
5
(см. теоремы 4.2.1, 4.3.1 и 4.3.2 в [13]). Следует подчеркнуть, что главный результат настоящей
работы по совместному использованию второго
5
лированный в виде теоремы 3.1, существенно отличается от результата работы [13]. Кроме того, как Гэш отмечает в разделе 4.4 своей
работы [13], использование его модификации
5
приводит к сколь-нибудь заметному ускорению вычислений, а скорее наоборот приводит к замедлению времени счёта (см. таблицу 1 на стр. 111 работы [13]). В то же время наша модификация приводит к существенному ускорению вычислений, как показывают компьютерные эксперименты раздела 4 настоящей работы.
Теперь мы опишем содержание данной работы. Раздел 2 содержит краткое описание крите-52
5
териями Бухбергера. Здесь же приведена модифицированная версия второго критерия Бухбергера, позволяющая включить его чтобы в алго-2
2
5
В разделе 5 на тестовых примерах сравниваются времена вычислений базисов Грёбнера для реализации на языке Maple нашего алгоритма и
2
заключительные замечания.
52
В этом разделе мы представим теоретические
5
димых понятий и определений (используемых не только в этом, но и в следующем разделе) мы сформулируем основную теорему работы [7], лежащую в основе алгоритма Рб. Затем мы вкратце опишем алгоритм С2У [10].
Пусть К := К[х^...,хп] обозначает кольцо многочленов над полем К от переменных х1,..., хп. Рассмотрим идеал I := (/1,..., /) К
/1,...,Д, й-мерный К-модуль Кк и его канонический базис £!,..., Гк- Модульный моном - это элемент К^ вид а т^, гд е т € К моном. Расширим линейный мономиальный порядок — К
на Кк по следующему правилу:
gfi < Y1
%=i
j > l he = 0, j = l LM(gj) x LM(hj).
Индекс модульного элемента g = ^k=1 gf G Rk, обозначенный как index(g), - это наименьшее целое i, такое что gi = 0. Если index(g) = i0, то LM(gi0 )fi0 - старший модульный моном в g, который мы обозначим через MLM(g). Кроме то-
LM(g)
шего, относительно порядка монома многочлена ^k=1 gifi.
Элемент вида r := (mfi, f) G A = Rk x R, где m - whom, i - натуральное число и f - многочлен, называется маркированным, многочленом. При этом S(r) := mfi называется сигнатурной частью (сигнатурой) r и poly(r) = f - его полиномиальной частью.
Рассмотрим теперь отображение:
^ := Rk ^ R
(gi,...,gfc) ^ gifi +-----+ gkfk.
Маркированный многочлен r = (S(r), poly(r)) называется допустимым если найдется модульный элемент g G Rk, такой что ^(g) = poly(r)
MLM(g) = S(r) рации умножения для маркированных многочленов. Пусть заданы: r = (mfi, f) - маркированный многочлен, и - моном и c G K. Тогда ur := (umfi,uf) and cr := (mfi, cf). Свойство до-
r
няется при указанных умножениях. В алгоритме F5 используется редукция (приведение), которая
также сохраняет свойство допустимости. Более того, в результате редукции сигнатура маркированного многочлена принимает минимально возможное значение.
Для того, чтобы сформулировать основную теорему [7] - критерий Рб - нам потребуется следующие два определения. Второе их этих определений обобщает на маркированные многочлены понятие ^представления в теории базисов Грёбнера (см. [14], стр. 219).
Определение 2.1. Допустимый маркированный многочлен г = (т^, /) называется нормализованным, если т € ЬТ((/г+1,..., /)). Пара допустимых маркированных многочленов (г, 8) называется нормализованной, если иг и гв нормализованы, где и = 1еш(ЬМ(/),ЬМ(д))/ЬМ(/) г = 1еш(ЬМ(/), ЬМ(д))/ЬМ(д) и / = рс1у(г), д = ро1у(в).
Определение 2.2. Пусть заданы, конечное множество Р С А маркированных многочленов и два, т,аких многочлена г, £ € Ас ро1у(г) = / = 0. Говорят,, что
/ = ^ ^гРо1у(Рг)
имеет ¿-представление г по отношению к Р, если для любого р € Р с ро1у(р) = 0 выполнено
ЬМ(^)ЬМ(ро1у(рг)) ^ ЪМ(ро1у(*)), ЬМ(^)5(рг) < 5(г).
Это свойство обозначается г = Ор (¿). Для маркированного многочлена в мы будем использовать запись в = ор (¿) если существует маркированный многочлен £ € А; удовлетворяющий 5(¿') < 5ЬМ(ро1у(£')) - ЬМ(ро1у(£)) и такой, что в = Ор(£').
Пусть задана пара многочленов /, д € К. Тогда Б-многочлен, Яро1у(/, д) от / and д определяется выражением
1еш(ЬМ(/), ЬМ(д)) 1еш(ЬМ(/), ЬМ(д))
-/--ТФ/ \-д.
LT(f)
LT(g)
Рассмотрим два допустимых маркированных многочлена г = (5(г), /) and в = (5(в),д), таких что г5(в) < и5(г) и = 1еш(ЬМ(/), ЬМ(д))/ЬМ(/) и г = 1еш(ЬМ(/),ЬМ(д))/ЬМ(д).
Тогда соответствующий им маркированный ^-многочлен определяется как 8ро1у(г,§) = (г), 8ро1у(/^)).
Фожер показал в [7], что Б-многочлен, составленный из пары маркированных многочленов, которая не является нормализованной, редуцируется к нулю (см. теорему 2.1). Следовательно, такая пара является бесполезной и может не рассматриваться в ходе алгоритма. Это свойство пары и определяется критерием ^б- В той же работе [7] был предложен алгоритм Гб, который строит базис Грёбнера идеала I с применением критерия Г б и является инкрементальным, т.е. строит последовательно базисы Грёбнера идеалов:
{/к} {/k-1, /к} ..., {/ъ ..., /к}.
Критерий Гб имеет форму теоремы, сформулированной и доказанной в [7]:
Теорема 2.1. Пусть и
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.