ПРОГРАММИРОВАНИЕ, 2013, No 2, с. 75-80
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ПАРАЛЛЕЛЬНОЕ МОДУЛЯРНОЕ ВЫЧИСЛЕНИЕ БАЗИСОВ ГРЁБНЕРА И ИНВОЛЮТИВНЫХ БАЗИСОВ *
© 2013 г. Д.А. Янович
Объединенный институт ядерных исследований Лаборатория информационных технологий 141980 Дубна, Россия E-mail: yan@jinr.ru Поступила в редакцию 31.07.2012
Представлен обзор алгоритма и собственная эффективная реализация параллельного вычисления инволютивных базисов и базисов Грёбнера при помощи модулярных операций. Рассмотрены проблемы, возникающие при вычислениях по модулю и восстановления базиса с коэффициентами из Z по его модулярным образам, указаны некоторые способы их избежать.
1. ВВЕДЕНИЕ
1.1. Инволютивные базисы и базисы Грёбнера
Ниже мы будем использовать следующие обозначения:
М = К[ж1,..., хп] кольцо многочленов над полем К нулевой характеристики; /, д, Н, ц, г многочлены из М; а, Ь, с элементы из К; Р, С, Н конечные подмножества из М; (р) Идеал из м порожденный Р; Z>o множество неотрицательных чисел; М = (х^1 ■ ■ ■ хПп | йг е ^>0} - множество моноМ
и, V, ш, в, Ь множество мономов или термов; и, V, Ш конечные подмножества из М; degг(и) степень переменной Жг в и; deg(u) полная степень монома и; >- допустимое мономиальное упорядочение с порядком переменных Ж1 >- ... >- хга;
/) лидирующий терм относительно упорядочения >-;
1т(/) лидирующий моном /;
1т(Р) = (1т(/) | / е Р} множество лидирующих мономов из Р;
1ст(Р) наименьшее общее кратное множества мономов из 1т(Р);
и | V означает, что моном и делит моном V. Определение и алгоритм построения базисов Грёбнера были предложены Б. Бухбергером [1]. Кратко напомним основные понятия.
Определение 1. [1, 2] Пусть заданно допустимое мономиальное упорядочение. Конечное подмножество С = (д-\_, ..., дт} элементов идеала I называется его базисом Грёбнера, если
(1т(д1), ..., 1ш(дт)) = (1т(!)).
Центральным понятием в алгоритме вычисления базиса Грёбнера является Я-полином.
Определение 2. [1, 2] 8-полиномом /, д е К называется комбинация
Вро!у(/,д) = 'Ст('т</); 1т(д)) / -
* Исследования, представленные в работе, были выполнены при частичной поддержке грантов 10-01-00200 и 1207-00294 Российского Фонда Фундаментальных Исследований и гранта 3802.2012.2 Министерства Образования и Науки Российской Федерации.
lt(f ) lcm(lm(f), lm(g))
-д.
Теорема 1. [1, 2] Пусть I - некоторый полиномиальный идеал. Базис G = {gi, ..., gm}
76
ЯНОВИЧ
идеала I является базисом Грёбнера в том и только в том случае, когда для, всех пар г = ] : NormalForm(Spo1y(gi,gj),С) = 0, где NormalForm - нормальная форма полинома ¡2].
Если, некоторым самосогласованным способом запретить деление по некоторым переменным, называемыми немультипликативными и разрешить по другим, называемыми мультипликативным,и, то мы получим сужение операции деления - инволют,ивное деление [3, 4]. Дадим основные определения.
Определение 3. [3, 41 Мы будем говорить, чт,о на, множестве мономов М определено ин-волютивное деление Ь если для любого конечного подмножества и С М и для любого и € и задан, подмоноид Ь(и, и) моноида М; удовлетворяющий следующим условиям:
(a) Из — € Ь(и, и) и V | — следует, V € Ь(и, и);
(b) Из и^ € и ииЬ(и,и)= 0 следует и € vL(v, и) или V € иЬ(и, и);
(c) Из V € и и V € иЬ(и, и) следует Ь^, и) С Ь(и, и);
(й) Из V С и следует Ь(и,и) С Ь(и,У) для, всех и € V.
Элементы Ь(и, и) (и € и) называются мультипликативными для и. Если — € иЬ(и, и) то и называется (Ь-)инволютивным делителем — и обозначается и |ь — . В свою очередь, моном — называется (Ь-)к^тным и.
Определение 4. [3, 41 Множество мономов называется Ь - инволют,иены,м,, если
(Уи € и) (V— € М) ^ € и) [ V | ь и— ].
Используя конструктивное и нётерово деление можно построить инволютивный базис алгоритмическим путем, пополняя частично инволютив-ное множество, в случае используемого автором деления Жане, определяемого следующим образом:
Определение 5. [31 Пусть Ь - деление Жане. Ь-авторедуцированное множество F называется частично инволют,иены,м, до монома V
в допустимом мономиальном упорядочении, У тогда и только тогда, когда выполнено следующее условие:
(V/ € F€ NMь(\m(f), 1ш(^)) (V У 1ш(/) ■ х^[Могша1Еогшь(/ ■ х^ F) = 0],
где Могша1Еогшь означает инволют,ивную нормальную форму, определенную заменой обычного деления на инволют,ивное.
Таким образом, добавив в частичный базис ненулевые инволютивные нормальные формы немультипликативных продолжений множества F, мы получим искомый инволютивный базис.
Связь между инволютивным базисом и базисом Грёбнера определяется следующей теоремой:
Теорема 2. [31 Инволют иены, й, базис, авторедуцированный в смысле обычного деления, является редуцированным, ба,зи,сом, Грёбнера.
1.2. Модулярное вычисление базисов
Ввиду широко известной проблемы разрастания промежуточных коэффициентов при построении базисов Грёбнера и инволютивных базисов, в мире имеется большой интерес к применению модулярных методов, позволяющих ее избежать.
Огромным преимуществом применения модулярных вычислений является естественный параллелизм, за счет слабой связанности подзадач друг с другом обещающий хорошую масштабируемость.
Для построения базиса (Грёбнера или инво-лютивного) с помощью модулярных вычислений необходимо выполнить следующие шаги [5, 6]:
1. Вычислить достаточное количество модулярных образов базиса идеала, порожденного исходной системы.
2. Выполнить восстановление коэффициентов из кольца Ъ у всех термов.
3. Проверить, является ли полученное множество полиномов базисом вообще и базисом
идеала, порожденного исходной системой, в частности. Если не базис, повторяем с пункта 1.
Как видно, все шаги легко допускают паралле-лизацию: на первом и третьем шаге очевидную, второй шаг можно распараллелить по схеме, похожей на умножение Карацубы.
Кроме плюсов, модулярный подход имеет по крайней мере два минуса, отсутствующие при вычислениях с коэффициентами из Ъ.
Выполнение первого шага сразу же ставит перед нами проблему «неудачных» модулей - вычисление образов по некоторым модулям приводит к потере информации. В данном контексте это означает, что некоторые термы, имеющие ненулевые коэффициенты в результирующем базисе, отсутствуют в модулярном образе и не могут быть восстановлены.
Второй проблемой является адекватное восстановление полиномов из их образов. При «наивном» подходе можно подумать, что проводя вычисления над кольцом Ър[х] мы сможем по китайской теореме об остатках получить коэффициенты исходного полинома. Однако, каждый образ /р полинома /, вычисленный по разным модулям р, будет иметь в своем составе коэффициент Ср ■ /р, зависящий от модуля. Этот коэффициент неустраним (у нас нет модулярного аналога наибольшего общего делителя), поэтому надо переходить к вычислениям над кольцом рациональных чисел, при которых коэффициент лидирующего терма всегда будет равен единице.
В данной работе коэффициенты в образах принадлежат множествам числам Фарея, получение образа и восстановление рационального числа описано в [7].
2. ВОПРОСЫ ЭФФЕКТИВНОЙ РЕАЛИЗАЦИИ
Во первых, каждое вычисление образа базиса по модулю вообще может дать разные результаты (с точки зрения мономов, находящихся в полиномах) при использовании разных модулей. Однако, чтобы получить не вероятный, а действительный базис, мы обязаны восстановить и проверить все полученные образы.
Для быстрого разбиения образов на классы автор использовал сравнение полинома Гильберта (для определения эквивалентности лидирующих мономов) и подпись базиса для проверки идентичности мономов в хвостах.
Определение 6. Пусть дан базис Р = /1,...,/п, полиномы которого сортированы по возрастанию лидирующих мономов по какому-либо допустимому упорядочению. Назовем, подписью базиса значение контрольной суммы тс15 [8], полученное суммированием, всех мономов всех полиномов /г|Уг = 1,... ,п, причем мономы суммируются в порядке убывания, по тому же упорядочению.
Коллизии, существующие в тс15, хотя и редкие, но вероятные, обходятся сравнением полиномов Гильберта. Таким образом, используя подпись и полином Гильберта можно эффективно и точно разделить образы базисов по мономам, т.е. отсечь «неудачные» модули, поскольку соответствующих им образов будет очень мало.
Во вторых, оказалось важно, сколько модулярных образов базисов надо вычислить перед началом восстановления. Пример скетедив в однопоточном варианте с подсчетом 8 базисов за проход, считается около получаса на Хеоп-Е5410@2.33Ггц. Если же считать по 80 базисов за проход, время вычислений на той же машине снижается до одной минуты. Автором была запрограммирована схема предиктор-корректор для определения числа базисов, считаемых перед началом восстановления, но в текущем виде схема не применима к параллельному варианту, поэтому она будет описана в следующих работах.
В третьих, необходимо уделять внимание порядку применения китайской теоремы об остат-
Ъ
Необходимо, чтобы модулярные коэффициенты обрабатывались строго в порядке возрастания модулей. Несоблюдение этого условия вызывает существенное падение производительности на всех примерах, рассмотренных в данной работе. Вследствие того, что в данном подходе параллельная программа нуждается в применении блокировок, данная реализация использует восстановление в один поток, что конечно несколько снижает общий коэффициент утилизации. В
ЯНОВИЧ Таблица 1
2*Пример 1 поток 8 потоков Ускорение
Mod J В Singular ModJB Singular ModJB Singular
assur44 24.99 21.72 3.84 13.09 6.51 1.66
chemequs 460.09 324.06 66.92 384.00 6.88 0.84
chemkin 78.63 327.46 11.39 383.95 6.90 0.85
cohn3 388.66 123.92 57.17 105.41 6.80 1.18
cyclic7 230.80 74.16 48.10 40.77 4.80 1.82
dl 163.07 50.03 24.95 47.21 6.54 1.06
dl 461.34 50.47 78.84 41.36 5.85 1.22
ecolO 152.79 71.38 20.96 49.49 7.29 1.44
ecoll 3240.40 1467.70 391.06 787.56 8.29 1.86
extcvc6 991.09 333.78 227.68 185.67 4.35 1.80
£855' 336.12 44.64 49.39 31.89 6.81 1.40
fabrice24 207.19 134.25 32.36 120.25 6.40 1.12
hcvclic7 280.83 1118.52 52.78 1047.14 5.32 1.07
il 2447.78 1528.42 325.26 1514.99 7.53 1.01
iliasl3 4473.00 640.51 790.14 422.58 5.66 1.52
ilias
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.