научная статья по теме ОБ ИСПОЛЬЗОВАНИИ КРИТЕРИЕВ БУХБЕРГЕРА В АЛГОРИТМЕ G 2V ВЫЧИСЛЕНИЯ БАЗИСОВ ГРЁБНЕРА Математика

Текст научной статьи на тему «ОБ ИСПОЛЬЗОВАНИИ КРИТЕРИЕВ БУХБЕРГЕРА В АЛГОРИТМЕ G 2V ВЫЧИСЛЕНИЯ БАЗИСОВ ГРЁБНЕРА»

ПРОГРАММИРОВАНИЕ, 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 рублей.

Показать целиком