Алгоритмические методы в дифференциальной теории идеалов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

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

На правах рукописи УДК 512 628 2+519 688

Овчинников Алексей Игоревич

Алгоритмические методы

в дифференциальной теории идеалов

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2008

003168902

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

Научные руководители кандидат физико-математических наук,

ведущий научный сотрудник

Евгений Васильевич Панкратьев

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

Официальные оппоненты доктор физико-математических наук,

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

Ведущая организация Вычислительный центр

им. А А Дородницына РАН

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

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

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

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

А О Иванов

Общая характеристика работы Актуальность темы

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

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

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

Цель работы

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

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

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

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

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

Основные методы исследования

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

Первые оценки на порядки характеристических множеств были получены Б Садиком6 Эти результаты касались лишь исключающих ранжиров и простых дифференциальных идеалов В диссертации же получены результаты, не имеющие таких ограничений ранжиры допускаются любые, а идеалы должны быть лишь характеризуемыми дифференциальными Простые дифференциальные идеалы таковыми являются Для доказательства основных результатов о канонических характеристических множествах в диссертации также используются утверждения, доказанные Э Юбер7 о связи между характеристическим множеством характеризуемого дифференциального идеала и характеристическими множествами его минималь-

1 Е Kolchin, Differential Algebra and Algebraic Groups Academic Press, New York, 1973

2 M Kondratieva, A Levin, A Mikhalev, and E Pankratiev, Differential and difference dimension polynomials Kluwer Academic Publisher, 1999

3 J Ritt, Differential Algebra. American Mathematical Society, New York, 1950

4F Boulier, D Lazard, F ОНшег, and M Petitot, Representation for the radical of a finitely generated differential ideal In Proceedings of ISSAC1995, pages 158-166 ACM Press, 1995

5F Boulier, D Lazard, F Ollivier, and M Petitot, Computing representations for radicals of finitely generated differential ideals Technical report, IT-306, LIFL, 1997

eB Sadik, A bound for the order of characteristic set elements of an ordinary prime differential ideal and some applications Applicable Algebra m Engineering, Communication and Computing, 10(3) 251-268,2000

7E Hubert, Factorization-free decomposition algorithms in differential algebra Journal of Symbolic Computation, 29(4-5) 641-662,2000

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

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

Теоретическая и практическая ценность работы

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

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

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

60 Golubitsky, М Kondratieva, and A Ovchiimikov Algebraic transformation of differential

characteristic decompositions from one rsnfang tnto another Submitted for publication, 2007

SF Boulier, F Lemaire, and M Moreno-Maza, PARDI' Ь Proceedings of ISS AC 2001, pages 38-47 ACM

Press, 2001

10O Golubitsky Grohncr traft for characteristic sets of prime differential ideals In Ganzha, V , Mayr, E , Vorozhtsov, E (Eds), Proc 7th Workshop on Comp Alg m Sc Comp TU München, Germany, pp 207-221, 2000

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

Результаты диссертации докладывались

• на семинаре по компьютерной алгебре Механико-математического факультета МГУ в 2003-2007 годах,

• на конференции «Компьютерная алгебра и ее приложения в физике» (СААР) и семинарах по компьютерной алгебре в 2001-2007 годах в Дубне,

• на Международной алгебраической конференции, посвященной 250-летию МГУ и 75-летию кафедры высшей алгебры в МГУ в 2004 году,

• на международной конференции «Приложения компьютерной алгебры» в 2003 году (Роли, Северная Каролина) и 2004 году (Бомонт, Техас),

• на международной конференции «Компьютерная алгебра в научных вычислениях» в 2002 году (Ялта, Крым) и в 2004 году (Санкт-Петербург),

• на Колчинском семинаре по дифференциальной алгебре (Нью-Йорк) в 2004 и 2005 годах,

• на конференции по дифференциальной алгебре в Университете Линца (RISC), Австрия, в 2006 году,

• на конференции по алгебраическим методам в дифференциальных уравнениях (Эдинбург, Шотландия) в 2006 году

Публикации

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

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

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

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

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

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

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

Четвертая глава посвящена каноническим характеристическим множествам характеризуемых дифференциальных идеалов Сначала дается определение канонического характеристического множества по аналогии с редуцированным базисом Гребнера Пусть к — дифференциальное поле нулевой характеристики с основным множеством дифференцирований Д = {¿1, ,5т} и © = Мы также предполагаем, что зафиксирован ранжир на множестве переменных ©У, где ^ — 2/х I , Уп Пусть А — авторедуцированное множество в кольце дифференциальных многочленов к {ух, ., уп} = к[©У] и пусть к[7У][£] — кольцо многочленов, ассоциированное с А, где Ь — множество лидеров многочленов из А и N — множество нелидеров, то есть, N = 6У \ ©Ь

Определение. Характеристическое множество С = Сг, ,СР дифференциального идеала I называется каноническим, если следующие условия выполнены для г — 1, ,р

• инициал 1с, зависит только от нелидеров N множества С,

• многочлен Сг не имеет делителей в /, кроме самого С,,

• старший коэффициент С, относительно индуцированного лексикографического упорядочения <1ех на мономах над N и Ь равен 1

Рассмотрим к{ух, ,у„} с Д = {5} Это означает, что мы находимся в обыкновенном случае Дифференциальной размерностью простого дифференциального идеала Р называется максимальное число д, такое что РГ)к{уч, ,у1д} = {0} Если / — дифференциальный многочлен, то огс1 / обозначает максимальный порядок дифференциальных переменных, входящих в / Пусть А = А1: ,АР — авторедуцированное множество Определим порядок множества А следующим равенством

огё А = ог(1 + + огс! Ар

Если С — характеристическое множество простого дифференциального идеала Р относительно степенного ранжира, го, по определению, порядок идеала Р равен неотрицательному целому числу огёС Обозначим через Р(з) множество элементов Р, чей порядок меньше или равен я Множество Р(в) образует простой алгебраический идеал в соответствующем кольце многочленов Известно1,2, что размерность Р(в) — многочлен от я для

s^ h — ord P Более точно,

dim P(s) = g(s + 1) + ord P,

где q — дифференциальная размерность идеала P Более того, q = n — p, где p — число элементов характеристического множества идеала Р относительно любого степенного ранжира Таким образом, числа ord Р и р ни зависят от выбора степенного ранжира Определим порядок характеризуемого дифференциального идеала

Определение. Для характеризуемого дифференциального идеала I = к

Р) Р„ где Р, — минимальные дифференциальные простые компоненты I, i=i

определим

ord/= max ord P.

Кг Kk

Доказательство основной оценки в этой главе диссертации (теорема 6)

Теорема. Пусть С = Ci, , Ср — каноническое характеристическое множество характеризуемого дифференциального идеала I Тогда

ord С, < ord 7, 1 ^ г ^ р

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

Теорема. Пусть Р — простой дифференциальный идеал порядка h в Мш> • i Уп} и > — любой ранжир Тогда существует характеристическое множество С = Ci, ,СР идеала Р относительно ранжира >, такое что порядок по yt каждого Сг не превосходит h для всех 1 ^ t ^ п

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

п

mt{F) = max ord^, /, M(F) = V mt(F)

Тогда все системы А, Я, получающиеся на выходе и в ходе работы алгоритма, удовлетворяют оценке

М(Л U Н) < (n-l)'-M(F) 6

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

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

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

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

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

атмосферу Автор также благодарит к ф -м н Алексея Игоревича Зобни-на и организаторов и участников ежегодного семинара ло компьютерной алгебре в Дубне за оживленные дискуссии по различным вопросам компьютерной алгебры

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

[1] А И Овчинников, Порядки дифференцирований в разложении радикальных дифференциальных идеалов, Успехи математических наук 63(2) (2008) 179-180

[2] О Д Голубицкий, М В Кондратьева и А И Овчинников, Канонические характеристические множества характеризуемых дифференциальных идеалов, Вестник МГУ Математика, (2) (2008) 49-51

В данной работе Овчинникову А.И. принадлежит доказательство основной теоремы 2, дающей верхнюю оценку на порядки дифференцирований в каноническом характеристическом множестве простого дифференциального идеала относительно любого ранжира Кондратьевой М В принадлежит доказательство теоремы 3, дающей обобщение упомянутой оценки на случай произвольных характеризуемых дифференциальных идеалов Голубицкому О Д принадлежат доказательства теоремы 1 и предложения 3, дающих критерий равенства характеризуемых дифференциальных идеалов, заданных своими характеристическими множествами.

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

В данной работе Овчинникову А И принадлежит доказательство основной теоремы 4, дающей способ вычисления характеристического множества радикального дифференциального идеала относительно степенного ранжира Кондратьевой М В принадлежат формулировка основного результата и вычислительные примеры

[4] М V. Kondratieva, A Ovchmmkov, On Computing Characteristic Sets of Arbitrary Radical Differential Ideals, в трудах конференции Applications of Computer Algebra 2004 (АСА 2004) 38-48

В данной работе Овчинникову А И. принадлежат доказательства основных результатов, находящихся в теоремах £ и 5 и формулировка теоремы 5 Эти теоремы позволяют вычислять характеристические

множества как в обыкновенно случае, так и в случае частных производных Кондратьевой М В принадлежат формулировка теоремы 4, алгоритмы 1 и 2, вычислительные примеры и гипотеза, находящаяся в разделе 6

[5] А Ovchinmkov, Computation of Charactenstic Sets of Radical Differential Ideals, в трудах конференции Computer Algebra m Scientific Computing 2004 (CASC 2004) 371-378

[6] А И Овчинников, Характеризуемые радикальные дифференциальные идеалы и некоторые свойства характеристических множеств, Программирование 30(3) (2004) 33-43

[7] А Ovchinmkov, Оп Charactenzable ideals and charactenstic sets, Contnbutions to General Algebra 14 (2004) 91-108

[8] А Овчинников, Сечения над дифференциальным спектром и вычисления, не использующие факторизацию, Фундаментальная и прикладная математика, том 9, вып 3 (2003) 133-144

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать ОВ

Формат 60x90 1/16 Уел печ л 0,7'5" Тираж /ОС экз Заказ /£

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

1 Введение

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

1.2 Цель работы

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

1.4 Основные методы исследования

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

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

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

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

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

2 Основные понятия и обозначения

3 Классические результаты конструктивной дифференциальной алгебры

4 Канонические характеристические множества

4.1 Определения и свойства.

4.2 Оценка порядка.

4.3 Оценка порядков в каноническом характеристическом множестве

5 Оценка числа дифференцирований в алгоритме Rosenfeld-Grobner

5.1 Введение.

5.2 Стандартный алгоритм Rosenfeld-Grobner.

5.3 Использование алгебраической редукции.

5.4 Модификация алгоритма.

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

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

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

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

1.2 Цель работы

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

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

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

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

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

6 Заключение

Данная работа продолжает исследование алгоритмов, начатое в [18, 8, 9]. Проведено сравнение с [29] и существенно улучшен результат, полученный в указанной статье: в диссертации получена оценка на порядки элементов канонического характеристического множества характеризуемого дифференциального идеала вне зависимости от рассматриваемого ранжира. Данная оценка рассматривалась в обыкновенном случае.

Также сделан первый шаг к теоретической оценке сложности работы алгоритма разоложения радикального дифференциального идеала на характеризуемые компоненты. А именно: в обыкновенном случае получена оценка сверху на порядки дифференцирований на выходе и всех промежуточных шагах алгоритма Rosenfeld-Grobner. Данная оценка может и не быть оптимальной, но она является первой, полученной для подобного алгоритма разложения.

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

1. Теоретическая сложность алгоритмов разложения радикальных дифференциальных идеалов: оценить сложность работы, например, алгоритма Rosenfeld-Grobner.

2. Эффективная дифференциальная теорема Гильберта о нулях: если дифференциальный идеал [F] единичный, то требуется, используя лишь порядки, степени и число образующих F, найти, сколько раз надо продифференцировать F, чтобы в соответствующем алгебраическом идеале лежала единица.

1. О.Д. Голубицкий, М.В. Кондратьева и А.И. Овчинников. Канонические характеристические множества характеризуемых дифференциальных идеалов. Вестник МГУ. Математика, (2):49-51, 2008.

2. М.В. Кондратьева и А.И. Овчинников. Характеристические множества обыкновенных дифференциальных уравнений. Программирование, 31(2):56—63, 2005.

3. А.И. Овчинников. Сечения над дифференциальным спектром и вычисления, не использующие факторизацию. Фундаментальная и прикладная математика, 9(3): 133-144, 2003.

4. А.И. Овчинников. Характеризуемые радикальные дифференциальные идеалы и некоторые свойства характеристических множеств. Программирование, 30(3):33-43, 2004.

5. А.И. Овчинников. Порядки дифференцирований в разложении радикальных дифференциальных идеалов. Успехи математических наук, 63(2):179-180, 2008.

6. W. Adams and P. Loustanau. An Introduction to Grobner Bases. American Mathematical Society, Providence, Rhode Island, 1996.

7. T. Becker and V. Weispfenning. Grobner Bases. Springer-Verlag, New York-Berlin-Heidelberg, 1993.

8. F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Representation for the radical of a finitely generated differential ideal. In Proceedings of ISSAC 1995, pages 158-166. ACM Press, 1995.

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

10. F. Boulier and F. Lemaire. Computing canonical representatives of regular differential ideals. In Proceedings of ISSAC 2000, pages 38-47. ACM Press, 2000.

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

12. F. Boulier, F. Lemaire, and M. Moreno Maza. Well known theorems on triangular systems and the D5 principle. In Proc. of Transgressive Computing 2006, pages 79-92, Spain, 2006. University of Granada.

13. D. Bouziane, A. Kandri Rodi, and H. Maarouf. Unmixed-dimensional decomposition of a finitely generated perfect differential ideal. Journal of Symbolic Computation, 31:631-649, 2001.

14. G. Carra Ferro. Some properties of the lattice points and their application to differential algebra. Communications in Algebra, 15(12):2625-2632, 1987.

15. G. Carra Ferro. Some remarks on the differential dimension. Lecture Notes in Computer Science, 357:152-163, 1989.

16. O. Golubitsky. Grobner walk for characteristic sets of prime differential ideals. In V. Ganzha, E. Mayr, and E. Vorozhtsov, editors, Proceedings of the 7th Workshop on Computer Algebra in Scientific Computing, pages 207-221. TU Munchen, Germany, 2004.

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

18. E. Hubert. Factorization-free decomposition algorithms in differential algebra. Journal of Symbolic Computation, 29(4-5) :641-662, 20001.

19. E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms II: Differential systems. In Symbolic and Numerical Scientific Computing 2001, pages 40-87, 2003.

20. E. Hubert. Improvements to a triangulation-decomposition algorithm for ordinary differential systems in higher degree cases. In Proceedings of IS SAC 2004, pages 191-198. ACM Press, 2004.

21. E. Kolchin. Differential Algebra and Algebraic Groups. Academic Press, New York, 1973.

22. M. Kondratieva, A. Levin, A. Mikhalev, and E. Pankratiev. Differential and difference dimension polynomials. Kluwer Academic Publisher, 1999.

23. M. Kondratieva, А. V. Mikhalev, and E. V. Pankratiev. Jacobi's bound for systems of differential polynomials. Algebra, Moscow State University, pages 79-85, 1982.

24. S. Morrison. The differential ideal P] : M°°. Journal of Symbolic Computation, 28:631-656, 1999.

25. A. Ovchinnikov. Computation of characteristic sets of radical differential ideals. In V. Ganzha, E. Mayr, and E. Vorozhtsov, editors, Proceedings of the 7th Workshop on Computer Algebra in Scientific Computing, pages 371-378. TU Munchen, Germany, 2004.

26. A. Ovchinnikov. On characterizable ideals and characteristic sets. Contributions to General Algebra, 14:91-108, 2004.

27. A. Ovchinnikov and M. V. Kondratieva. On computation of characteristic sets of arbitrary radical differential ideals. In Proceedings of the conference Applications of Computer Algebra (АСА 2004), pages 38-48, 2004.

28. J. Ritt. Differential Algebra. American Mathematical Society, New York, 1950.

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

30. W. Sit. The Ritt-Kolchin theory for differential polynomials. In Differential Algebra and Related Topics, Proceedings of the International Workshop (NJSU, 2-3 November 2000), 2002.

31. W. Y. Sit. Differential dimension polynomials of finitely generated extensions. Proceedings of American Mathematical Society, 68(3):251-257, 1978.

32. A. Szanto. Computation with Polynomial Systems. PhD thesis, Cornell University, 1999.