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

имени М.В. Ломоносова

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

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

УДК 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, которые были им разработаны для систем линейных дифференциальных уравнений с частными производными и обыкновенных систем из двух алгебраических дифференциальных уравнений. В диссертации приводится оценка порядка дифференцирований в обыкновенном случае, но допускается любое число уравнений в системе.

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

Также получена оценка на порядки элементов канонического характеристического множества характеризуемого идеала. Эта оценка позволила получить новый алгоритм преобразования характеристического разложения радикального дифференциального идеала от одного ранжира к другому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, E., Vorozhtsov, E. (Eds.), Proc. 7th Workshop on Comp. Alg. in Sc. Comp. TU Mnchen, Germany, pp.

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 относительно индуцированного лексикографического упорядочения любой ранжир. Тогда существует характеристическое множество C = C1,..., Cp идеала P относительно ранжира >, такое что порядок по yt каждого Ci не превосходит h для всех 1 t n.

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

Определим:

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