Алгоритмы вычисления базисов Грёбнера и инволютивных базисов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК 512+519.6

Митюнин Владимир Александрович

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

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА - 2004

Работа выполнена на кафедре высшей алгебры механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: кандидат физико-математических наук,

ведущий научный сотрудник Б.В. Панкратьев

Официальные оппоненты: доктор физико-математических наук,

профессор В. П. Гердт кандидат физико-математических наук, доцент И.Н. Балаба Ведущая организация: Вычислительный центр РАН

Защита диссертации состоится_17 декабря_2004 г. в

16 ч. 15 м. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж)

Автореферат разослан_17 ноября_2004 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В.Н.Чубариков

Общая характеристика работы

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

В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения.

Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных алгебраических уравнений с целочисленными коэффициентами. Часто решение разбивается на два этапа: на первом этапе система приводится к некоторому стандартному виду, называемому базисом Гребнера. На втором этапе решается система, полученная на первом этапе. Теоретическая сложность алгоритма пополнения исходной системы до базиса Гребнера, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего времени это действительно было так, и алгоритм мог применяться, главным образом, в академических целях. Однако, за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма пополнения, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Гребнера, на практике для реальных систем его производительность существенно выше.

В последнее время вызывает значительный интерес альтернативный алгоритм вычисления нередуцированного стандартного базиса, получивший название инволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуцированному базису Гребне-ра. Основное отличие инволютивного алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном алгоритме вычисления нормальной формы, который ограничивает набор возможных

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

Дальнейшим путем к увеличению эффективности алгоритмов является попытка использования большого количества процессоров одновременно — распараллеливание. Для ряда алгоритмов с помощью данного подхода удается существенно улучшить время работы. К сожалению, большинство алгоритмов компьютерной алгебры распараллеливаются со сравнительно небольшим коэффициентом эффективности. Алгоритм вычисления базисов Гребнера не является исключением. Тем не менее, грамотная реализация алгоритма вычисления на кластере наиболее доступного в данное время типа сеть рабочих станций позволяет увеличить производительность алгоритма до одного порядка на ряде примеров, что продемонстрировано в данной работе.

Основная проблема, с которой достаточно тяжело справиться, состоит во взрывном росте целочисленных коэффициентов в процессе вычислений. Это приводит к очень большим затратам, как по процессорному времени, так и по памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате накопления опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений.

В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с 4 неиз-

вестными имеет вид

/з = abc + abd + acd + bed

Базис Гребнера для этой системы имеет вид

Для системы уравнений cyclic от пяти неизвестных базис Гребнера состоит из И уравнений

д2 = 55d2e5 - 55d2 - 2de11 - 231 de6 + 233de - 8e12 - 979e7 + 987e2 93 = 6d7 + 57d®e6 - 39d®e + 25d5e7 - 19d5e2 - 5d*es + SdV - 8d3e9 +

gi = 360150ce5 - 360150c + 71540d9e2 - 110722d®e3 - 1744327dV -

- 3078595dV + 233730^ + 219158dse6 - 1058999d5e + 23662 lOdV -

- 2437750сГ®е2 + 1281458ci3e8 - 1170736d3e3 + 200573d2e9 + 1543754d2e4 +

g5 = 360150cd — 360150ce® — 71540d10e2 + 110722d9e3 + 1744327d®e4 +

+ 3064189dTes - 233730d7 + 313864d6e6 + 1058999с^е - 795956dse7 +

+ 2437750d5e2 - 1403909rf*e8 + 1293187d4e3 - 1360256d3e9 - 74422ld3e4 -

- 410571d2e10 - 2059738dV - 1372863de6 - 1570254e7

и т.д. Для системы уравнений cyclic от шести неизвестных базис Гребнера состоит из 17 уравнений, длина коэффициентов которых превышает 100 десятичных цифр

Цель работы.

Целью работы являются построение эффективных алгоритмов вычисления базисов Грёбиера в кольцах многочленов с коэффициентами из кольца целых чисел или конечного поля Z/pZ и в дифференциальном модуле, и их распараллеливание на кластерах типа "сеть рабочих станций".

Научная новизна.

Основные результаты диссертации являются новыми и заключены в следующем:

1. Построены параллельные алгоритмы вычисления базисов Грёбнера, дан метод оценки и проведена оценка эффективности распараллеливания алгоритмов вычисления базисов Грёбнера для ряда тестовых СНАУ, в частности, получена оценка для максимального числа эффективно используемых процессоров в параллельных алгоритмах.

2. Реализован программный комплекс вычисления базисов Грёбнера и инволютивных базисов в кольцах полиномов с коэффициентами из конечного поля или кольца целых чисел и в дифференциальном модуле.

3. Предложены обратимые линейные замены образующих, понижающие дифференциальный размерностный многочлен в системе уравнений Дирака, и приведен вид системы после проведения данных замен.

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

Теоретическая и практическая ценность.

Результатом работы является набор алгоритмов и программный комплекс, предназначенный для построения базисов Грёбнера и инволютивных базисов в кольце многочленов с целочисленными коэффициентами и коэффициентами из конечного поля. В качестве языка реализации был выбран язык C + +, позволяющий добиться высокой производительности и качества программного кода. Распараллеливание осуществлялось на кластере типа "сеть рабочих станций" под управлением операционной системы Linux и было осуществлено в терминах библиотеки MPI.

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

горитмов в конструктивной теории полиномиальных колец или предварительный этап для численного решения систем нелинейных алгебраических уравнений.

Проведено построение примитивного элемента для системы дифференциальных уравнений Дирака с использованием обратимых линейных замен образующих.

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

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

• 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 Involutive 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.

Публикации.

Основные результаты диссертации опубликованы в восьми работах, список которых приведен в конце автореферата.

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

Диссертационная работа состоит из введения, 5 глав, заключения, и содержит библиографию, включающую 53 наименования. Общий объем диссертации составляет 88 страниц.

Структура работы отражена в оглавлении.

Краткое содержание работы

Введение (Первая глава).

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

Работы по повышению эффективности алгоритма вычисления стандартного базиса можно разделить на несколько классов . К первому из них следует отнести методы, имеющие достаточно низкий теоретический интерес (по крайней мере с точки зрения теории стандартных базисов) и направленные на оптимизацию элементарных операций, таких как арифметика коэффициентов или сравнение мономов1,2. Вторым подходом является улучшение применяемых стратегий для выбора и отбрасывания s-элементов3,4. Третьим способом повышения эффективности алгоритмов вычисления базисов Грёбнера является их распараллеливание. Работы в этих трех на-

5

правлениях рассмотрены детально . Вторая глава.

Во второй главе вводятся основные обозначения, представлены последовательные алгоритмы вычисления базиса Грёбнера и проводится дока-

1Robbiano, L. Term Orderings on the Polynomial Ring, In Proceedings of EUROCAL 85, Lecture Notes in (Computer Science 204 (1985), pp. 513-517.

2Bachmann 0., Schonemann H. Monomial Representations for Grobner Bases Computations, Centre for Computer Algebra Department of Mathematics University of Kaiserslautern, 1998, http://www.mathematik.uni-kl.de/ zca/Reports_on_ca/18/paper_html/paper.html

3Giovanni A., Mora Т., Niesi G., Robbiano L., Traverso C. One sugar cube, please or Selection Strategies in Buchberger Algorithm, Proceedings of 1SSAC 1991, ACM, 1991, 49-54

4Gebauer R., Moller H.M. On an Installation of Buchberger's Algorithm, J. Symbolic Computation, 1988, 6, 275-286.

5Faugere J.C. Parallelization of Grobner Basis, Proceedings of PASCO 1994, World Scientific Publ. Сотр.

зательство их корректности.

Одним из наиболее важных методов, используемых в ходе решения систем алгебраических уравнений, является построение базиса Гребнера, также известного как стандартный базис. В случае идеала размерности ноль, когда система имеет конечное число решений, в качестве метода решения алгебраической системы уравнений можно предложить следующий алгоритм, состоящий из четырех шагов. В первую очередь, необходимо построить базис Гребнера для отношения порядка DegRevLex (степень обратная лексикографика). Затем проводится вычисление базиса в отношении порядка Lex (чистая лексикографика) путем пересчета найденного базиса с помощью, например, алгоритма FGLM или GrobnerWalk, и полученная треугольная система уравнений решается с помощью численных методов. Наиболее сложным с алгоритмической точки зрения является первый шаг данной цепочки в силу того, что очень непросто предсказать время, необходимое для построения стандартного базиса и размер коэффициентов как результата, так и полиномов, возникающих в процессе вычислений. Как правило, на практике существует огромное различие между вычислениями в кольцах полиномов с коэффициентами из конечного поля и целочисленными коэффициентами. Основной проблемой является рост коэффициентов в процессе вычислений [4].

Более глубоко с теорией можно ознакомиться в работах В. Buchberger, Т. Mora6'7-8"-10.

Третья глава.

В третьей главе построены параллельные версии алгоритмов пополнения.

Существует достаточно большое количество работ, посвященных распараллеливанию алгоритма Бухбергера, но ни в одной из них достигнутые результаты не являются слишком хорошими. J.C. Faugere показал, что алгоритм вычисления базиса Гребнера является очень сложно распараллели-

6Buchberger В. Critical-pair-completion algorithm for finitely generated ideals in rings, Logic and Machines: Decision problems and complexity, E. Borger, G. Hasenjaeger, D. Rodding, Editors Lecture Notes in Computer Science 171, Springer Verlag, 137 - 161, 1984.

7Buchberger B. Grobner Bases : An Algorithmic Method in Polynomial Ideal Theory, In N. K. Bose, editor, Multidimensional Systems Theory, pages 184-232. U. Reidel Publishing Company, 1985.

8Buchberger B. A Criterion for Detecting Unnecessawy Reductions in the Construction of Gfobner Bases, Proceedings of the 1744 European Symposium on Symbolic and Algebraic Computation, Lecture Notes in Computer Science 72, Springer-Verlag, Berlin, Heidelberg, 3-21,1976.

9Mora Т., Pfster G., Traverso C. An introduction to the tangent cone algorithm, Advances in Computing research, Issues in Robotics and nonlinear geometry, 1992, 6,199-570.

10Moller H.M., Mora Т., Traverso С Grobner bases computation using syzygies, Proc. of ISSAC 1992.

ваемым по своей сути. Основная причина этого состоит в том, что результат редукции полинома, как правило, сильно зависит от полученных ранее полиномов, и в частности, от последнего полученного полинома базиса11. Тем не менее, применяя определенные методы для модификации стратегии редукции, на практике может быть достигнуто достаточно значительное ускорение. В данной работе при распараллеливании алгоритма был в первую очередь сделан акцент на сохранении стратегии, хорошо зарекомендовавшей себя в последовательной версии алгоритма, что является очень важным, как было отмечено G. Attardi и С. Traverso 12. Также представлен способ оценить качество распараллеливания без явного вычисления базиса, который может быть использован, как для классического алгоритма Бух-бергера, так и для алгоритма вычисления минимального инволютивного базиса.

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

Первый подход состоит в том, что множество полиномов Р разбивается на несколько подмножеств, которые распределя.тся по доступным рабочим станциям. Обозначим это разбиение как P1,..., Рп. Далее, возможно провести редукцию полинома р на первой рабочей станции по подмножеству Р1. На следующем шаге результат редукции будет отправлен на следующую рабочую станцию, которая содержит подмножество базиса Рг В этот же момент следующий ожидающий редукции полином q будет отослан для редукции по подмножеству P1 на первую рабочую станцию. В этом состоит основная идея алгоритма PipeLine.

Второй подход строго противоположен. Множество Р распределяется по всем рабочим станциям так, что каждая из них содержит его копию, и затем осуществляется одновременная редукция набора полиномов pv..,pn по промежуточному базису Р. Эта стратегия получила название Conveyer.

Эксперименты показали, что производительность алгоритма Conveyer значительно превышает производительность алгоритма PipeLine.

Также представлена псевдо-вероятностная трактовка параллельного ал-

11Faugere J.C. Parallelization of Grobner Basis, Proceedings of PASCO 1994, World Scientific Publ. Сотр.

12 Attardi G., Traverso C. A strategy-accurate parallel Buchberger algorithm, Proceedings of PASCO 1994, World Scientific Publ. Сотр.

горитма вычисления базиса Гребнера, созданная по схеме Faugere. Предположим, что необходимо вычислить базис Гребнера для системы полиномов с целочисленными коэффициентами. Проведем моделирование работы параллельного алгоритма, используя вычисления в кольце полиномов с коэффициентами из конечного поля. Сохраним граф редукций и будем впо-следствие использовать его в процессе вычисления базиса Гребнера с целочисленными коэффициентами. После завершения работы алгоритма, аналогично последовательной псевдо-вероятностной версии алгоритма, необходимо будет осуществить проверку результата и, в случае ошибки, запуск медленной версии или вычислений для другого значения числа р, см. [5, 8].

Четвертая глава.

В четвертой главе дан метод оценки эффективности распараллеливания алгоритмов и приведены результаты оценок для ряда тестовых систем.

При моделировании параллельного алгоритма были приняты следую-

13

щие допущения :

• мы располагаем неограниченным числом процессоров, (на практике необходимое их число не так уж велико, так что это требование сделано исключительно для простоты);

• пренебрегаем временами на пересылку сообщений;

• предполагаем, что все элементарные операции над полиномами, такие, как шаг редукции (не полная редукция!) и вычисление s-полинома выполняются за постоянное время.

Условимся называть полином fi независимым, если полином не был использован в процессе вычисления /¿. Условимся называть полином /¿ почти независимым, если "почти весь" полином /,• может быть вычислен без непосредственного вычисления fi-\. Поясним значение фразы "почти весь". Определим величину р для полинома /,■ следующим образом

О если f¡ является s-полиномом полинома /i_1

^ 11 если индекс i — 1 не присутствует в списке S¡

l3J.-C. Faugere, A New Efficient Algorithm for Computing Grobner bases (F4), Journal of Pure and Applied Algebra, 1999,139, 1-3, 61-88, June

где 5< является списком индексов полиномов, использованных в процессе редукции полинома /¿, в порядке возникновения, и первые два элемента списка являются индексами образующих з-полинома, если полином /( является з-полиномом. Выберем величину О.бб как граничное значение для р, и условимся называть полиномы с р > 0.66 почти независимыми.

Далее, обозначим как Ыаи полное число полиномов, вычисленных в процессе нахождения базиса Гребнера; обозначим как число независимых полиномов и как число почти независимых полиномов. Пусть

Это - в точности число элементарных полиномиальных операций в процессе работы алгоритма. В параллельной версии алгоритма список является стеком полиномов, которые необходимо вычислить для того, чтобы вычисление полинома ^ стало возможным. Допуская, что каждый полином базиса будет вычисляться на выделенном процессоре (для этого потребуется .ЛТай процессоров), можно найти число элементарных полиномиальных операций в процессе работы параллельного алгоритма. Данное число обозначим за ТраГ. Обозначим за .Ртах максимальное количество процессоров, используемых одновременно в процессе работы алгоритма, и за Таг)егаде — среднее количество используемых процессоров.

Полученные результаты показывают, что в процессе вычисления базиса Гребнера эффективно может быть использовано только достаточно небольшое количество процессоров. Как правило, увеличение эффективности невозможно при использовании более чем 5 процессоров. Тем не менее, максимальное число процессоров, использованных в процессе вычисления, достаточно велико - до 194 в задаче Шаз12. Увеличение скорости работы алгоритма в среднем не очень велико, тем не менее значительно. С использованием данного подхода в некоторых задачах вычисления могут быть ускорены на порядок. Теоретические результаты достаточно хорошо согласуются с практическими [6, 7].

Данный подход может быть использован для вычисления инволютивных базисов. След модулярных вычислений может быть использован в процессе вычисления над целыми числами, при условии проверки базиса после завершения вычислений.

Пятая глава.

В пятой главе дано описание реализованного программного комплек-

са для построения инволютивного базиса в дифференциальном модуле в системе компьютерной алгебры Maple.

Понятие инволютивного деления на мономах, на котором основаны алгоритмы построения специальной нередуцированной формы базисов Грёбнера — инволютивных базисов, введено в работах В.П.Гердта и Ю.А.Блинкова14,15. Воспользовавшись хорошо известным соответствием между полиномами и линейными однородными уравнениями в частных производных с постоянными коэффициентами

можно расширить понятие инволютивности на дифференциальные уравнения16*17.

Связь между инволютивными и авторедуцированными базисами Грёбнера исследована в работе А.В.Астрелина, О.Д. Голубицкого, Е.В.Панкратьева18.

Дадим аксиоматическое определение инволютивного деления. Пусть задано множество мономов М = {xf-,..., Х^]^ € N} в кольце полиномов R = К[хи..., Хп] над полем К характеристики 0.

Определение 1. Будем считать заданным инволютивное деление L на М, если для каждого конечного множества мономов U С М и для любого UEU определен подмоноид L(u,U) в М, удовлетворяющий условиям:

(£>) Если u,veU и uL(u, U) f|vL(v, moue vL(v, U) или

(c) Если v e U и v е uL(u, U), то L(v, U) С L(u, U).

(d) Если V С U mo L(u, U) С L(u, V) для всех и £ V.

Элементы L(u, U) будем называть мультипликативными для и. Если W 6 uL{u, U), то и будем называть инволютивным делителем или L-делителем w. В этом случае моном V = w/u назовем L-мультиплика-

14Gerdt V.P., Blinkov Yu.A. Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation 45, 1998, 519-542.

15Gerdt V.P., Blinkov Yu. A. Minimal Involutive Bases, Mathematics and Computers in Simulation, 1998, 45.

16Gerdt V.P. Completion of Linear Differential System to Involution, Computer Algebra in Scientific Computing, V.G.Ganzha, E.W.Mayr and E.V. Vorozhtsov (Eds.), Springer-Verlag, Berlin, 1999, pp.115-137.

17Gerdt V.P. Groebner bases and involutive methods for algebraic and differential equations, Mathematics and Computers in Modelling, 25, No. 8/9, 1997, 75-90.

18Астрелин А.В., Голубицкий О.Д., Панкратьев Е.В., Инволютивные базисы идеалов в кольце многочленов, Программирование, 26 (1): с. 46-52, 2000.

пивным для и. Если и делит w в обычном смысле, но не в инволютивном, назовем v немультипликативным для и.

Определение 2. Деление Жане. Пусть U С. М - конечное множество. Разобьем U на группы, помеченные неотрицательными целыми числами ai,...а,-,(1 < i < п):

[аь...üi] = {ue U\otj = degy(u), 1 < j < i} Тогдаположим X мультипликативной для ueU, если t=l u degj(u) = maxfdeg^v)!*/ € U}

или Perm

г > 1,и 6 [аь... d!j_i] и degj(u) = maxidegjiu)^ e [аь... oü_i]}

Возможно сконструировать достаточно большое количество инволютив-ных делений19. С вычислительной точки зрения, наиболее важной характеристикой деления является количество мультипликативных переменных. Чем больше мультипликативных переменных, тем меньшее количество немультипликативных продолжений мы должны рассмотреть в процессе вычислений. Деление Жане —одно из лучших по этому критерию.

С эффективными алгоритмами построения полиномиальных инволю-тивных базисов можно ознакомиться в работах В.П.Гердта, Ю.А.Блинкова и Д.А.Яновича20'21.

Интересное исследование возможности распараллеливания инволютив-ных алгоритмов проведено в работах В.П.Гердта и Д.А.Яновича.22,23,24

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

l9Gerdt V.P. Involutive Division Technique: Some Generalizations and Optimizations, Journal of Mathematical Sciences 108(6), 2002,1034-1051.

20Gerdt V.P., Blinkov Yu. A., Yanovich D.A., Computation of Janet Bases. LMonomial Bases., Computer Algebra in Scientific Computing / CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), Springer-Verfag, Berlin, 2001, pp. 233-247.

21Gerdt V.P., Blinkov Yu.A. Yanovich D.A., Computation ofJanet Bases. Il.Polynomial Bases., Computer Algebra in Scientific Computing / CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp. 249-263.

22Gerdt V.P., Yanovich D.A., Parallelism in computing Janet bases

23Yanovich D.A. On Parallelization of Involutive Janet Bases Construction Algorithm, Programmirovanie, 2001

24Yanovich D.A. Parallelization of an Algorithm for Computation of Involutive Janet Bases, Programming and Computer Software vol.28, No. 2, 2002

операций умножения и дифференцирования, которые успешно разрешены автором [2].

Шестая глава.

В шестой главе приводится пример применения программного комплекса при вычислении обратимых линейных замен образующих, понижающих дифференциальный размерностный многочлен, в системе уравнений Дирака.

Э. Колчин25 ввел понятие дифференциального размерностного многочлена - математического объекта, соответствующего "жесткости" системы по Эйнштейну26. В диссертации изучаются преобразования системы дифференциальных уравнений, приводящие к уменьшению дифференциального размерностного многочлена, что соответствует увеличению "жесткости" системы по Эйнштейну.

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

и*.....*(«) = trdegF{Q(s)<j>be{s)<f>k)/F

(здесь - множество всех дифференциальных операторов

степени не выше s, trdeg - степень трансцендентности расширения поля). Иными словами, мы присоединяем к исходному полю F все производные элементов с т е п1е-н. и и ищем мощность максимального ал-

гебраически независимого над F множества элементов полученного поля. Для достаточно больших s эта зависимость будет полиномиальной, а точнее говоря, дифференциальный размерностный многочлен является полиномом Гильберта фильтрованного модуля дифференциалов расширения G над F. Этот многочлен содержит некоторые Д-инварианты поля G над F (в частности, степень и старший коэффициент), но сам многочлен может изменяться при выборе другой системы образующих Если степень и>ф11...1фк($) меньше тп, а поле F содержит <C(xi,... ,Xm) (поле рациональных функций от неизвестных Xi,... ,Xm), то в G есть примитив-

25Kolchin E.R. Differential algebra and algebraic groups, New York, Academic Press, 1973 26Эйнштейн А., Собрание научных трудов. Т.2. Работы по теории относительности. 1921-1955, М.: Наука 1966, с. 777-786.

ный элемент £ (т.е. такой, что G = F (£}). Более того, £ можно выбрать в виде к о м £ = Aj^j, Аj £ F,j = 1 ,...,к. и такой за-

мене дифференциальный размерностный многочлен не увеличивается, т.е.

5: Для всех достаточно больших s и поэтому проблема нахо-

ждения минимального дифференциального размерностного Д-многочлена связана с поиском примитивного элемента поля (хотя и не решает ее27'28). И задача вычисления многочлена и поиск £ "в принципе" реша-

ются использованием алгоритма Розенфельда-Грёбнера, входящем в пакет diffag системы компьютерной алгебры Maple- V29 или пакета для вычисления дифференциальных инволютивных базисов Invo, написанным в нашей лаборатории и находящегося в данный момент в стадии тестирования. Однако при реальных вычислениях прямое применение этих алгоритмов не всегда возможно из-за внутренних ограничений системы, влекущих прерывание работы после сообщения "Object too large". Для устранения этой ошибки изготовители системы предложили проводить вычисления на 64-битной платформе. С другой стороны, иногда возможно применение теоретических методов, которые мы продемонстрируем на примере уравнений Дирака.

Мы рассматриваем только линейные дифференциальные уравнения над полем С(а?ь..., хт).

Рассмотрим следующую систему дифференциальных уравнений: 0{ф{) -О, D{<h) = 0, где

^ 8x18x28x28x2 + 8x38x38x38x3 + дхфх^дх^дх^+

^ дх\дх2дхздхз ^ дххдхудх^дхц ^ 8x38x38x48x4

Примитивный элемент для такой системы можно взять следующего вида £ = Ф1 + 2Гз02- Присоединив к исходной системе уравнение

и рассмотрев такой ранжир, что ф\ > Ф2 > £ (чистая лексикографи-ка), применяем алгоритм Розенфельда-Грёбнера и получаем явное выражение для обратной замены (оно содержит производные от степени

27Кондратьева М.В. Описании множества минимальных дифференциальных размерностных многочленов, Вестник МГУ, сер. 7, Математика, механика, 1988, N 1, с. 35-39.

28Кондратьева М.В. Минимальный размерностный полином расширения поля, заданного системой линейных дифференциальных уравнений, Математические заметки, т. 45, N 3, 1989, с. 80-86.

29Boulier F., Lazard D., Ollivier F., Petitot M. Representation for the radical of a finitely generated differential ideal, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, 1995,p.158-166

не выше 12), а также систему определяющих уравнений для новой образующей £ (лидеры полученных Д-многочленов соответствуют множеству {(0,0,8,4) (0,0,11,0) (0,0,9,2)}. Поэтому размерностный многочлен щ(з) равен 8(^3) - 24(^) - 40- 467 и меньше, чем Щ^) = 8(Лд3) — 12(^2) +4. Заметим, что нахождение примитивного эле-

мента не всегда ведет к уменьшению Д-размерностного многочлена, но в некоторых случаях это действительно так.

Теперь рассмотрим систему уравнений Дирака, которая приводится к виду

линейной заменой в множестве дифференцирований Д30 . Для этой системы дифференциальный размерностный многочлен равен 4(*з3) . Можно предложить обратимую замену переменных31

или, разрешая замену относительно

В новых образующих дифференциальный размерностный многочлен равен 4('+3) — 1 , то есть меньше исходного [3,1]. Проверка обратимости и вычисление обращения замен, построение базиса Грёбнера системы, полученной

30Михалев А.В., Панкратьев Е.В. Вычисления в дифференциальной и разностной алгебре, МГУ, 1989

31 Кондратьева М.В., Панкратьев Б.В., Серов Р.Б. Вычисления в дифференциальных и разностных модулях, Аналитические вычисления на ЭВМ и их применение в теоретической физике. Дубна: ОИЯИ, ДП-85-791,1985, с. 208-213.

после замены переменных, и вычисление дифференциального размерност-ного многочлена Колчина были проведены с использованием разработанного в диссертации программного комплекса.

Заключение.

В заключительной главе подводится краткий итог и намечены наиболее перспективные направления для продолжения работ.

Автор выражает глубокую благодарность своему научному руководителю кандидату физико-математических наук Е.В.Панкратьеву и доктору физико-математических наук, профессору В.П.Гердту.

Работы автора по теме диссертации

[1] М.В. Кондратьева, В.А. Митюнин "Вычисление дифференциального размерностного многочлена при заменах образующих в системе уравнений Дирака"// "Программирование", 2001, 1, р. 37-40 (В.А.Митюнину принадлежит вычисление обращения замен переменных и дифференциального размерностного многочлена)

[2] Mityunin V.A. "Implementation of the differential involutive algorithms in the CAS Maple VR5" // Proceedings of IMACS АСА 2000, pp. 3839.

[3] Kondratieva M., 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. (В.А.Митюнину принадлежит вычисление обращения замен переменных и дифференциального размерностного многочлена)

[4] 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 (В.А.Митюнину принадлежат результаты глав 2 и 3)

[5] Mityunin V.A., Semenov A.S. "Parallel Implementations of Honey Strategy Buchberger Algorithm" // Proceedings of "Workshop on Under- and Over-Determined Systems of Algebraic or Differential Equations" (Karlsruhe, Germany, 2002), p.221-225 (В.А.Митюнину принадлежат результаты глав 2 и 5)

[6] Mityunin V.A., Semenov A.S. "An Estimation of the Parallelization Quality of the Involuive Basis Computation Algorithm" // Proceedings of CASC 2002 (В.А.Митюнину принадлежат результаты главы 4)

[7] Mityunin V.A., Pankratev E.V., "Comparison of the parallellization quality of algorithms for computing Groebner and involutive bases using the Faugere method" // Proceedings of IMACS АСА 2003, United States Of America (В.АМитюнину принадлежат результаты главы 2)

[8] Митюнин В.А., Панкратьев Е.В. "Параллельные алгоритмы построения базисов Грёбнера", Международная алгебраическая конференция, посвященная 250-летию Московского Государственного Университета // тезисы докладов, Москва, мех-мат МГУ, 2004, стр. 97-99 (В.А.Митюнину принадлежат результаты главы 1)

»22 932

Издательство ЦПИ при механико-математическом

факультете МГУ им. М.В. Ломоносова.

Подписано в печать /2, / £7^

Формат 60x90 1/16. Усл. печ. л. ¿¿6

Тираж 100 экз. Заказ

Лицензия на издательскую деятельность ИД В 04059,

от 20.02.2001 г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

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 Вычисление размерностного многочлена при заменах образующих в системе уравнений Дирака.

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

В последнее время достигнут значительный прогресс в области систем компьютерной алгебры. Лучшие из таких систем находят себе применение при решении задач, возникающих в различных областях науки. Во многом этот процесс обусловлен ростом производительности вычислительной техники, но он был бы невозможен без значительного улучшения классических алгоритмов. Большую практическую ценность имеют задачи, связанные с факторизацией больших чисел. Значительный прогресс в увеличении скорости вычислений дало применение быстрых алгоритмов умножения.

Одной из важных задач компьютерной алгебры является решение систем нелинейных алгебраических уравнений. На практике часто возникает необходимость решать системы нелинейных алгебраических уравнений с целочисленными коэффициентами. Одним из применяемых методов является построение базисов Гребнера. Теоретическая сложность этого алгоритма, впрочем, такова, что вряд ли можно ожидать успешного решения систем, возникающих на практике. До недавнего вре*ме-ни это действительно было так, и алгоритм мог применяться, главным образом, в академических целях. Однако за последние годы был достигнут значительный прогресс в увеличении производительности алгоритма Бухбергера, что позволило приступить к решению и успешно приводить к стандартному виду системы немыслимого ранее объема. Следует подчеркнуть, что прогресс в этой области был достигнут в гораздо большей степени благодаря улучшению алгоритмов, а не увеличению быстродействия компьютеров. Несмотря на наличие в теории систем уравнений, на которых достигается наихудшая граница сложности базисов Грёбнера, на практике для реальных систем его производительность существенно выше.

В последнее время вызывает сильный интерес альтернативный алгоритм вычисления нередуцированного стандартного базиса, получивший название инволютивного. Полученный инволютивный базис может быть использован при решении систем нелинейных алгебраических уравнений и для их исследования аналогично авторедуцированному базису Гребнера. Основное отличие инволютивного алгоритма вычисления стандартного базиса от алгоритма Бухбергера состоит в модифицированном алгоритме вычисления нормальной формы, который ограничивает набор воз

Ч' можных редукций. Инволютивный алгоритм вычисления стандартного базиса пришел в коммутативную алгебру из диффференциальной алгебры. На данный момент остается открытым вопрос о наиболее эффективном подходе к вычислению стандартных базисов. Существует теория, что инволютивный алгоритм вычисления стандартных базисов значительно эффективнее классического для достаточно больших систем уравнений. В данной работе уделяется большое внимание данному вопросу.

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

Основная проблема, с которой достаточно тяжело справиться состоит в том, что в процессе вычислений начинается взрывной рост целочисленных коэффициентов. Это приводит к очень большим затратам как по процессорному времени, так и по памяти при вычислении базисов для реальных систем. Бороться с этой проблемой можно двумя путями: улучшать алгоритм построения базисов или создавать параллельные версии известных алгоритмов. На первом пути на данном этапе основные продвижения осуществляются с помощью введения новых эвристик, появляющихся в результате появления богатого опыта построения базисов. Вторая область исследована явно недостаточно. К счастью, эти два пути нисколько не противоречат друг другу: большинство улучшений, достигнутых в последовательных алгоритмах, могут быть так или иначе перенесены на параллельные версии. На данный момент мы стоим на пороге, когда увеличение мощности компьютеров с одной стороны и улучшение алгоритмов с другой могут позволить обрабатывать реальные системы алгебраических уравнений.

В качестве примера можно рассмотреть одно из классических в теории базисов Гребнера семейств систем уравнений cyclic. Система cyclic с 4 неизвестными имеет вид fi = a + b + с + d /2 = аЪ + ad + be + cd /3 = abc + abd + aed 4- bed /4 = abed — 1 Базис Гребнера для этой системы имеет вид

91 = c2dQ - c2d2 - d" + 1

92 = c3d2 + c2d3 — c — d gz = bé-h + db-d gA = be - bd5 + c2dA + cd - d6 - d2 g5 = b2 + 2bd + d2 g6 = a + 6 + c + d

Для системы уравнений cyclic от пяти неизвестных базис Гребнера состоит из 11 уравнений дг = е15 + 122е10 — 122е5 — 1 д2- = ЪЫ2еъ - 55d2 - 2de11 - 23lde6 + 2Ше - 8е12 - 979е7 + 987е2 дг = 6d7 + 57dQeQ - 39d6e + 25d5e7 - 19d5e2 - 5d4e8 + 5d4e3 - 8d3e9 +

8f/3e4 - 2d2e10 + Ш2е5 - 18c/2 - 18de6 - 6e7 = 360150ce5 - 360150c + 71540d9e2 - 110722d8e3 - 1744327dV

- 3078595d6e5 + 233730d6 + 219158d5e6 - 1058999d5e + 23662Ш4е7

- 2437750d4e2 + 1281458d3e8 - 1170736d3e3 + 200573d2e9 + 1543754d2e4 + + 2844865de5 + 839841e6 gb = 360150cd — 360150ce6 — 71540d10e2 + 110722d9e3 + 1744327c?8 e4 +

3064189d7e5 - 233730d7 + 313864d6e6 + 1058999d6e - 795956dse7 +

2437750d5e2 - 1403909d4e8 + 1293187d4e3 - 1360256d3e9 - 744221d3e4

- 410571d2e10 - 2059738d2e5 - 1372863de6 - 1570254e7 и т.д. Для системы уравнений cyclic от шести неизвестных базис Гребнера состоит из 17 уравнений, длина коэффициентов которых превышает 100 десятичных цифр m

7 Заключение

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

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

1. Gerdt V.P. Completion of Linear Differential System to Involution // Computer Algebra in Scientific Computing, V.G.Ganzha, E.W.Mayr and E.V. Vorozhtsov (Eds.), Springer-Verlag, Berlin, 1999, pp. 115-137.

2. Gerdt V.P. On the Relation Between Pommaret and Janet Bases // Computer Algebra in Scientific Computing / CASC 2000, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 2000, pp.164-171.

3. Gerdt V.P. Invoiutive Division Technique: Some Generalizations and Optimizations // Journal of Mathematical Sciences 108(6), 2002, 10341051. URL: http://arXiv.org/abs/math.SC/9912030.

4. Gerdt V.P. Groebner bases and invoiutive methods for algebraic and differential equations // Mathematics and Computers in Modelling, 25, No. 8/9, 1997, 75-90.

5. Gerdt V.P., Blinkov Yu. A. Minimal Invoiutive Bases // Mathematics and Computers in Simulation, 1998, 45.

6. Gerdt V.P., Blinkov Yu.A., Yanovich D.A., Computation of Janet Bases. I.Monomial Bases. // Computer Algebra in Scientific Computing / CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp. 233-247.

7. Gerdt V.P., Blinkov Yu.A. Yanovich D.A., Computation of Janet Bases. ILPolynomial Bases. // Computer Algebra in Scientific Computing /

8. CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp. 249-263.

9. Gerdt V.P., Blinkov Yu.A. Involutive Polynomial Bases // Publication IT-271, Laboratoire d'Informatique Fondamentale de Lille, Lille, 1995

10. Gerdt V.P., Blinkov Yu.A. Involutive Bases of Polynomial Ideals // Mathematics and Computers in Simulation 45, 1998, 519-542.

11. Gerdt V.P., Blinkov Yu.A. Minimal Involutive Bases // Mathematics and Computers in Simulation 45, 1998, 543-560

12. Yanovich D.A. On Parallelization of Involutive Janet Bases Construction Algorithm // Programming and Computer Software, 2001

13. Yanovich D.A. Parallelization of an Algorithm for Computation of Involutive Janet Bases //Programming and Computer Software vol.28, No. 2, 2002

14. Siegl K. A Parallel Factorization Tree Gröbner Basis Algorithm // Proceedings of PASCO 1994, World Scientific Publ. Comp.

15. Reeves A.A. A Parallel Implementation of Buchberger's Algorithm over Zp for p < 31991 // J.Symbolic Computation, 1998, 229-244.

16. Gebauer R., Möller H.M. On an Installation of Buchberger's Algorithm // J. Symbolic Computation, 1988, 6, 275-286.

17. Giovanni A., Mora T., Niesi G., Robbiano L., Traverso C. One sugar cube, please or Selection Strategies in Buchberger Algorithm // Proceedings of ISSAC 1991, ACM, 1991, 49-54

18. Faugere J.C. Parallelization of Gröbner Basis // Proceedings of PASCO 1994, World Scientific Publ. Comp.

19. Attardi G., Traverso C. A strategy-accurate parallel Buchberger algorithm // Proceedings of PASCO 1994, World Scientific Publ. Comp.

20. Collart S., Kalkbrener M., Mall D. The Gröbner walk // Dept. of Math, Swiss Federal Inst, of Tech, 8092 Z urich, Switzerland

21. Amrhein B., Gloor O. The fractal walk // Groebner bases and applications, Cambridge University Press, 1998

22. Голубицкий О.Д. Инволютивный маршрут Гребнера // Фундаментальная и прикладная математика, том 7, 4, 993-1001, 2001.

23. Buchberger В. A Theoretical basis for the reduction of polynomials to canonical form // ACM SIGSAM Bulletin Vol. 10, No. 3, 19 29, 1976.

24. Buchberger B. Grobner Bases : An Algorithmic Method in Polynomial Ideal Theory // In N. K. Bose, editor, Multidimensional Systems Theory, pages 184-232. U. Reidel Publishing Company, 1985.

25. Moller H.M., Mora Т., Traverso C. Grobner bases computation using syzygies. // Proc. of ISSAC 1992.

26. Mora Т., Pfister G., Traverso C. An introduction to the tangent cone algorithm // Advances in Computing research, Issues in Robotics and nonlinear geometry, 1992, 6, 199-570.

27. Кондратьева M.B., Митюнин В.А. "Вычисление дифференциального размерностного многочлена при заменах образующих в системе уравнений Дирака"// "Программирование", 2001, 1, р. 37-40

28. Mityunin V.A. "Implementation of the differential involutive algorithms in the CAS Maple VR5",

29. Proceedings of IMACS АСА 2000, pp. 38-39.

30. Kondratieva M., Makarevich N., Mityunin V. Computation of primitive element in differential module // Proceedings of IMACS АСА 2000, p. 28-29. Add. Thesises 12-th International Conference FPSAC'00, pp. 2324.

31. Mityunin V.A., Semenov A.S. Parallel Implementations of Honey Strategy Buchberger Algorithm // Proceedings of "Workshop on Under-and Over-Determined Systems of Algebraic or Differential Equations, Karlsruhe, Germany, 2002.

32. Mityunin V.A., Zobnin A.I., Ovchinnikov A.I., Semenov A.S. Involutive and Classical Grobner Bases Construction from The Computational Viewpoint // Proceedings of СААР 2001, , p.221-230.

33. Mityunin VA., Semenov A.S. "An Estimation of the Parallelization Quality of the Involuive Basis Computation Algorithm"// Proceedings of CASC 2002

34. Митюнин В.А., Панкратьев E.B "Параллельные алгоритмы построения базисов Гребнера"// Международная алгебраическая конференция, посвященная 250-летию Московского Государственного Университета, тезисы докладов, Москва, мех-мат МГУ, 2004, стр. 97-99

35. Boulier F., Lazard D., Ollivier F., Petitot M. Representation for the radical of a finitely generated differential ideal // Proceedings of the 1995 international symposium on Symbolic and algebraic computation, 1995, p.158-166

36. Эйнштейн А., Собрание научных трудов. T.2. Работы по теории относительности. 1921-1955 // М.: Наука 1966, с. 777-786.

37. Астрелин А.В., Голубицкий О.Д., Панкратьев Е.В., Инволютивные базисы идеалов в кольце многочленов // Программирование, 26 (1): с. 46-52, 2000

38. Kondratieva M.V., Levin А.В., Mikhalev A.V., Pankratiev E.V., Differential and Difference Dimension Polynomial // Kluwer Academic Publishers, Dordrecht Hardbound, November 1998.

39. Михалев А.В., Панкратьев E.B. Вычисления в дифференциальной и разностной алгебре // МГУ, 1989

40. Михалев А.В., Панкратьев Е.В. Компьютерная Алгебра. Факторизация многочленов. Изд-во МГУ, 1991.

41. Кондратьева М.В., Панкратьев Е.В., Серов Р.Е. Вычисления в дифференциальных и разностных модулях. // Аналитические вычисления на ЭВМ и их применение в теоретической физике. Дубна: ОИ-ЯИ, ДП-85-791, 1985, с. 208-213.

42. Кондратьева М.В. Описание множества минимальных дифференциальных размерностных многочленов. // Вестник МГУ, сер. 7, Математика, механика, 1988, N 1, с. 35-39.

43. Кондратьева М.В. Минимальный размерностный полином расширения поля, заданного системой линейных дифференциальных уравнений. // Математические заметки, т. 45, N 3, 1989, с. 80-86.

44. Quoc-Nam Tran Parallel computation and Groebner bases: an application for converting bases with the groebner walk // Groebner bases and applications, Cambridge University Press, 1998

45. Капланский И. Введение в дифференциальную алгебру // Издательство иностранной литературы, Москва, 1959

46. Kolchin E.R. Differential algebra and algebraic groups // New York, Academic Press, 1973

47. High Performance Libraries // http://www.hipilib.de/

48. Verification of Riemann's Hypothesis, ZetaGrid // http://www.zetagrid.net/

49. Bachmann 0., Schonemann H. Monomial Representations for Grobner Bases Computations / / Centre for Computer Algebra Department of Mathematics University of Kaiserslautern, 1998, http://www.mathematik.uni-kl.de/ zca/Reportsonca/18/paperhtml/paper.html

50. Bachmann O., Grabe H. The SymbolicData Project // Reports On Computer Algebra, Univ. Kaiserslautern, 27/2000 http://dol.uni-leipzig.de/pub/2000-5

51. Bini D.A., Mourrain В., Polynomial test suite // http://www-sop.inria.fr/saga/POL/

52. Robbiano, L. Term Orderings on the Polynomial Ring //In Proceedings of EUROCAL 85, Lecture Notes in Computer Science 204 (1985), pp. 513-517.