*
m
Содержание
1 Вступление 3
1.1 Актуальность темы...................................... 3
1.2 Практическая ценность.................................. 5
1.3 Апробация работы....................................... б
1.4 Публикации............................................. 7
1.5 Обзор.................................................. 8
1.6 Структура и объем диссертации......................... 21
2 Последовательные алгоритмы вычисления базисов Грё-бнера 22
2.1 Классический алгоритм Бухбсргсра...................... 22
2.2 Вероятностный алгоритм вычисления базисов Гребнера . . 42
2.3 Версия, использованная при распараллеливании.......... 45
3 Параллельные алгоритмы вычисления базисов Грёбнера 47
3.1 Обзор параллельных алгоритмов......................... 47
3.2 Алгоритм Pipeline..................................... 48
3.3 Алгоритм Conveyer..................................... 52
3.4 Алгоритм с использованием графа редукций.............. 55
4 Оценка качества распараллеливания алгоритмов вычисления базисов Грёбнера 59
4.1 Оценка качества распараллеливания путем моделирования работы параллельного алгоритма............................ 59
5 Вычисление инволютивных базисов в дифференциальном модуле 67
5.1 Реализация алгоритма.................................. 70
5.2 Анализ производительности алгоритма................... 73
6 Пример применения системы для вычислений в дифференциальном модуле 79
6.1 Вычисление размерностного многочлена при заменах образующих в системе уравнений Дирака....................... 79
7 Заключение 86
2
1 Вступление
1.1 Актуальность темы
В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят себе применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения.
Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных «алгебраических уравнений с целочисленными коэффициентами. Одним из применяемых методов является построение базисов Гребнера. Теоретическая сложность этого алгоритма, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего времени это действительно было так, и алгоритм мог применяться, главным образом, в «академических целях. Однако за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма Бухбергера, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области был достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Грёбнера, на практике для реальных систем его производительность существенно выше.
В последнее время вызывает сильный интерес альтернативный «алгоритм вычисления нередуцированного стандартного базиса, получивший название ииволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуциров«анному базису Гребне-ра. Основное отличие шшолютивного «алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном «алгоритме вычисления нормальной формы, который ограничивает шабор воз-
можных редукций. Инволютивный алгоритм вычисления стандартного базиса пришел в коммутативную алгебру из диффференциальной алгебры. На данный момент остается открытым вопрос о наиболее эффективном подходе к вычислению стандартных базисов. Существует теория, что инволютивный алгоритм вычисления стандартных базисов значительно эффективнее классического для достаточно больших систем уравнений. В данной работе уделяется большое внимание данному вопросу.
Дальнейшим путем к увеличению эффективности алгоритмов является попытка обогнать прогресс в развитии вычислительной техники путем использования большого количества процессоров одновременно - распараллеливание. Для ряда алгоритмов с помощью данного подхода удается существенно улучшить время работы. К сожалению, большинство алгоритмов компьютерной алгебры распараллеливаются со сравнительно небольшим коэффициентом эффективности. Алгоритм вычисления базисов Гребнера не является исключением. Тем не менее, грамотная реализация алгоритма вычисления на кластере наиболее доступного в данное время типа сеть рабочих станций позволяет увеличить производительность алгоритма до одного порядка на ряде примеров, что продемонстрировано в данной работе.
Основная проблема, с которой достаточно тяжело справиться состоит в том, что в процессе вычислений начинается взрывной рост целочисленных коэффициентов. Это приводит к очень большим затратам как но процессорному времени, так и но памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате появления богатого опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений.
В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с 4
неизвестными имеет вид
/і = а + b -\- с + d /2 = ab 4- ad 4- be 4- cd /з = abc 4- abd 4- acd 4- bed /4 = abed — 1 Базис Гребнера для этой системы имеет вид
gi = с2 с/6 — c2d2 - с/4 4-1
(j2 = (?d2 4- с2 с/3 - с - d
<73 = bdA — b + d5 - d
04 = be — bdb 4- (?dA + cd — dG — d2
9b = b2 4- 2bd 4* c/2
0G = a + 6 + c + d
Для системы уравнений cyclic от пяти неизвестных базис Гребнера 40/ состоит из 11 уравнений
= е15 -I- 122с10 — 122е5 — 1 02‘ = 55с/2 е5 - 55с/2 - 2с/еп - 231с/е6 4- 233с/е - 8е12 - 979е7 + 987е2 дг = 6d7 4- 57с/6е6 - 39с/6е + 25с/5е7 - 19с/5е2 - 5с/4е8 + 5c/4e3 - 8c/3e9 +
4- 8d3e4 - 2c/2e10 4- 14c/V - 18c/2 - 18c/e6 - 6e7
04 = 360150ce5 - 360150c 4- 71540c/V - 110722c/V - 1744327c/V -
- 3078595c/6e5 4- 233730c/6 4- 219158c/5e6 - 1058999c/5 e 4- 236G210c/4e7 -
- 2437750c/4e2 4- 1281458c/3e8 - 117073Gc/3e3 4- 200573c/2e9 4- 1543754c/2e4 4-4- 2844865c/e5 4- 83984 le6
05 = 360150cc/ — 3G0150cec — 71540c/10e2 4- 110722c/9e3 4- 1744327c/8e4 4-4- 3064189c/V - 233730c/7 4- 313864^6° 4- 1058999c/6e - 795956c/V +
4- 2437750c/5e2 - 1403909dV 4- 1293187c/4e3 - 136025Gc/3e9 - 744221c/3e4 -
- 410571c/2e10 - 2059738c/2e5 - 13728G3c/c6 - 1570254c7
и т.д. Для системы уравнений cyclic от шести неизвестных базис Гребнера состоит из 17 уравнений, длина коэффициентов которых превышает 100 десятичных цифр
1.2 Практическая ценность
Результатом работы является программный комплекс, предназначенный для построения базисов Гребнера и инволютивных базисов в кольце мно-
5
гочленов с целочисленными коэффициентами и коэффициентами из конечного ноля. В качестве языка реализации был выбран язык С-Ь-Ь, позволяющий добиться высокой производительности и качества программного кода. Распараллеливание осуществлялось на кластере типа "сеть рабочих станций" под управлением операционной системы Linux и было осуществлено в терминах библиотеки MPI.
В качестве примеров применения базисов Гребнера можно привести такие задачи, как исследование систем нелинейных алгебраических уравнений на совместность, нахождение количества решений систем нелинейных алгебраических уравнений, составная часть большого количества алгоритмов в конструктивной теории полиномиальных колец или предварительный этап для численного решения систем нелинейных алгебраических уравнений.
1.3 Апробация работы
По результатам, полученным в данной работе, были сделаны доклады и публикации на российских и международных конференциях, список которых приведен ниже.
• International Association for Mathematics and Computers in Simulation Conference on Applications of Computer Algebra (IMACS АСА) 2000, Петербург, Россия
• Formal Power Series and Algebraic Combinatorics (FPSAC) 2000, Москва, Россия
• International Workshop on Computer Algebra and its Application to Physics (СААР) 2001, Дубна, Россия
• International Workshop on Involutivc Systems and Symmetries of Differential Equations, 2001, Новосибирск, Россия
• Workshop on Under- and Over-Determined Systems of Algebraic or Differential Equations, 2002, Карлсруэ, Германия
• Computer Algebra in Scientific Computing (CASC) 2002, Ялта, Украина
• International Association for Mathematics and Computers in Simulation Conference on Applications of Computer Algebra (IMACS АСА) 2003, Соединенные Штаты Америки
С помощью созданного пакета программ были вычислены базисы Греб-пера для большого набора тестовых систем из набора POSSO. В частности, были вычислены базисы Гребнера для систем попадающих в категории "очень сложные" и недоступные для пакета компьютерной алгебры Singular.
1.4 Публикации
• М.В. Кондратьева, В.Л. Митюнин "Вычисление дифференциального размерностного многочлена при заменах образующих в системе уравнений Дирака", "Программирование", 2001, 1, р. 37-40
• Mityunin V.A. ” Implementation of the differential involutive algorithms in the CAS Maple VR5”, Proceedings of IMACS АСА 2000, pp. 38-39.
• Kondratieva М., Makarevich N., Mityunin V. ’’Computation of primitive element in differential module”, Proceedings of IMACS АСА 2000, p. 28-29. Add. Thesises 12-th International Conference FP-SAC’00, pp. 23-24.
• V.A.Mityunin, A.I.Zobnin, A.I.Ovchinnikov, A.S.Semenov’’Involutive and Classical Groebner Bases Construction from the Computational Viewpoint” Proceedings of СААР 2001, p.221-230
• Mityunin V.A., Semenov A.S. ’’Parallel Implementations of Honey Strategy Buchberger Algorithm”, Proceedings of’’Workshop on Underand Over-Determined Systems of Algebraic or Differential Equations” (Karlsruhe, Germany, 2002), p.221-225
• Mityunin V.A., Semenov A.S. ”An Estimation of the Parallelization Quality of the Involuive Basis Computation Algorithm”, Proceedings of CAS С 2002
• Mityunin V.A, Pankratov E.V., ’’Comparison of the parallelIization quality of algorithms for computing Groebner and involutive bases using the Faugere method”, Proceedings of IMACS АСА 2003, United States Of America
• Митюнин B.A., Панкратьев E.B "Параллельные алгоритмы построения базисов Гребнера", Международная алгебраическая конференция, посвященная 250-летию Московского Государственного Университета, тезисы докладов, Москва, мех-мат МГУ, 2004, стр. 97-99
- Київ+380960830922