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

• Овчинников, Алексей Игоревич
• кандидат физико-математических наук
• 2008

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

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, чтобы в соответствующем алгебраическом идеале лежала единица.

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

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.