Маршруты Грёбнера тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Голубицкий, Олег Дмитриевич

• Голубицкий, Олег Дмитриевич
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Голубицкий, Олег Дмитриевич

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] не обобщается напрямую на случай дифференциальных идеалов, для которого приводится пример бесконечного разбиения Грёбнера. Тем не менее доказывается, что дифференциальный маршрут Грёбнера всегда конечен.

Список литературы диссертационного исследования кандидат физико-математических наук Голубицкий, Олег Дмитриевич, 2003 год

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.