Введение к работе
Актуальность темы. Системы полиномиальных уравнений изучаются на протяжении нескольких столетий и имеют множество приложений. На алгебраическом языке системы полиномиальных уравнений описываются идеалами в кольцах многочленов. Особо важна задача канонического представления идеала, вопрос о принадлежности многочлена идеалу и решение систем полиномиальных уравнений. Теория базисов Грёбнера дает алгоритмическое решение этих задач.
Первый алгоритм построения базиса Грёбнера был разработан и реализован Бухбергером в 1965 г. Его основная идея заключается в преобразовании исходной системы многочленов в эквивалентную каноническую систему. Решение системы линейных уравнений методом Гаусса и нахождение наибольшего общего делителя многочленов от одной переменной с помощью алгоритма Евклида являются частными случаями алгоритма Бухбергера. В общем случае алгоритм Бухбергера имеет высокую сложность, для которой не известно хорошей теоретической оценки — наоборот, известны примеры систем, для которых базис Грёбнера имеет экспоненциальный размер. Поэтому становится важной разработка различных методов, позволяющих усовершенствовать алгоритм Бухбергера на практике.
Идея преобразования системы в эквивалентную каноническую присутствует и в работах Жане, Томаса и Поммаре1'2'3 по системам линейных уравнений в частных производных. В этих работах приведение системы к каноническому виду называется приведением в инволюцию. В работах Гердта, Жаркова и Блинкова (например4 ) разработана теория инволю-тивных делений и инволютивных базисов для систем многочленов. Инво-лютивные базисы являются нередуцированными базисами Грёбнера5,6 и вместе с тем имеют дополнительные полезные свойства7 . Вид и сложность
'Janet, М. Sur les Systfcmcs d'Equationcs aux Dcrivccs Particlles. 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 Pseudo-groups, Gordon fc Breach, New York, 1978.
*Gcrdt V.P., Blinkov Yu.A., Involutivc Bases of Polynomial Ideals. Prcprint-Nr.1/1996, Naturwisscnschaftlich-Thcorcti6hes Zontrum, University of Leipzig; Math. Сотр. Sim. 45, 519-542, 1998.
sZharkov, A.Yu., Blinkov, Yu.A. Involutivc Approach to Investigating Polynomial Systems. In: Proceedings ofSC 95, International IMACS Symposium on Symbolic Computation: New Trends and Developments (Lille, June Ц-17, 1993),. Math. Сотр. Siimil. 42, 323-332,1996.
6Zharkov, A.Yu., Blinkov, Yu.A. Involutivc Bases of Zero-Dimensional Ide- als. Preprint No. E5 94-318, Joint Institute for Nuclear Research, Dubna, 1994.
'Zharkov A.Yu., Solving Zero-Dimensional Involutivc Systems. Algorithms in Algebraic Geometry and Applications, L. Gonzales-Vega, T. Rocio (cds). Progress in Mathematics, Vol. 143, BirkhauscT, Basel, pp 389-399,1996.
HSU4&
*>OC. НАЦИОНАЛЬ БИБЛИОТЕКА С.Петербург 09 V
построения инволютивных базисов зависит от инволютивного деления, грамотный выбор которого позволяет ускорить алгоритм этого построения8 . Эксперименты показывают, что во многих случаях инволютивный алгоритм работает быстрее, чем алгоритм Бухбергера.
Существует совершенно иной метод усовершенствования алгоритма Бухбергера для построения базисов Грёбнера относительно лексикографического порядка, известный под названием маршрута Грёбнера (Grobner Walk) Этот метод основан на известном наблюдении, что время работы алгоритма Бухбергера существенно зависит от выбора отношения порядка на мономах. Например, построение базиса Грёбнера относительно порядка общей степени, как правило, гораздо более эффективно, чем построение базиса для лексикографического порядка. Метод маршрута Грёбнера, впервые предложенный Коллартом, Калкбренером и Маллом в работе9 , позволяет эффективно преобразовывать базис Грёбнера относительно одного порядка на мономах в базис относительно любого другого порядка. Эксперименты показывают10 , что такое косвенное построение может оказаться гораздо эффективнее прямого построения лексикографического базиса Грёбнера.
Для систем нелинейных уравнений в частных производных также существует подход, связанный с приведением системы к каноническому виду и основанный на понятиях из дифференциальной алгебры. Основы дифференциальной алгебры, включая понятие кольца дифференциальных многочленов, дифференциального идеала и характеристического множества, были заложены Риттом11 и Колчином12 . Дальнейшее развитие дифференциальная алгебра получила в работах ряда авторов второй половины XX века. В частности, была разработана теория дифференциальных и разностных размерностных многочленов, с которой можно ознакомиться по монографии Кондратьевой, Левина, Михалева и Панкратьева13 . Характеристические множества дифференциальных идеалов играют роль, сходную с ролью базисов Грёбнера для полиномиальных идеалов. Однако, некоторые важные свойства базисов Грёбнера не переносятся на дифференциальный случай13 . Например, характеристическое множество дифференциального
'Gcrdt V.P., Involutivc Division Technique: Some Generalizations and Optimizations. Preprint of the Joint Institute for Nuclear Research, Dubna, Е5-98-Ш, 1998.
'Collart S., Kalkbrcner M., Mall D. The Gr5bncr walk. Dcpt. of Math., Swiss Federal Inst, of Tech, 8092 Zurich, Switzerland, 1993. I0Amrhcin В , Gloor 0., Kuchlin W. How fast docs the walk run. Proc of RWCA '96,1996. "Ritt J. Differential Algebra. Dover, 1950.
12Kolchin E.R. Differential Algebra and Algebraic Groups Academic press, 1973.
13Kondraticva M.V., Levin A.B., Mikhalcv A.V., Pankraticv E.V. Differential and Difference Dimension Polynomials Kliivcr publishers, 1999.
идеала, вообще говоря, может не порождать этот идеал.
Задача построения характеристических множеств гораздо сложнее ее полиномиального аналога. В случае простых дифференциальных идеалов эта задача может быть решена с помощью алгоритма Розенфельда-Грёбне-ра14 или специализированного алгоритма Розенфельда-Грёбнера15 . Однако, в обоих случаях искомое характеристическое множество строится путем прямого вычисления. Такой подход может оказаться неэффективным, особенно в случае исключающего ранжира. Для решения этой проблемы Булье16 предложил алгоритм DFGLM, являющийся дифференциальным обобщением алгоритма FGLM17 (последний алгоритм был разработан для ускорения подсчета полиномиальных базисов Грёбнера для лексикографического порядка в случае нульмерных идеалов). Однако, как отмечено в работе16 , этот алгоритм применим только к системам, решения которых параметризованы конечным семейством параметров. Алгоритм Кэли, также предложенный в работе16 , применим к произвольным дифференциальным системам, но, как отмечено в16 , менее эффективен, чем DFGLM.
Случай конечного семейства параметров для дифференциальных систем аналогичен случаю нульмерного идеала в кольце многочленов R, который является необходимым условием для применения алгоритма FGLM. Но даже при таком ограничении сложность алгоритма растет с ростом размерности векторного фактор-пространства R/I. Результаты экспериментов, приведенные в18'19 , показывают, что, за исключением простейших случаев, маршрут Грёбнера20 не менее эффективен, чем FGLM, а с ростом размерности R/I первый становится гораздо более эффективным. Кроме того, метод маршрута Грёбнера применим к произвольным полиномиальным идеалам. Данное наблюдение позволяет предположить, что обобщение метода маршрута Грёбнера на дифференциальный случай будет обладать теми же преимуществами по сравнению с алгоритмом16 .
Цель работы. Целью настоящей работы является исследование связи
"Boulicr F., Lazard D., Ollivicr F., Pctitot M. Representation for the radical of a finHcly generated differential ideal. Ртос. ISAAC 1995, ACM Press, 158-166.
"Boulicr F., Lcmairc F., Maza M.M. PARDI! Publication LIFL 2001-01, 2001.
ieBoulicr F. Efficient computation of regular differential systems Ъу change of rankings using Kahlcr differentials. Tech. rep., Univcrsitc Lille I, 1999.
,7Faugcrc J.C., Gianni P., Lazard D., Mora T. Efficient computation of zero-dimensional Grobncr bases by change of ordering. JSC, 16-329-344,1993.
"Amrhcin В., Gloor 0., Kiichlin W. How fast docs the walk run. Proc. of RWCA '96, 1996
,sAmrhein В., Gloor 0., Kiichlin W. Walking faster. Ртос of D1SC0'96, Karlsruhe, Germany, 1996.
'"Collart S , Kalkbrencr M., Mall D. The Grobncr walk. Dcpt. of Math., Swiss Federal Inst, of Tech, 8092 Zurich, Switzerland, 1993
между инволютивными базисами и базисами Грёбнера, обобщение метода маршрута Грёбнера на инволютивный и дифференциальный случаи и экспериментальное сравнение полученных алгоритмов с известными.
Научная новизна. Научная новизна данной работы состоит в следующем:
-
Понятия базисов Грёбнера и инволютивных базисов изложены в рамках общей теории схем симплификации и стандартных базисов21 .
-
Получен результат о сходстве алгоритма Бухбергера и алгоритма построения инволютивных базисов. Отмечена связь между выбором ин-волютивного деления и выбором алгоритма вычисления нормальной формы, являющимся частью алгоритма Бухбергера.
-
Метод маршрута Грёбнера перенесен на случай инволютивных базисов.
-
Алгоритм Бухбергера, алгоритм построения инволютивных базисов и методы маршрута Грёбнера и инволютивного маршрута Грёбнера реализованы в системе компьютерной алгебры Maple, и проведено экспериментальное сравнение их эффективности.
-
Метод маршрута Грёбнера перенесен на дифференциальный случай. Точнее, предложен алгоритм, который по характеристическому множеству А дифференциального идеала / относительно ранжира В идеала I относительно другого ранжира <2- Данный алгоритм применим в случае простых дифференциальных идеалов и ранжиров Рикье22'23'24 , которые включают порядковые и исключающие ранжиры25'16 . Теорема Мора и Робиа-но о конечности разбиений Грёбнера26'27 не обобщается напрямую на случай дифференциальных идеалов, для которого приводится пример бесконечного разбиения Грёбнера. Тем не менее доказывается, что дифференциальный маршрут Грёбнера всегда конечен.
21 Латышев В.Н., Комбинаторная теория колец Стандартные базисы М.: МГУ, 1988. BRiquicr С. Lea syatimes d'iguations aui dertvees partielhs. Gauthicr-Villars, Paris, 1910. 23Rust C.J., Rcid G.J. Rankings of partial derivatives. 1998.
"Wcispfcnning V. Differential term-orders. Proc. of ISAAC9S. Kiev, ACM press, 1993. 26Kondraticva M.V., Levin А.В., Mikhalcv A.V., Pankraticv E.V. Differential and Difference Dimension Polynomials Kluvcr publishers, 1999. MMora Т., Robbiano L The Grobncr fan of an ideal. JSC, 6:183-208,1988. 270'Shca D. Grobncr fan and walk. Springer-Verlag electronic production, 2001.
Практическая и теоретическая ценность. Методы и алгоритмы, предложенные в диссертации, могут быть внедрены в существующие системы компьютерной алгебры и таким образом дадут возможность анализировать и решать в символьном виде более сложные системы полиномиальных уравнений и уравнений в частных производных.
Результаты работы могут быть использованы в различных задачах теории базисов Грёбнера, полиномиальных инволютивных базисов и характеристических множеств дифференциальных идеалов в кольце дифференциальных многочленов.
Апробация работы. Основные результаты диссертации докладывались на Международной конференции по приложениям компьютерной алгебры IMACS АСА в 1998 г., Международной алгебраической конференции по случаю 90-летия А.Г. Куроша в 1998 г., Международном алгебраическом семинаре, посвященном 70-летию кафедры Еысшей алгебры МГУ в 1999 г., Ежегодном совместном семинаре МГУ и ОИЯИ РАН по компьютерной алгебре в 1999 г., Международном семинаре по компьютерной алгебре и приложениям в физике в 2001 г., и Рейнском семинаре по компьютерной алгебре в 2002 г.
Публикации. Результаты диссертации опубликованы в шести работах, список которых приведен в конце автореферата.
Структура и объем диссертации. Диссертационная работа состоит из четырех глав, первая из которых является вводной, и одного приложения и содержит библиографию (56 наименований). Общий объем диссертации составляет 57 страниц. Структура работы отражена в оглавлении.
