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

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

КОМПЬЮТЕРНАЯ АЛГЕБРА -

УДК 517.929

КОМПАКТНОЕ ПРЕДСТАВЛЕНИЕ ПОЛИНОМОВ ДЛЯ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ БАЗИСОВ ГРЁБНЕРА И ИНВОЛЮТИВНЫХ БАЗИСОВ *

© 2015 г. Д.А. Янович

Объединенный институт ядерных исследований 141980 Дубна, ул. Жолио Кюри, д. 6 E-mail: yan@jinr.ru Поступила в редакцию 13.10.2014

При вычислении базисов Грёбиера и ииволютивиых базисов с рациональными коэффициентами львиную долю памяти занимают числа произвольной точности, но в случае модулярных вычислений, а особенно при нахождении булевых базисов на первое место выходит проблема компактного представления мономов в составе полиномов системы. Для этого используют, к примеру, /,1)1) диаграммы и прочие структуры, которые осложняют выполнение типичных операций алгоритмов -умножения на моном и редукции полиномов. В данной работе сделана попытка создания удобного (в смысле вычисления базисов) и компактного представления полиномов на основе хэш-таблиц, приведены результаты тестовых прогонов.

1. ВВЕДЕНИЕ

Инволютивные базисы и базисы Грёбиера

Ниже мы будем использовать следующие обозначения:

X - множество переменных X = {х1,..., хга}; М = К[Х] - кольцо многочленов над полем К нулевой характеристики;

/, д, Н, ц, г - многочлены из М; а, Ъ, в - элементы из К; р, С, н - конечные подмножества из М; (Р) - идеал из М, порожденный Р;

- множество неотрицательных чисел; М = {х11 ■ ■ ■ хПп | ^ е ^>0} - множество моноМ

и, V, VI, в, I множество мономов или термов; и, V, Ш - конечные подмножества из М; degi(u) - степень переменной х^ в и; deg(u) - полная степень монома и;

* Исследования, представленные в работе, были выполнены при частичной поддержке грантов 12-07-00294 и 13-01-00668 Российского фонда фундаментальных исследований и гранта НШ-3003.2014.2 Министерства образования и науки РФ.

>— допустимое мономиальное упорядочение с порядком переменных Х1 >- ... >- хга;

И(/) - лидирующий терм относительно упорядочения >-;

1т(/) - лидирующий моном /; 1т(Р) = {1т(/) | / е Р} - множество лидирующих мономов из Р;

1ет(Р) - наименьшее общее кратное множества мономов из 1т(Р);

и | V означает, что моном и делит моном V. Определение и алгоритм построения базисов Грёбнера были предложены Б. Бухбергером [1]. Кратко напомним основные понятия.

Определение 1. [1, 2] Пусть заданно допустимое мономиальное упорядочение. Конечное подмножество С = {д1, ..., дт} элементов идеала I называется его ба,зисом, Грёбнера, если

(1т(д1), ..., 1т(дт)) = (1т(1)).

Центральным понятием в алгоритме вычисления базиса Грёбнера является Я-полином.

Определение 2. [1, 2] 8-полиномом /, д е К

•называется комбинация

йро1у(/,д) =

1еш(1ш(/), 1ш(д))

1^(/) 1еш(1ш(/), 1ш(д))

/ -

д.

Теорема 1. [1, 2] Пусть I - некоторый полиномиальный идеал. Базис С = |д1, ..., дт} идеала, I является базисом Грёбнера в том и только в том случае, когда для всех пар г = ] : Мотта1Готт(8ро1у(дг,д^ ),С) = 0.

Если некоторым самосогласованным способом запретить деление но некоторым неременным, называемыми немультипликативньши и разрешить но другим, называемыми мультипликативными, то мы получим сужение операции деления инволютивное деление [3, 4]. Дадим основные определения.

Определение 3. /5/ Мы, будем, говорить, что на множестве мономов М определено инволю-тивное деление Ь, если для любого конечного не пуст,ого и С М и для, любого и € и задано М^(и, и) С X, генерирующее подмоноид Ь(и, и) С М, состоящий из мономов с переменными из М^(и, и), удовлетворяющий следу-ющи,ы условиям:

(a) Изи,у € и ииЬ(и,и)ПуЬ(у,и)= 0 следует и € уЬ(у, и) или V € иЬ(и, и);

(b) Из V € и и V € иЬ(и, и) следует Ь^, и) С Ь(и, и);

(c) Из и € V иУ С и следует Ь(и, и) С Ь(и, V)

для всех и € V.

Элементы М^(и, и) называются Ь-мульти-пликативными для и, элементы ММ^ (и, и) = X \ М^ (и,и) называются Ь-немульти-пликативными. Если ш € иЬ(и,и), то и называется (Ь-)инволютивным делителем ш и обозначается и \ь ш. В свою очередь, моном ш называется (Ь-)кратным и.

Определение 4. [3, 4] Множество мономов Ь

(Уи € и) (Уш € М) (3v € и) [ V \ь иш ].

Используя конструктивное и нетерово деление (например, деление Жане) можно построить ин-волютивный базис а;п'оритмическим путем, пополняя частично инволютивное множество.

Определение 5. [3] Авторедуцированное .множество Г называется частично инволют иены м до монома V в допустимом мономиаль-ном упорядочении У, если выполнено следующие условие

(У/ € Г)(Уи € М)(1ш(/) У V) [Могша1Еогш^(/и, Г) = 0],

где МогшаГРогш^, означает инволют,ивную нормальную форму, определенную заменой обычного деления, на, инволютивное.

Таким образом, добавив в частичный базис ненулевые инволютивные нормальные формы немультинликативных продолжений множества Г, мы получим искомый инволютивный базис.

Приведем упрощенный алх'оритм для вычисления инволютивнохх) базиса, не использующий критерии для пропуска редукций р к нулю. Полный алх'орптм приведен в [3].

Связь между инволютивным базисом и базисом Грёбнера определяется следующей теоремой:

Теорема 2. [3] Инволютивный базис, авторедуцированный в смысле обычного деления, является редуцированным, базисом Грёбнера.

2. МОТИВАЦИЯ

При разработке модулярной параллельной версии реализации алгоритма вычисления ин-волютивных базисов [6] было выявлено много примеров, при вычислении которых не хватало оперативной памяти. Так как коэффициенты при вычислении по модулю не играют значительной роли, стало очевидно, что причина сверхбыстрого увеличения необходимой памяти кроется в затратах на внутреннее представление мономов и полиномов.

Для проверки гипотезы были проведены эксперименты с примерами из криптографии и, например, тест НРЕ25-96 [7] доводил потребление до 16 Гб в течение нескольких секунд вычислений. Проведя исследование множества мономов, входящих в полиномы, которые появлялись в ходе вычислений, было решено попытаться использовать более сложные структуры данных для представления полиномов, пожертвовав скоростью в угоду экономии ресурсов.

3. ПРЕДСТАВЛЕНИЕ ПОЛИНОМОВ

3.1. Обзор современных представлений полиномов

В настоящее время используются несколько типов представлений полиномов:

• списки термов - классическое распределенное представление, широко используется в системах компьютерной алгебры общего типа, отдельные термы представлены в виде коэффициента и монома в виде мультиин-декса степеней;

ставления, фактически список списков термов. Более эффективен по времени вычислений, менее эффективен по используемой памяти;

ние хорошо подходит для выполнения некоторых операций над полиномами, но для задач рассматриваемых в статье, ведущее к слишком большим накладным расходам;

• ZDD [10] - вариант рекурсивного представления полинома, используется в основном при вычислении булевых базисов и решении задач SAT;

ступом [11] - к сожалению, в открытых источниках информации о данном представлении нет, но, согласно документации, оно должно быть быстрее и компактнее представления в виде списка термов.

3.2. Предлагаемое представление

Для задач вычисления базисов Грёбнера и ин-волютивных базисов представление полиномов должно обеспечивать высокую эффективность

следующих операций: •

жение);

Списочное представление полиномов пока что является лучшим (по мнению автора), соответствующим описанным критериям. Поэтому попытаемся улучшить именно его.

В ходе экспериментов было сделано несколько

наблюдений: •

комбинации мультииндексов, в задачах вычисления базисов Грёбнера, множество возможных мономов ограничено широко известной фигурой staircase;

мов Q, которые необходимо рассмотреть в ходе алгоритма, образуется огромное количество почти одинаковых полиномов, т.е. в самой объемной структуре данных большое количество одинаковых мономов;

дованием, мы не можем адресовать больше 264 объектов.

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

struct Monom {

long refcount; VAR* monom;

>

Для обеспечения уникальности каждого муль-тииндексного представления монома в системе следует придерживаться определенного протокола:

• при появлении потенциально нового монома (вследствие редукций, продолжений или начального ввода данных) необходимо проверить, есть ли такой мультииндекс в хэш-таблице. Если есть - выдать для использования заместителя (в данном случае - указатель на члена структуры топот, увеличив счетчик использования refcount. Если мультииндекса в таблице нет - занести его с ref count равным 1 и также возвратить заместителя для использования;

использования refcount на 1 и при достижении нулевого значения удаляем запись из таблицы.

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

Хэш-таблицы и ранее применялись для оптимизации полиномиальных вычислений [12], но автору не известно ни одного предшествующего использования хэш-таблицы именно для уменьшения избыточности хранения данных.

4. ДЕТАЛИ РЕАЛИЗАЦИИ

Как известно [13], сложность доступа к данным в хэш-таблице как минимум постоянна, как максимум - пропорциональна количеству элементов, но на практике сильно зависит от свойств используемой хэш-функции, а объем занимаемой памяти пропорционален количеству элементов, но также сильно зависит от реализации самой хэш-таблицы.

При реализации хранилища мономов тестировались следующие реализации хэш-таблиц:

доступа, худшая по объему занимаемой памяти;

по скорости и объему занимаемой памяти;

рость

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

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