Алексей игоревич алгоритмические методы в дифференциальной теории идеалов

На правах рукописи

УДК 512.628.2+519.688 Овчинников Алексей Игоревич Алгоритмические методы в дифференциальной теории идеалов 01.01.06 математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Москва 2008

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

Научные руководители: кандидат физико-математических наук, ведущий научный сотрудник Евгений Васильевич Панкратьев кандидат физико-математических наук, старший научный сотрудник Марина Владимировна Кондратьева

Официальные оппоненты: доктор физико-математических наук, профессор Александр Александрович Михалев кандидат физико-математических наук, доцент Ирина Николаевна Балаба

Ведущая организация: Вычислительный центр им. А.А. Дородницына РАН

Защита диссертации состоится 23 мая 2008 г. в 16 ч. 40 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Российская Фе дерация, Москва, ГСП-1, Ленинские горы, Московский Государственный Университет имени М.В. Ломоносова, Механико-математический факуль тет, аудитория 14-08.

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

Автореферат разослан 23 апреля 2008 г.

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

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

Актуальность темы За последние десятилетия был достигнут значительный прогресс в обла сти компьютерной алгебры, одной из приоритетных задач которой являет ся развитие методов решения систем нелинейных алгебраических уравне ний от нескольких переменных, а также методов изучения алгебраических идеалов, порожденных нелинейными полиномиальными системами. Насто ящим прорывом в данной области стало появление базисов Гребнера и ал горитма их вычисления, предложенного Бухбергером еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную си стему уравнений к стандартному виду.

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

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

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

Эта задача успешно решена автором в данной работе.

Научная новизна В диссертации получены следующие основные результаты:

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

2. Впервые получена оценка сверху на число дифференцирований, вы полняемых алгоритмом Rosenfeld-Grbner, который разлагает ради o кальный дифференциальный идеал на характеризуемые компоненты.

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

Первые оценки на порядки характеристических множеств были получе ны Б. Садиком6. Эти результаты касались лишь исключающих ранжиров и простых дифференциальных идеалов. В диссертации же получены ре зультаты, не имеющие таких ограничений: ранжиры допускаются любые, а идеалы должны быть лишь характеризуемыми дифференциальными. Про стые дифференциальные идеалы таковыми являются. Для доказательства основных результатов о канонических характеристических множествах в диссертации также используются утверждения, доказанные Э. Юбер7 о связи между характеристическим множеством характеризуемого диффе ренциального идеала и характеристическими множествами его минималь E. Kolchin, Dierential Algebra and Algebraic Groups. Academic Press, New York, 1973.

M. Kondratieva, A. Levin, A. Mikhalev, and E. Pankratiev, Dierential and dierence dimension polynomials. Kluwer Academic Publisher, 1999.

J. Ritt, Dierential Algebra. American Mathematical Society, New York, 1950.

F. Boulier, D. Lazard, F. Ollivier, and M. Petitot, Representation for the radical of a nitely generated dierential ideal. In Proceedings of ISSAC 1995, pages 158–166. ACM Press, 1995.

F. Boulier, D. Lazard, F. Ollivier, and M. Petitot, Computing representations for radicals of nitely generated dierential ideals. Technical report, IT-306, LIFL, 1997.

B. Sadik, A bound for the order of characteristic set elements of an ordinary prime dierential ideal and some applications. Applicable Algebra in Engineering, Communication and Computing, 10(3):251–268, 2000.

E. Hubert, Factorization-free decomposition algorithms in dierential algebra. Journal of Symbolic Computation, 29(4-5):641–662, 2000.

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

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

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

Также получена оценка на порядки элементов канонического характе ристического множества характеризуемого идеала. Эта оценка позволила получить новый алгоритм преобразования характеристического разложе ния радикального дифференциального идеала от одного ранжира к дру гому8. Подобный алгоритм может быть реализован на компьютере, напри мер, в системе компьютерной алгебры Maple. Предыдущие исследования по этому вопросу проводились Ф. Булье, Ф. Лемэром, М. Морено Маза9 и О. Голубицким10.

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

O. Golubitsky, M. Kondratieva, and A. Ovchinnikov. Algebraic transformation of dierential characteristic decompositions from one ranking into another. Submitted for publication, 2007.

F. Boulier, F. Lemaire, and M. Moreno-Maza, PARDI! In Proceedings of ISSAC 2001, pages 38–47. ACM Press, 2001.

O. Golubitsky. Grbner walk for characteristic sets of prime dierential ideals. In: Ganzha, V., Mayr, o E., Vorozhtsov, E. (Eds.), Proc. 7th Workshop on Comp. Alg. in Sc. Comp. TU Mnchen, Germany, pp.

u 207–221, 2000.

Апробация работы Результаты диссертации докладывались:

• на семинаре по компьютерной алгебре Механико-математического фа культета МГУ в 2003–2007 годах, • на конференции Компьютерная алгебра и ее приложения в физике (CAAP) и семинарах по компьютерной алгебре в 2001–2007 годах в Дубне, • на Международной алгебраической конференции, посвященной 250 летию МГУ и 75-летию кафедры высшей алгебры в МГУ в 2004 году, • на международной конференции Приложения компьютерной алгеб ры в 2003 году (Роли, Северная Каролина) и 2004 году (Бомонт, Техас), • на международной конференции Компьютерная алгебра в научных вычислениях в 2002 году (Ялта, Крым) и в 2004 году (Санкт-Петербург), • на Колчинском семинаре по дифференциальной алгебре (Нью-Йорк) в 2004 и 2005 годах, • на конференции по дифференциальной алгебре в Университете Линца (RISC), Австрия, в 2006 году, • на конференции по алгебраическим методам в дифференциальных уравнениях (Эдинбург, Шотландия) в 2006 году.

Публикации Результаты автора по теме диссертации опубликованы в 8 работах, список которых приводится в конце автореферата [1–8].

Структура и объем диссертации Диссертационная работа состоит из 5 глав (первая глава является вводной) и заключения. Библиография содержит 32 наименования. Общий объем диссертации составляет 61 стр.

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

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

В третьей главе сформулированы классические результаты дифферен циальной алгебры о характеристических множествах и соответствии меж ду характеризуемыми алгебраическими и дифференциальными идеалами:

теоремы 1–3. Данные результаты используются в диссертации.

Четвертая глава посвящена каноническим характеристическим мно жествам характеризуемых дифференциальных идеалов. Сначала дается определение канонического характеристического множества по анало гии с редуцированным базисом Гребнера. Пусть k дифференциальное поле нулевой характеристики с основным множеством дифференцирова kk km ний = {1,..., m } и = 1 1 2 2 · · · m, ki 0. Мы также пред полагаем, что зафиксирован ранжир на множестве переменных Y, где Y = y1,..., yn. Пусть A авторедуцированное множество в кольце диффе ренциальных многочленов k{y1,..., yn } = k[Y ] и пусть k[N ][L] кольцо многочленов, ассоциированное с A, где L множество лидеров многочле множество нелидеров, то есть, N = Y \ L.

нов из A и N Определение. Характеристическое множество C = C1,..., Cp дифферен циального идеала I называется каноническим, если следующие условия выполнены для i = 1,..., p:

• инициал iCi зависит только от нелидеров N множества C;

• многочлен Ci не имеет делителей в I, кроме самого Ci ;

• старший коэффициент Ci относительно индуцированного лексикогра фического упорядочения lex на мономах над N L равен 1.

Рассмотрим k{y1,..., yn } c = {}. Это означает, что мы находимся в обыкновенном случае. Дифференциальной размерностью простого диф ференциального идеала P называется максимальное число q, такое что P k{yi1,..., yiq } = {0}. Если f дифференциальный многочлен, то ord f обозначает максимальный порядок дифференциальных переменных, входящих в f. Пусть A = A1,..., Ap авторедуцированное множество.

Определим порядок множества A следующим равенством:

ord A = ord A1 +... + ord Ap.

Если C характеристическое множество простого дифференциального идеала P относительно степенного ранжира, то, по определению, порядок идеала P равен неотрицательному целому числу ord C. Обозначим через P (s) множество элементов P, чей порядок меньше или равен s. Множе ство P (s) образует простой алгебраический идеал в соответствующем коль це многочленов. Известно1,2, что размерность P (s) многочлен от s для s h = ord P. Более точно, dim P (s) = q(s + 1) + ord P, где q дифференциальная размерность идеала P. Более того, q = n p, где p число элементов характеристического множества идеала P отно сительно любого степенного ранжира. Таким образом, числа ord P и p не зависят от выбора степенного ранжира. Определим порядок характеризу емого дифференциального идеала.

Определение. Для характеризуемого дифференциального идеала I = k Pi, где Pi минимальные дифференциальные простые компоненты I, i= определим ord I = max ord Pi.

1ik Доказательство основной оценки в этой главе диссертации (теорема 6) Теорема. Пусть C = C1,..., Cp каноническое характеристическое множество характеризуемого дифференциального идеала I. Тогда ord Ci ord I, 1 i p.

опирается существенным образом на аналогичную оценку для простых иде алов, доказанную в диссертации (теорема 4):

Теорема. Пусть P простой дифференциальный идеал порядка h в k{y1,..., yn } и любой ранжир. Тогда существует характеристи ческое множество C = C1,..., Cp идеала P относительно ранжира, такое что порядок по yt каждого Ci не превосходит h для всех 1 t n.

В пятой главе рассматривается алгоритм разложения Rosenfeld-Grbner o радикального дифференциального идеала {F }, заданного конечной систе мой образующих F, на характеризуемые компоненты. Основной результат этой главы состоит в следующем. Пусть на вход алгоритма разложения (ал горитм 3), корректность которого доказана в предложении 5, подается ко нечная система F из кольца дифференциальных многочленов k{y1,..., yn }.

Определим:

n mi (F ) = max ordyi f, M (F ) = mi (F ).

f F i= Тогда все системы A, H, получающиеся на выходе и в ходе работы алго ритма, удовлетворяют оценке M (A H) (n 1)! · M (F ).

Основной идеей доказательства данной оценки было заменить использо вание дифференциальной редукции на применение дифференцирования в начале вычисления, а затем алгебраической редукции (см. алгоритм 2).

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

От этого осложнения можно избавиться и существенно повысить при влекательность и применимость данного результата. В предложении 7 и теореме 7 показывается, как избежать применения упомянутого алгорит ма алгебраической редукции. В частности, доказывается, что, если полу чившийся остаток не удовлетворяет оценке, то можно отбросить мономы у этого остатка, не удовлетворяющие оценке, при этом сохранив коррект ность алгоритма. Это рассуждение подытожено в двух последних алгорит мах диссертации (см. алгоритмы 4 и 5).

Благодарности Автор благодарит своих научных руководителей: ведущего научного сотрудника Лаборатории вычислительных методов МГУ, к. ф.–м. н.

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

Работы автора по теме диссертации [1] А. И. Овчинников, Порядки дифференцирований в разложении ра дикальных дифференциальных идеалов, Успехи математических наук 63(2) (2008) 179– [2] О.Д. Голубицкий, М. В. Кондратьева и А. И. Овчинников, Канониче ские характеристические множества характеризуемых дифференци альных идеалов, Вестник МГУ. Математика, (2) (2008) 49– В данной работе Овчинникову А.И. принадлежит доказательство основной теоремы 2, дающей верхнюю оценку на порядки дифферен цирований в каноническом характеристическом множестве просто го дифференциального идеала относительно любого ранжира. Кондра тьевой М.В. принадлежит доказательство теоремы 3, дающей обоб щение упомянутой оценки на случай произвольных характеризуемых дифференциальных идеалов. Голубицкому О.Д. принадлежат доказа тельства теоремы 1 и предложения 3, дающих критерий равенства характеризуемых дифференциальных идеалов, заданных своими харак теристическими множествами.

[3] М. В. Кондратьева, А. И. Овчинников, Характеристические множе ства обыкновенных дифференциальных уравнений, Программирование 31(2) (2005) 56– В данной работе Овчинникову А.И. принадлежит доказательство основной теоремы 4, дающей способ вычисления характеристическо го множества радикального дифференциального идеала относительно степенного ранжира. Кондратьевой М.В. принадлежат формулиров ка основного результата и вычислительные примеры.

[4] M.V. Kondratieva, A. Ovchinnikov, On Computing Characteristic Sets of Arbitrary Radical Dierential Ideals, в трудах конференции Applications of Computer Algebra 2004 (ACA 2004) 38– В данной работе Овчинникову А.И. принадлежат доказательства ос новных результатов, находящихся в теоремах 4 и 5 и формулировка теоремы 5. Эти теоремы позволяют вычислять характеристические множества как в обыкновенно случае, так и в случае частных произ водных. Кондратьевой М.В. принадлежат формулировка теоремы 4, алгоритмы 1 и 2, вычислительные примеры и гипотеза, находящаяся в разделе 6.

[5] A. Ovchinnikov, Computation of Characteristic Sets of Radical Dierential Ideals, в трудах конференции Computer Algebra in Scientic Computing 2004 (CASC 2004) 371– [6] А. И. Овчинников, Характеризуемые радикальные дифференциальные идеалы и некоторые свойства характеристических множеств, Про граммирование 30(3) (2004) 33– [7] A. Ovchinnikov, On Characterizable ideals and characteristic sets, Contributions to General Algebra 14 (2004) 91– [8] А. Овчинников, Сечения над дифференциальным спектром и вычисле ния, не использующие факторизацию, Фундаментальная и прикладная математика, том 9, вып. 3 (2003) 133–