Алгоритмы вычисления базисов Грёбнера и инволютивных базисов

• Автор: Митюнин, Владимир Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 91 с. : ил.

1 Вступление

1.1 Актуальность темы

1.2 Практическая ценность

1.3 Апробация работы

1.4 Публикации

1.5 Обзор

1.6 Структура и объем диссертации

2 Последовательные алгоритмы вычисления базисов Грё-бнера

2.1 Классический алгоритм Бухбергера

2.2 Вероятностный алгоритм вычисления базисов Гребнера

2.3 Версия, использованная при распараллеливании

3 Параллельные алгоритмы вычисления базисов Грёбнера
3.1 Обзор параллельных алгоритмов
3.2 Алгоритм Pipeline
3.3 Алгоритм Conveyer
3.4 Алгоритм с использованием графа редукций
4 Оценка качества распараллеливания алгоритмов вычисления базисов Грёбнера
4.1 Оценка качества распараллеливания путем моделирования работы параллельного алгоритма
5 Вычисление инволютивных базисов в дифференциальном модуле
5.1 Реализация алгоритма
5.2 Анализ производительности алгоритма
6 Пример применения системы для вычислений в дифференциальном модуле
6.1 Вычисление размерностного многочлена при заменах образующих в системе уравнений Дирака
7 Заключение

1 Вступление
1.1 Актуальность темы
В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят себе применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения.
Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных алгебраических уравнений с целочисленными коэффициентами. Одним из применяемых методов является построение базисов Гребнера. Теоретическая сложность этого алгоритма, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего времени это действительно было так, и алгоритм мог применяться, главным образом, в академических целях. Однако за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма Бухбергера, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области был достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Грёбнера, на практике для реальных систем его производительность существенно выше.
В последнее время вызывает сильный интерес альтернативный алгоритм вычисления нередуцированного стандартного базиса, получивший название инволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуцированному базису Гребнера. Основное отличие инволютивного алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном алгоритме вычисления нормальной формы, который ограничивает набор возможных редукций. Инволютивный алгоритм вычисления стандартного базиса пришел в коммутативную алгебру из диффференциальной алгебры. На данный момент остается открытым вопрос о наиболее эффективном подходе к вычислению стандартных базисов. Существует теория, что инволютивный алгоритм вычисления стандартных базисов значительно эффективнее классического для достаточно больших систем уравнений. В данной работе уделяется большое внимание данному вопросу.
Дальнейшим путем к увеличению эффективности алгоритмов является попытка обогнать прогресс в развитии вычислительной техники путем использования большого количества процессоров одновременно - распараллеливание. Для ряда алгоритмов с помощью данного подхода удается существенно улучшить время работы. К сожалению, большинство алгоритмов компьютерной алгебры распараллеливаются со сравнительно небольшим коэффициентом эффективности. Алгоритм вычисления базисов Гребнера не является исключением. Тем не менее, грамотная реализация алгоритма вычисления на кластере наиболее доступного в данное время типа сеть рабочих станций позволяет увеличить производительность алгоритма до одного порядка на ряде примеров, что продемонстрировано в данной работе.
Основная проблема, с которой достаточно тяжело справиться состоит в том, что в процессе вычислений начинается взрывной рост целочисленных коэффициентов. Это приводит к очень большим затратам как по процессорному времени, так и по памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате появления богатого опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений.
В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с
Требуемая редукция в-полинома / по промежуточному базису Р преобразуется в цепь редукций следующего вида:
/ -Ч. ЛОД/, Рг) -> Л^(^(/, Рх), Р2)
-> ^р(лгр(лгр(. ..), р„_1), рп) = /'
которую можно считать первым приближением к искомой нормальной форме Л^Р(/, Р). Основным преимуществом данного подхода по сравнению с последовательной версией алгоритма является тот факт, что данные цепи могут вычисляться одновременно, как показано ниже.
Slave1 Slave2 Slavey
Moment 1 NF(fhP) 0
Moment 2 NF(h, Рг) NF(NF(fuP1),P2)
Moment 3 NF(f3,P1) NF{NF(f2,Pl),P2) NF(NF(NF(f1,Pl),P2),Ps)
Однако, как было упомянуто, приведенная цепь является только первой аппроксимацией искомой нормальной формы NF(f,P). Использование данного приближения не гарантирует корректности алгоритма. Если полином f не находится в нормальной форме относительно одного из подмножеств Рг, полученный результат не является нормальной формой относительно промежуточного базиса. Таким образом, в случае если f ф NF(f, Рг), необходимо осуществить повторный прогон f через цепочку редукций. Данный процесс необходимо продолжать до стабилизации результата. В данной реализации подобные частично редуцированные полиномы накапливаются в списке PendingList.
Полученные нормальные формы полиномов распределяются по рабочим станциям. Стратегия выбора очередной рабочей станции может различаться - например, можно использовать генератор случайных чисел.
Описанная логика реализована в виде процедуры processpipeline() Algorithm processpipeline
Input: GB - polynomials list, В - the set of critical pairs
Output: modified set GB and В
begin
h <— receive polynomial from the pipeline if h ф 0 then if h was modified by reductions then