Маршруты Грёбнера тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Московский государственный университет им. М.В. Ломоносова

Механико-математический факультет

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

Голубицкий Олег Дмитриевич

МАРШРУТЫ ГРЁБНЕРА

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

АВТОРЕФЕРАТ

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

МОСКВА - 2003

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук, ведущий научный сотрудник Е.В. Панкратьев

доктор физико-математических наук, профессор С.А. Абрамов

кандидат физико-математических наук, доцент И.Н. Балаба Объединенный институт ядерных исследований РАН

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

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

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

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

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

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

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

Идея преобразования системы в эквивалентную каноническую присутствует и в работах Жане, Томаса и Поммаре1'2,3 по системам линейных уравнений в частных производных. В этих работах приведение системы к каноническому виду называется приведением в инволюцию. В работах Гердта, Жаркова и Блинкова (например4 ) разработана теория инволю-тивных делений и инволютивных базисов для систем многочленов. Инво-лютивные базисы являются нередуцированными базисами Грёбнера5,6 и вместе с тем имеют дополнительные полезные свойства7 . Вид и сложность

'Janet, M. Sur los Systèmes d'Equationcs aux Dérivées Partielles. J.Math. Pure at Appl. 3,65-151,1920.

2Thomas, J. Differential Systems. American Mathematical Society, New York, 1937.

3Pommarct J.F., Systems of Partial Differential Equations and Lie Pseudogroups, Gordon fc Breach, New York, 1978.

■•Gerdt V.P., Blinkov Yu.A., Involutive Bases of Polynomial Ideals. Preprint-Nr.1/1996, Naturwisscnschaftlich-Theorcti6hes Zentrum, University of Leipzig; Math. Comp. Sim. 45, 519-542, 1998.

'Zharkov, A.Yu., Blmkov, Yu.A. Involutive Approach to Investigating Polynomial Systems. In: Proceedings of SC 95, International IMACS Symposium on Symbolic Computation: New Trends and Developments (Lille, June 14-17, 1993),. Math. Comp. Simul. 42, 323-332,1996.

6Zharkov, A.Yu., Blinkov, Yu.A. Involutive Bases of Zero-Dimensional Ide- als. Preprint No. E5 94-318, Joint Institute for Nuclear Research, Dubna, 1994.

'Zharkov A.Yu., Solving Zero-Dimensional Involutive Systems. Algorithms in Algebraic Geometry and Applications, L. Gonzales-Vega, T. Recio (cds). Progress in Mathematics, Vol. 143, BirkMuser, Basel, pp

389-399,1996.

»>GC. НАЦИОНАЛbi>'. БИБЛИОТЕКА

построения инволютивных базисов зависит от инволютивного деления, грамотный выбор которого позволяет ускорить алгоритм этого построения8 . Эксперименты показывают, что во многих случаях инволютивный алгоритм работает быстрее, чем алгоритм Бухбергера.

Существует совершенно иной метод усовершенствования алгоритма Бухбергера для построения базисов Грёбнера относительно лексикографического порядка, известный под названием маршрута Грёбнера (Gröbner Walk) Этот метод основан на известном наблюдении, что время работы алгоритма Бухбергера существенно зависит от выбора отношения порядка на мономах. Например, построение базиса Грёбнера относительно порядка общей степени, как правило, гораздо более эффективно, чем построение базиса для лексикографического порядка. Метод маршрута Грёбнера, впервые предложенный Коллартом, Калкбренером и Маллом в работе9 , позволяет эффективно преобразовывать базис Грёбнера относительно одного порядка на мономах в базис относительно любого другого порядка. Эксперименты показывают10 , что такое косвенное построение может оказаться гораздо эффективнее прямого построения лексикографического базиса Грёбнера.

Для систем нелинейных уравнений в частных производных также существует подход, связанный с приведением системы к каноническому виду и основанный на понятиях из дифференциальной алгебры. Основы дифференциальной алгебры, включая понятие кольца дифференциальных многочленов, дифференциального идеала и характеристического множества, были заложены Риттом11 и Колчином12 . Дальнейшее развитие дифференциальная алгебра получила в работах ряда авторов второй половины XX века. В частности, была разработана теория дифференциальных и разностных размерностных многочленов, с которой можно ознакомиться по монографии Кондратьевой, Левина, Михалева и Панкратьева13 . Характеристические множества дифференциальных идеалов играют роль, сходную с ролью базисов Грёбнера для полиномиальных идеалов. Однако, некоторые важные свойства базисов Грёбнера не переносятся на дифференциальный случай13 . Например, характеристическое множество дифференциального

'Gerdt V.P., Involutive Division Technique: Some Generalizations and Optimizations. Preprint of the Joint Institute for Nuclear Research, Dubna, E5-98-151, 1998.

"Collart S., Kalkbrener M., Mall D. The Gröbner walk. Dept. of Math., Swiss Federal Inst, of Tech, 8092 Zürich, Switzerland, 1993.

I0Amrhcin В , Gloor O., Küchlin W. How fast docs the walk run. Proc of RWCA '96,1996.

"Ritt J. Differential Algebra. Dover, 1950.

12Kolchm E.R. Differential Algebra and Algebraic Groups Academic press, 1973.

13Kondraticva M.V., Levin A.B., Mikhalev A.V., Pankratiev E.V. Differential and Difference Dimension Polynomials Klüver publishers, 1999.

идеала, вообще говоря, может не порождать этот идеал.

Задача построения характеристических множеств гораздо сложнее ее полиномиального аналога. В случае простых дифференциальных идеалов эта задача может быть решена с помощью алгоритма Розенфельда-Грёбне-ра14 или специализированного алгоритма Розенфельда-Грёбнера15 . Однако, в обоих случаях искомое характеристическое множество строится путем прямого вычисления. Такой подход может оказаться неэффективным, особенно в случае исключающего ранжира. Для решения этой проблемы Булье16 предложил алгоритм DFGLM, являющийся дифференциальным обобщением алгоритма FGLM17 (последний алгоритм был разработан для ускорения подсчета полиномиальных базисов Грёбнера для лексикографического порядка в случае нульмерных идеалов). Однако, как отмечено в работе16 , этот алгоритм применим только к системам, решения которых параметризованы конечным семейством параметров. Алгоритм Кэли, также предложенный в работе16 , применим к произвольным дифференциальным системам, но, как отмечено в16 , менее эффективен, чем DFGLM.

Случай конечного семейства параметров для дифференциальных систем аналогичен случаю нульмерного идеала в кольце многочленов R, который является необходимым условием для применения алгоритма FGLM. Но даже при таком ограничении сложность алгоритма растет с ростом размерности векторного фактор-пространства R/I. Результаты экспериментов, приведенные в18'19 , показывают, что, за исключением простейших случаев, маршрут Грёбнера20 не менее эффективен, чем FGLM, а с ростом размерности R/I первый становится гораздо более эффективным. Кроме того, метод маршрута Грёбнера применим к произвольным полиномиальным идеалам. Данное наблюдение позволяет предположить, что обобщение метода маршрута Грёбнера на дифференциальный случай будет обладать теми же преимуществами по сравнению с алгоритмом16 .

Цель работы. Целью настоящей работы является исследование связи

"Boulier F., Lazard D., Ollivicr F., Pctitot M. Representation for the radical of a fimtcly generated differential ideal. Proc. ISAAC 1995, ACM Press, 158-166.

"Boulier F., Lern aire F., Maza M.M. PARDI! Publication LIFL 2001-01, 2001.

"Boulier F. Efficient computation of regular differential systems Ъу change of rankings using Kahler differentials. Tech. rep., Université Lille I, 1999.

,TFaugirc J.C., Gianni P., Lazard D., Mora T. Efficient computation of zero-dimensional Gröbncr bases by change of ordering. JSC, 16-329-344,1993.

"Amrhein В., Gloor O., Küchlin W. How fast docs the walk run. Proc. of RWCA '96, 1996

,sAmrhein В., Gloor O., Kùchlin W. Walking faster. Proc of DISCO'96, Karlsruhe, Germany, 1996.

'"Collart S , Kalkbrcner M., Mall D. The Gröbncr walk. Dept. of Math., Swiss Federal Inst, of Tech, 8092 Zürich, Switzerland, 1993

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

Научная новизна. Научная новизна данной работы состоит в следующем:

1. Понятия базисов Грёбнера и инволютивных базисов изложены в рамках общей теории схем симплификации и стандартных базисов21 .

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

3. Метод маршрута Грёбнера перенесен на случай инволютивных базисов.

4. Алгоритм Бухбергера, алгоритм построения инволютивных базисов и методы маршрута Грёбнера и инволютивного маршрута Грёбнера реализованы в системе компьютерной алгебры Maple, и проведено экспериментальное сравнение их эффективности.

5. Метод маршрута Грёбнера перенесен на дифференциальный случай. Точнее, предложен алгоритм, который по характеристическому множеству А дифференциального идеала I относительно ранжира <i строит характеристическое множество В идеала I относительно другого ранжира <2- Данный алгоритм применим в случае простых дифференциальных идеалов и ранжиров Рикье22'23'24 , которые включают порядковые и исключающие ранжиры25'16 . Теорема Мора и Робиа-но о конечности разбиений Грёбнера26'27 не обобщается напрямую на случай дифференциальных идеалов, для которого приводится пример бесконечного разбиения Грёбнера. Тем не менее доказывается, что дифференциальный маршрут Грёбнера всегда конечен.

21 Латышев В.Н., Комбинаторная теория колец Стандартные базисы М.: МГУ, 1988.

22Riquicr С. Lea systèmes d 'equations aux dérivées partielles. Gauthier-Villars, Paris, 1910.

23Rust C.J., Reid G.J. Rankings of partial derivatives. 1998.

"Wcispfcnning V. Differential term-orders. Proc. ofISAAC'93. Kiev, ACM press, 1993.

26Kondraticva M.V., Levin A.B., Mikhalcv A.V., Pankratiev E.V. Differential and Difference Dimension Polynomials Klüver publishers, 1999.

2sMora T., Robbiano L The Gröbncr fan of an ideal. JSC, 6:183-208,1988.

270'Shca D. Gröbncr fan and walk. Springer-Verlag electronic production, 2001.

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

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

Апробация работы. Основные результаты диссертации докладывались на Международной конференции по приложениям компьютерной алгебры IMACS АСА в 1998 г., Международной алгебраической конференции по случаю 90-летия А.Г. Куроша в 1998 г., Международном алгебраическом семинаре, посвященном 70-летию кафедры Еысшей алгебры МГУ в 1999 г., Ежегодном совместном семинаре МГУ и ОИЯИ РАН по компьютерной алгебре в 1999 г., Международном семинаре по компьютерной алгебре и приложениям в физике в 2001 г., и Рейнском семинаре по компьютерной алгебре в 2002 г.

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

Структура и объем диссертации. Диссертационная работа состоит из четырех глав, первая из которых является вводной, и одного приложения и содержит библиографию (56 наименований). Общий объем диссертации составляет 57 страниц. Структура работы отражена в оглавлении.

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

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

Автор признателен Бруно Бухбергеру и Францу Винклеру за исклю-

читальную возможность, предоставленную ему приглашением на курсы и конференцию по базисам Гребнера в институте RISC-Linz, Австрия, в январе 1998 г. Лекции Виктора Николаевича Латышева о приложениях высшей алгебры помогли автору проанализировать и выразить результаты в более общей форме,

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

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

Введение (первая глава). Во введении изложена краткая история вопроса, показана актуальность темы и сформулированы основные результаты.

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

Теорема 1 Последовательности нормальных форм, вычисляемые алгоритмом Бухбергера и инволютивным алгоритмом, совпадают.

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

Третья глава. Известно, что процесс построения базиса Гребнера, равно как и сам базис, существенно зависит от выбранного отношения порядка на множестве мономов. Как правило, вычисление базиса Гребнера относительно лексикографического порядка требует гораздо больше времени, чем для порядка общей степени. В связи с этим в работе17 (см. также алгоритм РСЬМ, реализованный в системе компьютерной алгебры Мар1е-У.5). предложен быстрый алгоритм перехода от одного порядка к другому для нульмерных идеалов, основанный на методах линейной алгебры. Другой подход основан на понятии разбиения Гребнера пространства весовых векторов, при котором два вектора относятся к одному классу тогда и только тогда, когда редуцированные базисы Гребнера относительно соответствующих отношений порядка на мономах совпадают. Далее предлагается алгоритм, переводящий базис Гребнера от данного класса к соседнему, и так

далее — к произвольному порядку на мономах. Этот метод и называется маршрутом Гребнера (Grobner Walk)9.

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

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

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

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

Теорема 2 Для любого дифференциального идеала I С K.{U}: семейство множеств лидеров всевозможных характеристических множеств этого идеала, Ld(I), конечно.

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

Далее приводятся леммы, на основе которых строится шаг маршрута Грёбнера:

Лемма 1 Пусть < — ранжир, и весовой вектор w согласован с <. Пусть Л — характеристическое множество идеала I относительно <. Тогда множество начальных форм характеристического множества, inw(.4), является характеристическим для множества начальных форм идеала, mw(7), относительно <.

Преобразование характеристического множества, соответствующее одному шагу маршрута, приведено в следующей лемме.

Лемма 2 Пусть Лои — характеристическое множество идеала I относительно ранжира <0id- Пусть w — весовой вектор, согласованный с

<оЫ и удовлетворяющий следующему условию: для всех А € Лм, $ € Э, вф 1,

¿её„(1А) < <^(£0 < (1)

где инициал и сепаранта берутся относительно ранжира <0ы?Ъ Пусть <пеш ~ другой ранжир, согласованный с v?. По лемме 1, поскольку у/ согласован с <м, множество пьД.Дои) является характеристическим для т,, (I) относительно <ы<г■ Пусть В = {¿1,..., В3} — характеристическое множество для т^,(1) относительно <„еш- Тогда существует эффективная процедура построения характеристического множества Лпеш для I относительно <пеш.

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

Приложение. В приложении приводится реализация инволютивного маршрута Грёбнера в системе Мар1е, а также результаты экспериментального сравнения производительности четырех алгоритмов: построение базиса Грёбнера (алгоритм 8Е1етеМзСотр1еЫоп(Р,ЕЛц)), построение инволютивного базиса (алгоритм 1пуоШюеСотр1еИоп), обычного маршрута Грёбнера и инволютивного маршрута Грёбнера. Из этих результатов сделаны следующие выводы: маршрут Грёбнера почти всегда быстрее прямого вычисления для лексикографического порядка с помощью алгоритма Бухбергера. Даже если это не так, время вычисления промежуточных базисов все равно меньше, а остальным временем, в основном затрачиваемым на вычисление точек пересечения с границами конусов, можно пренебречь по сравнению со временем вычисления базисов. Кроме того, в тех экспериментах, где маршрут Гребнера не дал улучшения по сравнению с прямым алгоритмом, инволютивный маршрут Грёбнера оказался все же быстрее. Поэтому, имея в распоряжении быструю реализацию алгоритма построения инволютивного базиса, мы можем применить к ней технику инволютивного маршрута Гребнера и получить алгоритм, который не только быстро строит базисы Гребнера, но и автоматически переносим на случай линейных дифференциальных уравнений и наследует все преимущества инволютивного подхода.

г8Если условия (1) не выполнены, преобразование, описанное ниже, не может быть произведено. В этом случае можно либо построить характеристическое множество относительно <„,„, напрямую, либо найти другой весовой вектор, для которого условия (1) выполняются.

р 1 6 0 7 9

-fy

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

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

(Основной результат сформулирован в теореме 1. Гипотеза и идея принадлежат Е.В. Панкратьеву и А.В. Астрелину. Доказательство основного результата и двух вспомогательных лемм реализовано О.Д. Голу-бицким)

[2] Астрелин А.В., Голубицкий О.Д., Панкратьев Е.В., Сравнение алгоритмов построения базисов Гребнера и инволютивных базисов, Международный алгебраический семинар, посвященный 70-летию кафедры высшей алгебры МГУ, Тезисы докладов, с. 9-10, 1999.

(О.Д. Голубицкий реализовал вышеуказанные алгоритмы и провел их экспериментальное сравнение)

[3] Голубицкий О.Д., Инволютивный маршрут Грёбнера, Фундаментальная и прикладная математика, 7 (4): pp. 993-1001, 2001.

[4] Astrelin, А. V., Golubitsky О. D., Pankratiev Е. V., Grdbner bases and involutive bases, in Algebra. Proc. International Algebraic Conference on the Occation of the 90th Birthday of A. G. Kurosh, Moscow, Russia, May 25-30, 1998. Berlin, Walter de Gruyter, pp. 49-55, 2000.

(Основной результат сформулирован в предложении 1. Гипотеза и идея принадлежат Е.В. Панкратьеву и А.В. Астрелину. Доказательство реализовано О.Д. Голубицким)

[5] Golubitsky О., Transformation of characteristic sets from one ranking to another, Proceedings of 8th Rhine Workshop on Computer Algebra, Mannheim, Germany, pp. 225-236, 2002.

[6] Golubitsky O., Differential Grdbner Walk, Proceedings of International Workshop on Computer Algebra and its Application to Physics (СААР),

2000.

Dubna, Russia, pp. 114-126, 2001.

1 Введение

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

1.2 Цель работы

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

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

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

1.6 Публикации.

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

1.8 Благодарности.

2 Базисы Гребнера и инволютивные базисы

2.1 Основные понятия коммутативной алгебры.

2.2 Схемы симплификации и стандартные множества.

2.3 Стандартные базисы.

2.4 Инволютивные деления.

2.5 Инволютивные базисы.

2.6 Сравнение алгоритмов Бухбергера и инволютивного алгоритма

3 Инволютивный маршрут Гребнера

3.1 Допустимые отношения порядка и весовые вектора

3.2 Шаг инволютивого маршрута Гребнера.

3.3 Конусы Гребнера и инволютивный маршрут Гребнера

4 Дифференциальный маршрут Гребнера

4.1 Основные понятия дифференциальной алгебры

4.2 Ранжиры.

4.3 Характеристические множества.

4.4 Лидеры характеристических множеств

4.5 Дифференциальное разбиение Гребнера.

4.6 Преобразование характеристических множеств.

4.7 Дифференциальный маршрут Гребнера.

4.8 Конечность дифференциального маршрута Гребнера

4.9 Нерешенные проблемы.

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

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

Первый алгоритм построения базиса Грёбнера был разработан и реа- ■ лизован Бухбергером в 1965 г. Его основная идея заключается в преобразовании исходной системы многочленов в эквивалентную каноническую систему. Решение системы линейных уравнений методом Гаусса и нахождение наибольшего общего делителя многочленов от одной переменной с помощью алгоритма Евклида являются частными случаями алгоритма Бухбергера. В общем случае алгоритм Бухбергера имеет высокую сложность, для которой не известно хорошей теоретической оценки — наоборот, известны примеры систем, для которых базис Гребнера имеет экспоненциальный размер. Поэтому становится важной разработка различных методов, позволяющих усовершенствовать алгоритм Бухбергера на практике.

Идея преобразования системы в эквивалентную каноническую присутствует и в работах Жане, Томаса и Поммаре [33, 46, 41] по системам линейных уравнений в частных производных. В этих работах приведение системы к каноническому виду называется приведением в инволюцию. В работах Гердта, Жаркова и Блинкова (например [22]) разработана теория инволютивных делений и инволютивных базисов для систем многочленов. Инволютивные базисы являются нередуцированными базисами Грёбнера [49, 50] и вместе с тем имеют дополнительные полезные свойства [48]. Вид и сложность построения инволютивных базисов зависит от инволютивного деления, грамотный выбор которого позволяет ускорить алгоритм этого построения [23]. Эксперименты показывают, что во многих случаях инволютивный алгоритм работает быстрее, чем алгоритм Бухбергера.

Существует совершенно иной метод усовершенствования алгоритма

Бухбергера для построения базисов Грёбнера относительно лексикографического порядка, известный под названием маршрута Грёбнера (Grob-ner Walk). Этот метод основан на известном наблюдении, что время работы алгоритма Бухбергера существенно зависит от выбора отношения порядка на мономах. Например, построение базиса Грёбнера относительно порядка общей степени, как правило, гораздо более эффективно, чем построение базиса для лексикографического порядка. Метод маршрута Грёбнера, впервые предложенный Коллартом, Калкбренером и Маллом в работе [19], позволяет эффективно преобразовывать базис Грёбнера относительно одного порядка на мономах в базис относительно любого другого порядка. Эксперименты показывают [6], что такое косвенное построение может оказаться гораздо эффективнее прямого построения лексикографического базиса Грёбнера.

Для систем нелинейных уравнений в частных производных также существует подход, связанный с приведением системы к каноническому виду и основанный на понятиях из дифференциальной алгебры. Основы дифференциальной алгебры, включая понятие кольца дифференциальных многочленов, дифференциального идеала и характеристического множества, были заложены Риттом [43] и Колчином [34]. Дальнейшее развитие дифференциальная алгебра получила в работах ряда авторов второй половины XX века. В частности, была разработана теория дифференциальных и разностных размерностных многочленов, с которой можно ознакомиться по монографии Кондратьевой, Левина, Михалева и Панкратьева [35]. Характеристические множества дифференциальных идеалов играют роль, сходную с ролью базисов Грёбнера для полиномиальных идеалов. Однако, некоторые важные свойства базисов Грёбнера не переносятся на дифференциальный случай [35]. Например, характеристическое множество дифференциального идеала, вообще говоря, может не порождать этот идеал.

Задача построения характеристических множеств гораздо сложнее ее полиномиального аналога. В случае простых дифференциальных идеалов эта задача может быть решена с помощью алгоритма Розенфельда-Грёбнера [16] или специализированного алгоритма Розенфельда-Грёбне-ра [15]. Однако, в обоих случаях искомое характеристическое множество строится путем прямого вычисления. Такой подход может оказаться неэффективным, особенно в случае исключающего ранжира. Для решения этой проблемы Булье [14] предложил алгоритм DFGLM, являющийся дифференциальным обобщением алгоритма FGLM [20] (последний алгоритм был разработан для ускорения подсчета полиномиальных базисов Грёбнера для лексикографического порядка в случае нульмерных идеалов). Однако, как отмечено в работе [14], этот алгоритм применим только к системам, решения которых параметризованы конечным семейством параметров. Алгоритм Кэли, также предложенный в работе [14], применим к произвольным дифференциальным системам, но, как отмечено в [14], менее эффективен, чем DFGLM.

Случай конечного семейства параметров для дифференциальных систем аналогичен случаю нульмерного идеала в кольце многочленов R, который является необходимым условием для применения алгоритма FGLM. Но даже при таком ограничении сложность алгоритма растет с: ростом размерности векторного фактор-пространства R/L Результаты экспериментов, приведенные в [6, 7], показывают, что, за исключением простейших случаев, маршрут Грёбнера [19] не менее эффективен, чем FGLM, а с ростом размерности R/I первый становится гораздо более эффективным. Кроме того, метод маршрута Грёбнера применим к произвольным полиномиальным идеалам. Данное наблюдение позволяет предположить, что обобщение метода маршрута Грёбнера на дифференциальный случай будет обладать теми же преимуществами по сравнению с алгоритмом [14].

1.2 Цель работы

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

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

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

1. Понятия базисов Грёбнера и инволютивных базисов изложены в рамках общей теории схем симплификации и стандартных базисов [11

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

3. Метод маршрута Грёбнера перенесен на случай инволютивных базисов.

4. Алгоритм Бухбергера, алгоритм построения инволютивных базисов и методы маршрута Грёбнера и инволютивного маршрута Грёбнера реализованы в системе компьютерной алгебры Maple, и проведено экспериментальное сравнение их эффективности.

5. Метод маршрута Грёбнера перенесен на дифференциальный случай. Точнее, предложен алгоритм, который по характеристическому множеству Л дифференциального идеала I относительно ранжира <1 строит характеристическое множество В идеала / относительно другого ранжира <2- Данный алгоритм применим в случае простых дифференциальных идеалов и ранжиров Рикье [42, 44, 47], которые включают порядковые и исключающие ранжиры [35, 14]. Теорема Мора и Робиано о конечности разбиений Грёбнера [37, 38] не обобщается напрямую на случай дифференциальных идеалов, для которого приводится пример бесконечного разбиения Грёбнера. Тем не менее доказывается, что дифференциальный маршрут Грёбнера всегда конечен.

1. Boulier F. Efficient computation of regular differential systems by change of rankings using Kahler differentials. Tech. rep., Université Lille I, 1999.

2. Boulier F., Lemaire F., Maza M.M. PARDI! Publication LIFL 2001-01, 2001.

3. Boulier F., Lazard D., Ollivier F., Petitot M. Representation for the radical of a finitely generated differential ideal. Proc. ISAAC 1995, ACM Press, 158-166.

4. Buçhberger B. An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal (in German). PhD Thesis, Univ. of Insbruck, Inst, for Math, 1965.

5. Carra-Ferro G., Sit W.Y. On term-orderings and rankings. Lecture notes in pure and applied Math., Computational Algebra, Dekker, 151, 1992.

6. Collart S., Kalkbrener M., Mall D. The Grôbner walk. Dept. of Math., Swiss Federal Inst, of Tech, 8092 Zurich, Switzerland, 1993.

7. Faugére J.C., Gianni P., Lazard D., Mora T. Efficient computation of zero-dimensional Grôbner bases by change of ordering. JSC, 16:329344, 1993.

8. Gerdt V.P., Grôbner Bases and Involutive Methods for Algebraic and Differential Equations, Mathematics and Computers in Modelling, 25, No, 8/9, 75-90, 1997.

9. Gerdt V.P., Blinkov Yu.A., Involutive Bases of Polynomial Ideals. Preprint-Nr.1/1996, Naturwissenschaftlich-Theoretishes Zentrum, University of Leipzig; Math. Comp. Sim. 45, 519-542, 1998.

10. Gerdt V.P., Involutive Division Technique: Some Generalizations and Optimizations. Preprint of the Joint Institute for Nuclear Research, Dubna, E5-98-151, 1998.

11. Gerdt V.P., Blinkov Yu.A., Minimal Involutive Bases, Math. Comp. Sim. 45, 543-560, 1998.

12. Gerdt V.P., Blinkov Yu.A., Involutive Monomial Divisions, Programming and Computer Software, 24, 22-24, 1998.

13. Gerdt V.P., Blinkov Yu.A., Completion of Linear Differential Systems to Involution, Computer Algebra in Scientific Computing CASC'99, V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, pp. 115-137, 1999.

14. 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, pp. 164171, 2000.

15. Gerdt V.P., Blinkov Yu.A., Yanovich D.A., Fast Search for the Janet Divisor. Programming and Computer Software, Vol. 27, No. 1, 22-24, 2001.

16. 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.), Springer-Verlag, Berlin, pp. 233-247, 2001.

17. Gerdt V.P., Blinkov Yu.A., Yanovich D.A., Computation of Janet Bases. ILPolynomial Bases. Computer Algebra in Scientific Computing / CASC 2001, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, pp. 249-263, 2001.

18. Gerdt V.P., On an Algorithmic Optimization in Computation of Involutive Bases, Programming and Computer Software, Vol. 28, No. 2, C2-65, 2002.

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

20. Janet, M. Sur les Systèmes d'Equationes aux Dérivées Partielles. J.Math. Pure at Appl. 3, 65-151, 1920.

21. Kolchin E.R. Differential Algebra and Algebraic Groups. Academic press, 1973.

22. Kondratieva M.V., Levin A.B., Mikhalev A.V., Pankratiev E.V. Differential and Difference Dimension Polynomials. Klüver publishers, 1999.

23. Mansfield E. Differential Gröbner bases. Ph.D. Thesis, University of Sydney, 1991.

24. Mora T., Robbiano L. The Gröbner fan of an ideal. JSC, 6:183-208, 1988.

25. O'Shea D. Gröbner fan and walk. Spring er-Verlag electronic production, 2001.

26. Pankratiev E.V., Some Approaches to Construction of Standard Bases in Commutative and Differential Algebra, Proc. of CASC'2002, V.G. Ganzha, E. W. Mayr, E. V. Vorozhtsov (Eds.), Technische Universitaet Muenchen, Garching, Germany, 265-268, 2002.

27. Pommaret J.F., Systems of Partial Differential Equations and Lie Pseu-dogroups, Gordon & Breach, New York, 1978.

28. Riquier C. Les systèmes d'équations aux dérivées partielles. Gauthier-Villars, Paris, 1910.

29. Ritt J. Differential Algebra. Dover, 1950.

30. Rust C.J., Reid G.J. Rankings of partial derivatives. 1998.45| Schwarz F. Monomial orderings and Gröbner bases. ACM SIGSAM Bulletin 25/1, pp. 10-23, 1991.

31. Thomas, J. Differential Systems. American Mathematical Society, New York, 1937.

32. Weispfenning V. Differential term-orders. Proc. of ISAAC'93. Kiev, ACM press, 1993.

33. Zharkov A.Yu., Solving Zero-Dimensional Involutive Systems. Algorithms in Algebraic Geometry and Applications, L. Gonzales-Vega, T. Recio (eds). Progress in Mathematics, Vol. 143, Birkhauser, Basel, pp. 389-399, 1996.

34. Zharkov, A.Yu., Blinkov, Yu.A. Involutive Bases of Zero-Dimensional Ide- als. Preprint No. E5-94-318, Joint Institute for Nuclear Research, Dubna, 1994.Работы автора по теме диссертации:

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

36. Астрелин А.В., Голубицкий О.Д., Панкратьев Е.В., Сравнение алгоритмов построения базисов Гребнера и инволютивных базисов, Международный алгебраический семинар, посвященный 70-летию ■кафедры высшей алгебры МГУ, Тезисы докладов, с. 9-10, 1999.

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

38. Golubitsky O., Transformation of characteristic sets from one ranking to another, Proceedings of 8th Rhine Workshop on Computer Algebra, Mannheim, Germany, pp. 225-236, 2002.

39. Golubitsky O., Differential Grobner Walk, Proceedings of International Workshop on Computer Algebra and its Application to Physics (CAAP), Dubna, Russia, pp. 114-126, 2001.