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



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

Блинков Юрий Анатольевич

ИНВОЛЮТИВНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МОДЕЛЕЙ, ОПИСЫВАЕМЫХ СИСТЕМАМИ АЛГЕБРАИЧЕСКИХ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

05.13.18 - математическое моделирование, численные методы и комплексы программ

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

Саратов 2009

003471389

Работа выполнена в ГОУ ВПО «Саратовский государственный университет имени Н. Г. Чернышевского».

Научный консультант:

доктор физико-катематических наук профессор Гердт Владимир Петрович

Официальные оппоненты:

доктор физико-математических наук профессор Абрамов Сергей Александрович

доктор физико-математических наук профессор Михалев Александр Александрович

доктор физико-математических наук профессор Утешев Алексей Юрьевич

Ведущая организация:

Санкт-Петербургское Отделение

Математического института им. В. А. Стеклова РАН

Защита состоится «26» июня 2009 г. в 1530 на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по "адресу: г. Москва, ул. Орджоникидзе, дом 3.

С диссертацией можно ознакомиться в научной библиотеке Российского университета дружбы народов по адресу: 117198, г. Москва, ул. Миклухо-Маклая, дом 6.

Автореферат разослан « ^» мая 2009 г.

Ученый секретарь диссертационного совета

(С у^г^

Фомин М.Б.

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

Актуальность работы. Область применимости методов качественного анализа математических моделей, описываемых алгебраическими и дифференциальными уравнениями, весьма ограничена'1'. Гораздо более универсальным способом исследования дифференциальных систем является переход к их дискретным аналогам. В результате, такое понимание математического моделирования означает не просто уточнение количественных характеристик явлений, но также изучение основных их качественных свойств, прежде всего для нелинейных объектов. Проблемы численного моделирования не снимаются сами собой по мере появления все более мощных и дешевых компьютеров. Это связано, по меньшей мере, с двумя причинами: усложнением выдвигаемых как практикой, так и теорией задач и необходимостью проведения большого числа серий вычислительных экспериментов для достаточно полного изучения объекта. Поэтому разработка эффективных вычислительных алгоритмов всегда остается одной из ключевых задач математического моделирования. Для их конструирования широко используются методы, идеи и подходы, применяемые при построении исходных математических моделей. Эта связь хорошо прослеживается на примере очень широкого класса моделей - тех, которые сводятся к дифференциальным уравнениям.

Приведение систем алгебраических, дифференциальных и разностных уравнений к канонической форме, называемой базисом Грёбнера'2', представляет собой качественный аналитический метод исследования математических моделей.

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

[1] Самарский, А. А. Математическое моделирование: Идеи. Методы. Примеры. / А. А. Самарский, А. П. Михайлов.— 2-е, исправленное изд. — Физматлнт, 2001. — С. 320.

[2] Бухбергер, Б. Базисы Грёбнера. Алгоритмический метод в теории полиномиальных идеалов / Б. Бухбер-гер // Компьютерная алгебра. Символьные и алгебраические вычисления. — М. Мир, 1986. — С. 331-372.

конечного числа решений найти это число, а в случае бесконечного числа решений вычислить размерность пространства решений; находить алгебраические зависимости между уравнениями; в ряде случаев строить решения в явном виде.

Для систем уравнений полиномиального типа их инволютивная форма является специальным случаем базисов Грёбнера. Базисы Грёбнера являются универсальным алгоритмическим инструментом'3' во многих областях математики: алгебраическая геометрия, коммутативная алгебра, теория полиномиальных идеалов, теория инвариантов, автоматическое доказательство геометрических теорем, теория кодирования, целочисленное программирование, дифференциальные уравнения в частных производных, гипергеометрические функции, символьное суммирование, статистика', некоммутативная алгебра, численные (например вейвлет-) преобразования, теория управления и др. В настоящее время алгоритм построения базисов Грёбнера встроен во все современные системы компьютерной алгебры достаточно универсального характера: Magma, Axiom, CoCoA, Reduce, Macaulay, Maple, Mathematica, Maxima, MuPAD, SINGULAR.

Алгоритмы построения базисов Грёбнера имеют экспоненциальную сложность относительно числа переменных, как по времени вычислений, так и по требуемой памяти. По этой причине разработка алгоритмов построения базисов Грёбнера, позволяющих оптимизировать требуемые для их вычисления компьютерные ресурсы, приводит к расширению круга решаемых задач.

Цель работы. Разработка теории инволютивных алгоритмов для эффективного построения базисов Грёбнера как метода качественного исследования математических моделей.

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

[3] Buchberger, В. Grobiter Bases and Applications / В. Buchberger, F. Winkler. — Cambridge University Press, 1998. .

Методы исследований основаны на приведении в инволюцию систем многочленов и восходит к конструктивным методам, разработанным французскими математиками РикьеМ и Жане'5!. В работе также используются известные методы построения разностных схем и их обобщения, полученные с помощью техники базисов Грёбнера.

Достоверность и обоснованность. Разработана аксиоматическая теория инволютивного мономиального деления, на основе которой строго исследованы вопросы корректности и завершаемое™ полученных алгоритмов в зависи-, мости от свойств задаваемого инволютивного деления. Корректность работы инволютивных алгоритмов подтверждена также компьютерными расчетами на многочисленных примерах, взятых из международной базы данных'6'. Это база данных специально создана для тестирования программных продуктов, предназначенных для вычисления базисов Гребнера. Предложенный алгоритмический подход к построению разностных схем для дифференциальных уравнений, опирающийся на метод базисов Гребнера, позволил воспроизвести целый ряд хорошо известных разностных схем. Свойства найденных с помощью этого метода принципиально новых разностных схем строго исследованы теоретически. Теоретические результаты подтверждены численными расчетами на математических моделях физических процессов, допускающих точное решение. Научная новизна.

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

2. Разработан алгоритм построения минимальных инволютивных базисов,

[4] Riquier, С. Les Systèmes d'Equations aux Dérivées Partielles / C. Rlquier. — Gauthier-Villars, Paris, 1910.

[5] Janet, M: Systèmes d'équations aux dérivées partielles / M. Janet // Journals de mathématiques, 8e série.— 1920,-Vol. 3 -Pp. 65-151.

[6| The database of polynomial systems, http://www.math.uic.edu/~jan/demo.html.

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

3. При построении инволютивного базиса, значительная часть вычислений не приводит к получению нового элемента базиса. Установлены критерии равенства нулю инволютивной нормальной формы, позволяющие оптимизировать процесс вычисления.

4. Поиск мономиального делителя - одна из наиболее часто выполняемых операций при построении базисов Грёбнера. Найдены оптимальные структуры данных для быстрого поиска инволютивного делителя, представляющие собой деревья специального типа.

5. Минимальный инволютивный базис, в некоторых случаях, может значительно превосходить авторедуцированный базис Грёбнера по числу элементов, а следовательно и по требуемой памяти. Разработано новое моно-миальное деление, основанное на понятии немультипликативных степеней переменных, дающее более компактное представление базиса.

6. Разработан полностью алгоритмический метод построения разностных схем, использующий технику базисов Грёбнера. Данный метод является обобщением известных процедур построения разностных схем метода конечных объемов, Лакса, Лакса-Вендроффа и ряда других.

7. Для нелинейного уравнения околозвуковых течений Кармана-Фальковича найдена принципиально новая разностная схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и переключателей.

8. Для логистического отображения найдено значения параметра /х, при котором происходит образование 9-и периодических циклов. До настоящего времени'71 были найдены значения до п < 8.

(7) Kotsireas, /. S. Exact computation ot the bifurcation point bt of the logistic map and the bailey-broadhurst conjectures / I. S. Kotsireas, K. Karamanos // Journal Bifurcation and Chaos. — 2004. — Vol. 14. — Pp. 2417-2423.

Практическая значимость.

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

2. На основе предложенных алгоритмов создана специализированная система компьютерной алгебры CINV с открытым кодом, доступная для широкого использования и успешно применяющаяся в ОИЯИ1 и RWTH2 для различных научных и прикладных задач. Кроме того, GINV используется в программном модуле Janet, написанном на языке системы компьютерной алгебры Maple.

3. Программный модуль INVBASE, реализующий полиномиальные инволю-тивные алгоритмы, включен в качестве стандартного в систему компьютерной алгебры Reduce.

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

Основные результаты, выносимые на защиту.

1. Создана теория инволютивных базисов. Теория основана на понятии ин-волютивной делимости мономов, для которого сформулированы аксиомы и дополнительные свойства (нётеровость, непрерывность и конструктивность), обеспечивающие алгоритмичность построения инволютивных базисов. Доказано, что инволютивные базисы являются базисами Грёбнера специального вида.

2. Разработан новый алгоритм вычисления базисов Грёбнера, альтернативный классическому алгоритма Бухбергера, названный инволютивным и

'Объединенный институт ядерных исследований (Дубна, Россия)

2Рейнско-Вестфальский технический университет (Ахен, Германия)

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

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

4. Создана специализированная система компьютерной алгебры GINV с открытым кодом, написанная на языке С++ и организованная в виде модуля языка Python. Ядро системы составляют инволютивные алгоритмы. Система доступна для широкого использования и успешно применяется в ряде организаций для решения научных и прикладных задач. По скорости вычисления базисов Грёбнера система GINV является самой быстрой в мире среди систем с открытым кодом.

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

6. Путем вычисления разностного идеала, для нелинейного уравнения Кар-мана-Фальковича, описывающего околозвуковые течения в газовой динамике, найдена принципиально новая разностная схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и

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

Личный вклад соискателя. Все результаты, изложенные в единоличных публикациях, получены автором самостоятельно. Из совместных публикаций в диссертацию включены лишь те результаты, которые получены лично автором. Вклад автора в реализацию специализированной системы компьютерной алгебры GINV, модулей Janet и INVBASE является основным.

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

Гранты РФФИ: 98-01-00101-а инволютивный йнализ динамических систем со связями (1998-2000); 99-01-00192-а развитие кватернионных моделей и методов механики космического полета (1999-2000); 00-15-96691 поддержки ведущих научных школ (2000-2002); 01-01-00708-а компьютерные методы инво-лютивного анализа дифференциальных уравнений и их применение к калибровочным теориям поля (2001-2003); 04-01-00784-а компьютерное приведение нелинейных систем в инволюцию с приложением к обобщенной гамильтоно-вой динамике и построению разностных схем для уравнений в частных производных (2004-2006); 07-01-00660-а компьютерный анализ совместности систем уравнений с приложением к квантовым вычислениям, калибровочным моделям теории поля и численному решению уравнений в частных производных (2007-2009). .

Гранты Президента Российской Федерации: НШ-2339.2003.2 развитие и применение новых аналитических и численных методов в теоретической и математической физике; НШ-5362.2006.2 развитие и применение новых аналитических и численных методов в теоретической и математичёской физике.

Гранты ИНТАС: 93-0030 Computer algebra, symbolic and combinatorial tools in differential algebra and differential equations (1994-1995); 99-1222 Involutive Systems of Differential and Algebraic Equations (2000-2002).

Апробация работы. Основные результаты, полученные в диссертации, докладывались: на Международной конференции "Симпозиум по символьным

вычислениям IMACS" (Lille, Франция, 1993 г.); на совместных с МГУ семинарах по компьютерной алгебре в Лаборатории информационных технологий ОИЯИ (Дубна, 1994, 1998, 2001, 2002, 2003, 2004, 2005, 2006, 2007 гг.); на Международной конференции "Новые компьютерные технологии в системах управления" (Переславль-Залесский, 1994 г.); на Международной конференции "Интервальные и компьютерно-алгебраические методы в научных вычислениях Interval'94" (Санкт-Петербург, 1994 г.); Современные тенденции в вычислительной физике (Дубна, 1998, 2000 гг.); на Международных конференциях "Rhein Workshop on Computer Algebra RWCA" (Karlsruhe, Германия, 1994 г.; Sankt -Augustin, Германия, 1998 г.; Mannheim, Германия, 2002 г.; Basel, Германия, 2006 г.); на Международной конференции "Приложения компьютерной алгебры IM ACS/ АС А" (Санкт-Петербург, Россия, 2000 г.); в Высшей технической школе Рейна-Вестфалии RWTH (Аахен, Германия, 2001, 2003, 2006 гг.); на Международной конференции "Компьютерная алгебра и ее приложения в физике СААР'2001" (Дубна, 2001 г.); на пятом Международном конгрессе по математическому моделированию (Дубна, 2002 г.); на Международных конференциях "Компьютерная алгебра в научных вычислениях CASC" (Konstanz, Германия, 2001 г.; Passau, Германия, 2003 г.; Kaiamata, Греция, 2005 г.); на всероссийском семинаре "СЕТОЧНЫЕ МЕТОДЫ ДЛЯ КРАЕВЫХ ЗАДАЧ И ПРИЛОЖЕНИЯ" (Казань 2004 г.); на семинаре по компьютерной алгебре на факультете ВМиК МГУ им. М.В.Ломоносова (Москва, 2005 г.); на. Международной конференции "Symmetry in Nonlinear Mathematical Physics" (Киев, 2005 г.); на Международной конференции "Computer Algebra and Differential Equations" (Turku, Финляндия, 2007 г.); на семинаре по алгебре на механико-математическом факультете МГУ им. М.В.Ломоносова (Москва, 2007 г.); на Международной конференции "Полиномиальная компьютерная алгебра" (Санкт-Петербург, 2008 г.).

Публикации. По теме диссертации опубликовано 32 работы. Основные результаты представлены 8 в российских и 5 зарубежных журналах рекомендованных ВАК для представления результатов докторских диссертаций:

1. Жарков, А. 10. Инволютивные системы алгебраических уравнений / А. Ю.

Жарков, Ю. А. Блинков // Программирование. — 1994. — № 1. — С. 53-51

2. Zharkov, A. Yu. Involution approach to investigating polynomial systems / A. Yu. Zharkov, Yu. A, Blinkov // Mathematics and Computers in Simulation.

- 1996. - Vol. 42, no. 4-6. - Pp. 323-332.

3. Гердт, В. П. Инволютивные деления мономов / В. П. Гердт, Ю. А. Блинков // Программирование. — 1998. — Т. 24, № 6. — С. 22-24.

4. Gerdt, V. P. Involutive bases of polynomial ideals / V. P. Gerdt, Yu. A. Blinkov // Mathematics and Computers in Simulation. — 1998. — Vol. 45. — Pp. 519-542.

5. Gerdt, V. P. Minimal involutive bases / V. P. Gerdt, Yu. A. Blinkov // Mathematics and Computers in Simulation. — 1998, — Vol. 45.

- Pp. 543-560.

6. Гердт, В. П. Быстрый поиск делителя Жане / В. П. Гердт, Д. А. Янович, Ю. А. Блинков ■// Программирование. — 2001. — Т. 27, № 1. — С. 32-36.

7. Блинков, Ю. А. Метод сепарирующих мономов для инволютивных делений / Ю. А. Блинков // Программирование. — 2001.— Т. 27, № 3.— С. 43-45.

8. Блинков, Ю. А. Вычисление базисов Жане торических идеалов / Ю. А. Блинков // Программирование. — 2002. — Т. 28, № 5. — С. 65-68.

9. Gerdt, V. P. Janet-like monomial division / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra in Scientific Computing. — Springer Berlin / Heidelberg, 2005, — Vol. 3718 of Lecture Notes in Computer Science. — Pp. 174-183.

10. Gerdt, V. P. Janet-like Grobner bases / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra in Scientific Computing. — Springer Berlin / Heidelberg, 2005. - Vol. 3718 of Lecture Notes in Computer Science. - Pp. 184-195.

11. Блинков, Ю. А. Генерация разностных схем для уравнения Бюргерса построением базисов Грёбнера / Ю. А. Блинков, В. В. Мозжилкин // Программирование. — 2006. — Т. 32, № 2. — С. 71-74.

12. Гердт, В. П. О стратегии выбора немультипликативных продолжений при вычислении базисов Жане / В. П. Гердт, Ю. А. Блинков // Программирование,- 2007. - Т. 33, № 3. - С. 34-43.

13. Блинков, Ю. А. Специализированная система компьютерной алгебры GINV / Ю. А. Блинков, В. П. Гердт // Программирование. — 2008. — Т. 34, № 2. - С. 67-80..

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и одного приложения. Работа изложена на 251 страницах машинописного текста, из них основного текста 176 страниц. Работа содержит 23 рисунка, 10 таблиц, 20 описаний алгоритмов и одного приложения. Список литературы включает 281 наименование.

Содержание работы

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

В последующем будут использованы следующие обозначения: И = К[Х] кольцо полиномов над полем К с независимыми переменными X = х\,..., хп,

/, д, Л, q, г полиномы из К;

^ б, Я конечные подмножества из И;

(.Р) идеал из И порожденный

М = {хI1 • • • х^Н с^ е 2>о} - множество мономов;

и, у, ги, в, £ множество мономов или термов;

и, V, IV конечные подмножества из М;

У допустимое мономиальное упорядочение с порядком переменных XI у ...у

и | V означает, что моном и делит моном и; ис. V означает, что моном и делит моном и и и ^ V. В первой главе кратко рассмотрена теория базисов Грёбнера. Сформулирована концепция инволютивного деления и доказаны его основные свойства. Разработаны основные алгоритмы, использующие инволютивное деление, и доказаны их корректность и завершаемость. Введено новое деление, названное степенным делением Жане, и исследованы его основные свойства.

Определение I. Инволютивное деление С задано на М, если для любого

конечного множества и с М и для любого и е и определен подмоноид £(и, и) С М, удовлетворяющий условиям:

1. (Уи, V £11) [и£(и, и)Г\у£{ь,и)^®=>ие у£{у, ¡7) или «е«£(и,(/)];

2. (Уг; е [/) [у е и£(и, и) £(у, и) С £(и, [/)];

3. (V« € К) [К С I/ =>• £(и, [/) С £{и, V)].

Определение 1 для каждого и€ и задает разбиение множества переменных

{хъ...,хп} =Мс(щи)иЛГМс(и,и)

на два непересекающихся множества мультипликативных Мс(и, {/) и немультипликативных ММс{и, II) переменных. В результате, инволютивное деление для монома может быть задано через определение множеств мультипликативных и немультипликативных переменных.

Пусть заданы инволютивное деление £ и V, тогда для каждого и £ II £(и, II) С М определяет множество всех мультипликативных мономов для и. В этом случае условие V £ и£(и, I/) будем записывать в виде и\с V и говорить, что моном и является инволютивным делителем монома V.

В дальнейшем будем использовать обозначение V = и х -ш, если и — ин-волютивный делитель у. В этом случае, моном ш будем называть мультипликативным множителем. В случае, когда и является делителем у в обычном смысле, но не является его инволютивным делителем мы будем использовать обозначение ^ = и ■ ю. В этом случае т называется немультипликативным множителем для и.

Обычное деление мономов, очевидно, удовлетворяет условию 1 в определение 1, записанному через инволютивное деление

(\Л1,И1 £ и)(\/ги е М) \u\cw \\ щ \с ш =>• и |£ 111 или 1x1 | с и],

только в случае одной переменной. Простейший контрпример для двух переменных: х | (ху) и у | (ху), но х | у и у | х.

Рассмотрим три различных примера инволютивных делений, соотвествую-щих разбиениям, введеным Жане и Томасом для анализа систем дифференциальных уравнений.

Определение 2. Разбиение Томаса'8'. На U переменная ац считается мультипликативной для u£ U если

degj(ii) = max{degj(u) | и е U}

и немультипликативной в противном случае.

Определение 3. Разбиение Жаке'5'. Разобьем U на подмножества, задаваемыми числами d0, d\,..., d» € Z>o:

[d0) db..., di] = {u e U I d0 = 0, di = deg^u),..., d» = deg^it)}.

Переменная Xi считается мультипликативной для и € [do,db... ,dj_i] если

degj(u) = maxideg^v) | v e [d0, db ..., di_i]}

и немультипликативной в противном случае.

Определение 4. Разбиение Поммаре'9'. Для монома xf1--- xdkk с dk > 0 переменные xj с j > к считаются мультипликативными, a Xj с j < к немультипликативными. Для и = 1м все переменные мультипликативные.

Применяя определение 1 можно построить еще два разбиения переменных.

Определение 5. Разбиение I. На U переменная х^ немультипликативна для и eU, если имеется v Ç.U такой, что

xt ■ '- х'Ьи = lcm(u> 1 < ™ < N2]> di > 0 (1 < J <

{xjj,..., и мультипликативна в противном случае.

Определение 6. Разбиение II. Для монома и — х{1 ••■ xf1 переменная я* будет мультипликативной если dj = max{dj,..., dn} и немультипликативной в противном случае.

[8] Thomas, J. Deferential Systems / J. Thomas. — American Mathematical Society, New York, 1937.

(5] Janet, M. Systèmes d equations aux dérivées partielles / M. Janet // Journals de mathématiques, 8e série. —

1920. — Vol. 3 — Pp. 65-151. |9] Поммаре, Ж. Система уравнений с частными производными и псевдогруппы Ли / Ж. Поммаре. — М. Мир, 1983.-С. 400.

Замечание 7. Разбиения Томаса, I и II не зависят от упорядочения переменных Х(. В отличии от них, разбиения Жане и Поммаре основаны на выбранном упорядочении переменных у х2 У ■ • ■ У хп.

Разделение переменных на мультипликативные и немультипликативные в случае разбиений Томаса и Жане зависит от остальных мономов множества и. Напротив, разбиения Поммаре и II не зависят от остальных мономов множества и и по этой причине называются глобальными.

Для обозначения рассматриваемых делений будем использовать сокращения

Т, .7,7м, II.

Пример 8. 11 = {ху, т/2, г) (х У у У г).

Таблица 1. Разбиения Томаса, Жане, Поммаре, I и II

МТ ЯМТ ММа М-р ЯМ-р МI ММх Ми ММц

X2 X У, г - - X У, г X У, г

ху У Х,2 У, * X X У Х,2 Х,У г

г г У, г X г У, г X г

Предложение 9. Мономиальные деления Томаса, Жане, Поммаре, I, II являются инволютивными.

Определение 10. и называется инволютивно авторедуцированным по делению С или С—авторедуцированным, если это множество не содержит инволю-тивных делителей своих элементов кроме них самих.

Предложение 11. Инволютивное авторедуцированное множество может содержать не более одного инволютивного делителя для любого заданного монома.

Определение 12. Для заданного инволютивного деления С множество II называется инволютивным или С—инволютивным, если для любого и е и, умноженного на любой моном, существует инволютивный делитель в и.

Определение 13. Обозначим через С (£/) дискретный конус и„е[/иМ порожденный и. Множество ип€циС(и,и) будем называть инволютивным конусом, порожденным и и записывать Сс(17).

Определение 14. Инволютивное деление £ называется нётеровым, если и является конечно порожденным относительно £.

Предложение 15. Для нётерового инволютивного деления £, каждый мономи-альный идеал и имеет конечный инволютивный базис.

Предложение 16. Деления Томаса, Жане, I, II нётеровы.

Определение 17. Умножение и е {/ на переменную х называется продолжением и. Для инволютивного деления, определенного н,а и, продолжение называется мультипликативным, если х мультипликативно для и к немультипликативным в другом случае.

Определение 18. и называется локально инволютивным относительно деления С, если

(\/иеи)(\/х{еЯМс{и,и)){Зуеи)[у\си-х^. (1)

Определение 19. Инволютивное деление £ будем называть непрерывным, если для любого конечного множества £/ и для любой конечной последовательности {"»}(1<г<<:) элементов из и выполнено

(\/г < к){Зж,- € ЯМс{щ, Щ) [щ+1 |с Щ • я? Щ для i ф (2)

Теорема 20. Если инволютивное деление £ непрерывно, то из локальной ин-волютивности любого и следует его инволютивность.

Следствие 21. Деления Томаса, Жане, Поммаре, I и II непрерывны.

Определение 22. Будем называть непрерывное инволютивное деление £ конструктивным, если

(VII е и)(Ух] 6 и))(ь -Х^аи- х*) [и ■ X€ ииеи и С{и, и)}

и выполнены условия:

(Чт е ииеииС{и, и)) [и • зц $ иС{щ и и {и/})]. (3)

Предложение 23. Деления Томаса, Жане, Поммаре, I и II конструктивны.

Теорема 24. Для конструктивного деления С процедуру пополнения и до £-инволютивного множества II э 17 можно провести немультипликативными продолжениями его элементов.

Определение 25. На Р мультипликативные и немультипликативные переменные для / € Р определяются по старшему моному 1ш(/) полинома / относительно у и множеству 1т(.Р) старших мономов Р.

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

Для записи £—нормальной формы / по модулю С? введем обозначение №/;(/, б), а обычную нормальную гребнеровскую форму'2' будем записывать ввиде №(/,£).

Определение 26. Р называется инволютивно авторедуцированным по инво-лютивному делению С, или С—авторедуцированному, если множество является С—авторедуцированным и каждое / € Р не содержит мономов имеющих инволютивного делителя во множестве 1ш(1?).

Теорема 27. Если ^ £-авторедуцированно, то ИГс{р,Р)> — ° тогда и только тогда, когда р представляет собой конечную сумму термов вида

с 1т(иу) ф для эфк.

Следствие 28. Если Р С—авторедуцированно то, тогда С— нормальная форма для любых полиномов Р1,Р2 и р имеет следующие свойства:

1. Единственность-, если /11 = ^^р, Р) и /12 = ^¿(р, F) то, тогда /11 = /12.

[2] Бухбергер, Б. Базисы Грёбнера. Алгоритмический метод в теории полиномиальных идеалов / Б. Бухбер-гер // Компьютерная алгебра. Символьные и алгебраические вычисления. — М. Мир, 1986. — С. 331-372.

(4)

2. Линейность: + Рг, = ^(ръ + №£(р2, -Р).

Определение 29. £-авторедуцированное множество Р называется С-инволю-тивным базисом идеала (Р), если

Следствие 30. Если множество Р1 инволютивно, то р € (Р) тогда и только тогда, когда ИГДр, Р) = 0. Также имеет место равенство = (Р).

Теорема 31. С—авторедуцированное множество Р инволютивно относительно непрерывного деления С, тогда и только тогда, когда выполнены следующие условия локальной инволютивности

Теорема 32. Если Р является С—инволютивным, то имеет место равенство

Следствие 33. Инволютивный базис есть базис Грёбнера.

Предложение 34. Если инволютивное деление С нётерово, то тогда любой полиномиальный идеал (Р) имеет конечный £—инволютивный базис.

Следующая теорема дает инволютивную форму для цепного критерия Бухбер

Теорема 35. Пусть задано Р £—авторедуцированное множество полиномов и д ■ х - немультипликативное продолжение д е Р. Тогда ^¿(д • х, Р) = 0 если

(V/ б б м) и, л = о].

(5)

(У/ е € ММС{ 1ш(/), 1ш(^))) №(/ • ц, Р) = 0]. (6)

(Ур б И) =

(7)

(У/г € ^)(Уи е М) [1т(/г) • и -< 1т(д ■ х) => ОТ£(Л • и, F) = 0],' (8)

1т(/0) 11т(/), 1тЫ | И5)

(3/, /о, да е Р) 1т(/) 1т(д ■ х), 1ст(/0, д0) -< Щд ■ х)

Алгоритм 1 1пуо1иИуеВа51з(.Р, -<, С)_

Вход: Р конечное множество полиномов Выход: й инволютивный базис идеала (/•') 1: й := Аик>11ес1исе(Р) 2: Т := 0

3: для всех д е б 4: Г:=Ги{(Р,1тЫ,0)}

5: пока существуют (д,и,Р) еТ и х € Л/Мс (1т(д), 1т(С)) \ Р

6: выбрать (д,и,Р) и х с наименьшим 1т(д) •х относительно -<

7: Г;=Г\{(г,и,Р)}и{(5,и,Ри{1})}

8: если существует / е (/, ч, £>) € Т такое, что 1т(/) |с 1т(<7 • х) то

9: если 1ст(и, ь) = 1т(д) ■ х то

10: /1 := ^¿(д ■ х, в)

И: если Иф 0 то

12: Г:=Ти {(Л,1т(/г),0)}

13: иначе

14: :=№£((/-ж, в)

15: Т--Т и {(й,и, 0)}

16: . в := Аи^Кеаисе£(С и {/»})

17: д := Т

18: Т •- 0

19: для всех д € й

20: если существует (/, и, Р) 6 <Э такой, что 1т(/) = 1т(д) то

21: выбрать д-1 € (3 такое, что 1т(<71) и

22: Г:=Ти{(5,1т(31),Р)}

23: иначе

24: Т \~T\J {(<7,1т(д),0)}

Алгоритм 1 был включен с именем INVBASE в стандартную библиотеку системы Reduce, начиная с версии 3.5.

Определение 36. Немультипликативная степень. Разобьем U на подмножества аналогично определению 3. Для каждого и£[/и1<г<п рассмотрим hi(u, U) € Z>o определенного по формуле

hi{u, U) = maxjdeg^) | и, v е [do, ■ ■ ■, <£-i]} - deg^u).

Если hi(u,U) > 0, то тогда степень xf, где

k = min{degj(u) - deg^u) | v,u £ [d0,.. ■ A-i], deg^u) > deg^u)}

будем называть немультипликативной степенью для и.

[2] Бухбергер, Б. Базисы Грёбнера. Алгоритмический метод в теории полиномиальных идеалов / Б. Бухбер-гер // Компьютерная алгебра. Символьные и алгебраические вычисления. — М. Мир, 1986. — С. 331-372.

Будем обозначать через ЛЛМТ-^и, 17) все немультипликативные степени для

и е и.

Определение 37. Степенное деление Жане. Для и £11 элементы моноида

ММ(и,и) = {г; € М | (Эш £ ММГ(и, и)) [и» | «]} (10)

будем называть Зь—немножителями, а элементы МР(и,и) = М \ММ(и, £/) соответственно Зь~множителями, и будем называть степенным делителям Жане или Зь~делителем монома ги € М и записывать и ги, если ю = и - V

Предложение 38. Для [/ с элементом и € V игоеМиз делимости по Жане ги на и следует делимость по степенному делению Жане. В общем случае, обратное неверно.

Предложение 39. Моном ги не может иметь два различных ^¿-Делителя на любом множестве мономов.

Для степенного деления Жане в диссертации показано выполнение алгоритмических свойств: непрерывности, нётеровости и конструктивности.

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

Определение 40. £.—инволютивный базис {/ будем называть минимальным, если для любого другого £—инволютивного базиса V с (С/) выполнено включение и СУ.

Предложение 41. Пусть С конструктивное инволютивное деление определенное на и, то тогда (и) имеет минимальный С—инволютивный базис.

Определение 42. Пусть С конструктивное инволютивное деление, инволютивный базис й идеала ((?) будем называть минимальным, если 1ш(С) минимальный ¿-инволютивный базис мономиального идеала, порожденного {1т(/) | / 6

(С)}-

Пусть даны .Р и конструктивное инволютивное деление С. Тогда для совместимого со степенью допустимого упорядочения >-, представленный в диссертации алгоритм, строит минимальный инволютивный базис (Р) если этот базис конечен. В случае нётеровости инволютивного деления С алгоритм строит базис для любого допустимого упорядочения.

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

Определение 43. ю называется сепарирующим для V С и и заданного инволютивного деления С если он удовлетворяет следующим условиям:

1. К =

2. Уи € VI, $у е иС(и, и), то тогда ю | г>;

3. Уи £ Уг, $у е иС(и, и), то тогда т \ V.

Поскольку условие 3 является отрицанием условия 2 для множеств из определения 43 следует У\ П — 0.

На приведенных ниже рисунках показаны сепарирующие мономы для делений Томаса и Жане для С/ = {х2у, хг, у3, уг,г2} с порядком переменных х У у У г. Мономы,, расположенные в листьях, принадлежат исходному множеству. Согласно определений? 43 моном расположенный в вершине является сепарирующем. Для всех мономов в листьях в его правом поддереве не может находиться инволютивный делитель монома, который имеет делителем в обычном смысле моном, расположенный в вершине.

У

У

,3

я" / ч

х

х2у

Ч

ху

/ \

ху у3

/ V

/ ч

хг х2у

хг

.2

уг

Рис. 1. Пример деревьев для деления Томаса и Жане

Теорема 44. При выполнении условий определения 43 следующие два утверждения равносильны:

1. Уи е Уг и то тогда и> \ V и V е и£(и, 17);

2. Ми е У2 и (Уги1, 11)2) IV = следует £ С(и, 17) н гиг \ и.

Данная теорема дает конструктивный метод нахождения сепарирующих мономов. Введем следующие обозначение: gcd(иС(и, 17),ш) = V если (у е иС(и, 17), ги) и (Уя е иС(и, 17), я | ш) следует, что я | V.

Следствие 45. При выполнении условий определения 43 необходимо и достаточно:

1. (Уи£ К) [7),-ш) = и>;

2. (Уи е У2) gcd(u£(u1 17),-ш) ф ю.

Для некоторых видов инволютивных делений возможно построение специализированных деревьев поиска. По определению 3 деления Жане множество мономов II разбивается на группы. На рис. 2 показано бинарное дерево, которое будем называть деревом Жане. Его структура отражает разделение элементов в 17 на группы, которые отсортированы по степенях переменных в пределах каждой группы. Такая структура данных позволяет эффективно искать делитель Жане и вычислять мультипликативные переменные для элементов 17.

Дерево Жане показано на рисунке 2. Мономы множества и расположены в листьях дерева. Движение по левой ветки дерева увеличивает степень переменной, а по правой выбирает следующую переменную согласно заданному порядку переменных.

/ \

х1

/ "ч

X2 Х1у°

"ч Ч Ч

х2у хг Х°у°

/ ч

Х^у1 г2

/ Ч

у3 . у2

Рис. 2. Пример дерева Жане (в вершинах мономы)

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

Теорема 46. Пусть й - максимальная полная степень мономов от п переменных, из которых состоит конечное множество {/. Тогда временная сложность алгоритма поиска по "дереву Жане" и алгоритма бинарного поиска может быть выражена следующим образом

¿7-<Ну18ог(У) = 0((1 + п),

¿ВтагуБеагсЬ(У) = 0(п((<* + п) + п) - П 1с^(п) - сЛс^(б/))).

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

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

Система компьютерной алгебры GINV (сокращение от Gröbner INVolutive), разработанная для исследования и решения систем алгебраических, дифференциальных и разностных уравнений полиномиального типа методами их приведения в инволюцию. В основе системы лежат авторские алгоритмы построения инволютивных базисов Жане и степенных базисов Жане для полиномиальных идеалов и модулей, а также приведенных базисов Грёбнера. GINV состоит из библиотеки программ на языке С++, являющейся модулем языка Python. GINV доступен на сайте http://invo.jinr.ru/ginv/ и распространяется на условиях GPL v2 .

Из внешних библиотек используется кроссплатформенная библиотека GMP для арифметики целых, рациональных и чисел с плавающей точкой произвольной точности. Документация системы GINV состоит из "руководства пользователя" и "руководства разработчика". Первая из них построена с помощью стандартных средств для документирования модулей языка Python, а вторая с помощью системы Doxygen. Документация поддерживается на двух языках, русском и английском, и доступна на сайте http: //invo. jinr.ru/ginv/ в форматах pdf и html. Руководство разработчика содержит более 1000 страниц формата A4.

Алгоритмы построения базисов Грёбнера имеют экспоненциальную сложность как по времени выполнения, так и по требуемой памяти. Поэтому, при реализации этих алгоритмов бывает трудно соблюсти их универсальность, не забывая при этом об эффективности. Как показывает сравнение GINV с реализацией на С этого удалось достичь. Сравнение результатов расчета с последней версией GINV доступны на вышеуказанном сайте.

На рисунке 3 изображен образец (шаблон проектирования), применяющийся для организации структур данных при использовании в алгоритмах. Образец позволяет в классах выделять информацию и поведение, общее для всех объектов класса, в интерфейсный класс. Конкретная реализация образца применяется в GINV для описания мономов, коэффициентов, полиномиальной арифме-

тики, инволютивных делений и критериев равенства нулю нормальной формы.

Рис. 3. Основной образец

В названии групп определяющих порядки на мономах используются следующие обозначения: Lex - лексикография, DegRevLex - по полной степени и затем обратная лексикография, Elim - разделение по выбранной независимой переменной, Pos - разделение по выбранной зависимой переменной, Pot -"позиция старше терма" - упорядочение сначала по зависимым переменным, а затем по независимым, Тор - "терм старше позиции" - упорядочение сначала по независимым переменным, а затем по зависимым, Byte - степень монома может быть размещена в одном байте.

Допустимые порядки на мономах можно разделить на следующие группы:

Исключающие упорядочения: Lex, Elim, PosElim, PotLex, PotDegRevLex, TopLex и TopElim.

Упорядочения, совместимые с полной степенью: DegRevLex, TopDegRevLex, DegRevLexByte и TopDegRevLexByte.

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

В названии групп для коэффициентов используются следующие обозначения: Z - целые числа, Q - рациональные числа, ModularShort - числа по модулю (квадрат модуля при этом умещается в машинное слово), Gmp - используется библиотека GMP, AlgebraicFieldExtension - расширение алгебраического

поля задаваемое многочленом, One - один параметр, Two - два параметра, N - п параметров.

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

Поле: GmpQ, ModularShort, AlgebraicFieldExtensionGmpQ и AlgebraicField-ExtensionModularShort.

Кольцо: GmpZ, OneParameterGmpZ, OneParameterModularShort, TwoPara-meterGmpZ, TwoParameterModularShort, NParameterGmpZ и NParameterMo-dularShort.

Четвертая глава посвящена исследование математических моделей.

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

Этот метод позволил обобщить метод конечных объемов, схемы Лакса и Лакса-Вендроффа. Продемонстрировал возможность построения многошаговых схем и схем с переключателями. Для уравнения околозвуковых течений Кар-мана-Фальковича получена схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и переключателей. При одномерном течении в канале с прямым скачком уплотнения зона ударного перехода имеет протяженность порядка шага сетки.

Рассмотрим применение техника базисов Грёбнера для генерации схем типа Лакса на примере уравнения Бюргерса

Щ + fx = v ихх, v — const (11)

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

24

для уравнения (II) и интегральных связей функций и их производных

Щ" + 1х] = V их

я

Щ]Т = и]+1~ и]1 2/г "+1 Ь, = /"+2 — /]' 1их ™+11г = и'1+2-и?

2ихх И

их 2 ] •

Здесь И — Кч — /11, г = Т2 — п - шаги по переменным х и Ь, а п, ^ номера узлов сетки по х и £ соответственно. Через и обозначенно место для замены Лакса. Заменяя во втором уравнении в системе (12) значение и с предыдущего временного слоя средним значением соседних точек по оси х, получим систему разностных соотношений для вывода схемы типа Лакса

2ду+1л = (13)

2 их]+1Н = и]+2-и]

О,, п и _ п _ „ п ^ахх и — "х ¿+2 х 3 '

Выбирая допустимое упорядочение >- для функций ихх У их >- щ >- /х >- и >-/ с «позицией старше терма», получим в качестве элемента базиса Грёбнера разностное соотношение

2И&1 -К+3 + и]+1) /"+з — /"+1 ... ц"+4-2""+а + Ц"

2г 2/1 4/12

(14)

содержащие только искомые функции и и /. Соотношение (14) является классической схемой Лакса для уравнения (11).

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

производных ихх, их, fx общее количество различных вариантов равно 8 с 6 различными схемами.

Газовая динамика рассматривает теорию трансзвуковых течений, когда характерное число Маха Мх мало отличается от 1. Двумерное нестационарное течение невязкого газа в околозвуковом приближении может быть описано потенциалом скорости ip, который удовлетворяет уравнению Кармана-Фальковича

Ч>хх{К - (7 + IV*) + Ууу = О,

где X,у -декартовы координаты, К = (1 — - параметр трансзвукового

подобия, S - характерный угол наклона вектора скорости к невозмущенному потоку, 7 > 1 - показатель адиабаты. Уравнение Кармана-Фальковича относится к смешанному типу: эллиптическому при К > (7 + 1)^г и гиперболическому при К> (7 + 1 )ipx.

В нестационарном варианте при медленном изменении параметров потока по времени t уравнение Кармана-Фальковича переходит в уравнение Линя-Ре-йснера-Тзяна'11,12'

2Vit + <Рхх{К - (7 + l)Vs) + <Руу = О-

Это уравнение линейной заменой координат легко свести'13,14' к уравнениям газовой динамики:"коротких волн" и нелинейной акустики.

Представим уравнение Линя-Рейснера-Тзяна в интегральной форме для построения разностной схемы, позволяющей решать нелинейное уравнение Кар-

[10] von Karman, Т. Collected works / T. von Karman. — Von Karman Institute, Rhode St. Genese, 1975.

[11] Lun, С. С. Non-steady motion of a slender body in a compressible (luid / С. С. Lun, E. Reissner, H. S. Tslen // lournal of Mathematic and Physics. — 1948. — Vol. 27, no. 3.

[12] Тзян, X. Ш. О двумерном неустановившимся движении тонкого тела в сжимаемой жидкости / X. Ш. Тзян, Ц. Ц. Лин, Е. Рейснер//Газовая динамика. — М. Мир, 1950. — С. 181-196.

[13] Блинков, Ю. А. Редукция нестационарного трансзвукового уравнения к квазистационарному / Ю. А. Блинков, И. А. Чернов 11 Аэродинамика: Нелинейные проблемы. Межвуз. науч. сб.— 1988.— Т. 11(14).— С. 110-131.

[14] Фущич, В. И. Точные решения некоторых уравнений газовой динамики и нелинейной акустики / В. И. Фущич, В. К. Репета // Scientific Works—2002.— Vol. 4,— Pp. 267-273,

dxdy = О. (15)

мана-Фальковича методом установления.

¿п+1 / \ tj+2 Ук+a "+1

| J^ifa + ^-iliil^dyjdi- J J (2^+ </>,)

in \Г / ж,- V* <

Ln

Добавляя интегральные соотношения и используя для интегрирования формулу трапеций для ^px-,lPy< а также формулу среднего значения для <pt получим в операторной форме для уравнения (15) соотношения

(-(Г, - ТХТ$ о Щ + (Т£Ту - Ту) о {К<рх - ■ 2ДЛД*-

-(Г, - 1)(7£Г„ - Г„) О 2ip • 2ДЛ - Г,Г„ О щ • 4Д/12 = О (Tx + l)o4>x.f = {Tx-l)oy (TB + l)oVB.M = (Ty-l)oV 71 о • 2Дг = (Гг2 - 1) о <р

Выбирая допустимое лексикографическое упорядочение сначала по функциям <рх >~ Vy >~ ft </>> затем по переменным Тх УТу>- Tt, построим базис Грёбнера, последнее уравнение которого, является искомой разностной схемой:

(<Р"+п - Щь + ■ Щк - Щ-П - ^И+и

+ ~ + ty-lM - Щ-lk + W - 4>T-lk - <p]k + fUk) - «ifc- Щ-ik + <Pj-lk)m\+ (16) (¥>?* ~ Щ-ik + <p"-2k) ■ [((vy+it - щк + vUk)(K ~ ЩЬЩ+и

WXlk --+- wt1 -щк+^fil = o- ■

Заметим, что разностная схема (16) обладает полной консервативностью по построению и не содержит переключателей обычно используемых при расчете трансзвуковых течений'15'.

Рассмотрим в качестве примера одномерное течение в канале с прямым скачком уплотнения с результатом расчета приведенным на рисунке 4. Полученные

[15] Jameson, A. Transonic flow calculations / A. Jameson // Numerical Methods In Fluid Dynamics / Ed by H. J. Wirz, J. J. Smolderen.— Hemisphere, 1976, — Vol. 87 of von Karman Institute ¡or Fluid Dynamics Lecture Series. — Pp. 1-87.

0.75

н

9-

0.25

0.5

О

0 0.2 0.4 0.6 0.8 1

х

точное решение

начальное приближение

решение полученное методом установления

Рис. 4. Решение задачи с одномерной ударной волной

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

Логистическое отображение является является дискретным аналогом непрерывного логистического уравнения Ферхюльста

Логистическое отображение (17) отражает тот факт, что прирост популяции происходит в дискретные моменты времени.

Нахождение таких значений ц при которых возникает смена поведения логистического отображения является сложной вычислительной задачей'7'. Она

17] Kotsireas, I. S. Exact computation oi the bifurcation point 64 ol the logistic map and the bailey-broadhurst conjectures / I. S. Kotsireas, K. Karamanos // Journal Bifurcation and Chaos.— 2004.— Vol. 14,— Pp.2417-2423.

шаблоном в до- и сверхзвуковых областях.

z„+l — п(1 ®п)>

(17)

может быть описана следующей системой уравнений

■

Х2 = №1(1 — ¡гг)

хз = №2(1 - х2)

П Л (18)

Хп = -хп-х)

XI = цхп(1 - хп) к= 1

Для решения системы 18 можно построить базис Грёбнера, а затем, используя тот факт, что система имеет конечное число корней, средствами линейной алгебры получить полином от переменной /х. Нахождение действительных корней полинома представляет собой, с вычислительной точки зрения, значительно более простую задачу.

С помощью системы йШУ было впервые найдено значение /х = 3.687196... при котором возникает бифуркация для п = 9.

В заключении сформулированы основные результаты, выносимые на защиту.

В приложении приведено "Руководство пользователя" специализированной системы компьютерной алгебры СШУ.

"ИНВОЛЮТИВНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МОДЕЛЕЙ, J л ОПИСЫВАЕМЫХ СИСТЕМАМИ АЛГЕБРАИЧЕСКИХ И /С/ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ"

Аннотация

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

Для повышения эффективности вычислений разработан новый алгоритмический подход к построению базисов Грёбнера, альтернативный классическому методу Еухбергера. В его основе лежит новое математическое понятие — ин-волютивное деление мономов. Это понятие обобщает известные в литературе разделения переменных, используемые для приведения в инволюцию дифференциальных систем.

Описываемые в работе методы позволяют эффективно проверять совместность, исследовать структуру пространства решений, а в ряде случаев находить и сами решения рассматриваемых систем уравнений. Разработанные оригинальные алгоритмы и типы данных для построения инволютивных базисов Гребнера реализованы в виде специализированной системы компьютерной алгебры GINV (Groebner INVolutive).

"INVOLUTIVE METHODS APPLIED TO MODELS DESCRIBED BY SYSTEMS OF ALGEBRAIC AND DIFFERENTIAL EQUATIONS"

Abstract

In the given paper to investigate mathematical models which are described by systems of algebraic, differential and in some cases by difference equations a theory of modified Grobner bases called involutive is presented. The involutive bases are oriented to the investigation indicated.

To increase efficiency of computation, a new algorithmic approach to construct« of Grobner bases developed which is alternative to the classical Buchberger method. The approach is based a new mathematical notion of involutive monomial division. This notion generalizes partitions of variables used in the literature for completion of partial differential equation systems to involution.

The methods described in the paper allow effective verification of the consistence of a given system, to study the structure of its solution space, and in certain cases to find the solutions. The original algorithms and data structures for efficient construction of the involutive Grobner bases have been implemented in the specialpurpose computer algebra system GINV (Groebner INVolutive).

Введение

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

Основные обозначения и определения

Глава 1. Инволютивное деление и инволютивные базисы

1.1. Базисы Грёбнера

1.2. Инволютивное деление мономов.

1.3. Инволютивный базис

1.4. Степенное деление Жане.

Глава 2. Алгоритмы и структуры данных.

2.1. Минимальный инволютивный базис

2.2. Быстрый поиск делителя.

2.3. Инволютивный базис торических идеалов

2.4. Вычислительные стратегии построения инволютивного базиса

Глава 3. Специализированная система компьютерной алгебры GINV.

3.1. Описание основных структур

3.2. Примеры

3.3. Maple пакет Janet

Глава 4. Исследование математических моделей.

4.1. Метод конечных объемов для уравнения высших порядков

4.2. Генерация разностных схем для уравнения Бюргерса.

4.3. Логистическое отображение

Область применимости методов качественного анализа математических ' " моделей весьма ограничена [269]. Гораздо более универсальным способом исследования моделей является переход к дискретным аналогам исходных моделей. В результате, такое понимание математического моделирования означает не просто уточнение количественных характеристик явлений, но также изучение' основных их качественных свойств, прежде всего для нелинейных объектов. Проблемы численного моделирования не снимаются сами собой по мере появления все более мощных и дешевых компьютеров. Это связано, по меньшей мере, с двумя причинами: усложнением выдвигаемых как практикой, так и теорией задач и необходимостью проведения большого числа серий вычислительных экспериментов для достаточно полного изучения объекта. Поэтому разработка эффективных вычислительных алгоритмов всегда остается одной из ключевых задач математического мо* делирования. Для их конструирования широко используются методы, идеи и подходы, применяемые при построении исходных математических моделей. Эта связь хорошо прослеживается на примере очень широкого класса моделей - тех, которые сводятся к дифференциальным уравнениям.

Инволютивные методы построения базисов Грёбнера систем алгебраи- • ческих, дифференциальных и разностных уравнений позволяют проверить совместность и, в ряде случаев, построить решение систем. Базисы Грёбнера позволяют без явного построения решений системы уравнений:

• выполнить проверку уравнения на корнях системы уравнений с учетом и без учета кратности;

• провести сравнение уравнений на корнях системы уравнений;

• определить размерность пространства решений системы, а в случае конечного числа решений найти точное число с корней с учетом и без учета кратности, а также число действительных корней;

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

Базисы Грёбнера стали универсальным алгоритмическим методом решения задач коммутативной алгебры и алгебраической геометрии [62, 63, 68, 154, 260]. Базисы Грёбнера легко обобщается на кольца линейных дифференциальных и разностных операторов [49, 186], а также на идеалы (и модули), порожденные линейными дифференциальными и разностными многочленами [150].

В ряде случаев, метод базисов Грёбнера также допускает обобщение на кольца некоммутативных [171] многочленов, алгебры и супералгебры Ли ( базисы Грёбнера-Ширшова) [22, 38, 244, 276] и на отдельные дифференциальные идеалы [51, 173].

Исторически, первая работа выполненная в направлении создания теории базисов Грёбнера была сделана в 1900 году [122]. Допустимое мо-номиальное упорядочение было введено Макколи (Macaulay) в 1927 году [160]. В 1939 году [127] Грёбнер (Grobner) использовал допустимое мономиальное упорядочение для нахождения базиса фактор-кольца для нульмерного идеала. Базисы Грёбнера были введены Бухберге-ром (Buchberger) в его диссертации [43]. Бухбергером в его последующих работах [44, 45, 46, 47, 48, 245] алгоритм построения базисов Гребне-ра был применен к исследованию систем полиномиальных уравнений и построению для них канонического вида. Усовершенствования алгоритма Бухбергера (например применение критериев равенства нулю нормальной формы) изложены в следующих работах [46, 47, 48, 245].

Для исследования систем алгебраических уравнений, кроме базисов

Грёбнера [12, 24, 43, 46, 47, 48, 49, 51, 62, 63, 66, 154, 155, 168, 171, 245, 258, 260, 261], можно применять результанты [27, 162] (в случае нульмерных идеалов) введенные Сильвестром (Sylvester) [209] или "треугольные системы" рассмотренные By (Wu) [222].

В настоящие время алгоритм построения базисов Грёбнера встроен в большинство современных системы компьютерной алгебры [1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 124, 125, 126, 170].

Большое количество работ посвящено применению базисов Грёбнера в различных математических приложениях [37, 119, 123, 138, 156, 219, 220].

Развитию алгоритма Бухбергера в полиномиальном и дифференциальном случае посвящены следующие работы [40, 51, 51, 64, 141, 149, 164, 169, 173, 207].

Определение базиса Грёбнера использует понятие допустимого упорядо.-чения [53, 128, 184, 216]. Временная сложность построения базиса Грёбнера сильно зависит от выбранного допустимого упорядочения. Существуют методы пересчета [74, 74, 215] из одного упорядочения в другое с помощью "маршрута Грёбнера" и алгоритмов линейной алгебры.

Эффективность реализации любого алгоритма существенно зависит от организации структур данных, которая должна учитывать частоту обращения к элементарным операциям составляющим алгоритм. Например, одной из наиболее частых операций при работе алгоритма Бухбергера является операция сравнения мономов [21]. Исследованию эффективности различных структур данных в алгоритме Бухбергера посвящены работы [18, 19, 36, 65, 67, 81, 120, 148, 166, 218, 223].

Другая возможность ускорения вычислений связана с параллелизацией алгоритмов. Работы [13, 20, 41, 70, 140, 215] посвящены развитию параллельных версий алгоритма Бухбергера.

Альтернативный подход методу базисов Грёбнера сформировался при исследовании дифференциальных уравнений. Часть свойств систем аналитических дифференциальных уравнений в частных производных (ДУЧП) может быть исследована без получения явного решения. Это проверка совместности и формулировка начальных условий, которые необходимы для доказательства существования и единственности решения. Классическая теорема Коши-Ковалевской [153] устанавливает существование и единственность решения для определенного класса квазилинейных ДУЧП. Для этого класса квазилинейных ДУЧП легко проверить совместность системы и сформулировать начальные условия. Основным препятствием в исследовании других классов систем ДУЧП порядка q является нахождение условия совместности системы, то есть получения соотношений для производных порядка < q, которые не являются чисто алгебраическими следствиями уравнений в системе.

Рассмотрим, в качестве примера такой системы [274], уравнение Навье-Стокса для несжимаемой жидкости (р = const) / их + vy + w2 = О F1 = ut + uux + vuv + wu~ = —Px + vAu F2 = vt + uvx + vvy 4- wv~ — —Py + vAv F3 = wt-\- uwx + vvjy + wwz — —Pz + vAw из которой можно получить дополнительное соотношение на давление Р

F4 = и2х + 2vxuy + 2wxuz + vl + 2wyv~ + w2z = -АР , как следствие исходных уравнений

Fl + F2 + Fz - F® - uF° - vF° - wF% + vAF° = F4 .

Понятие инволютивности было введено около ста лет тому назад Кар-таном (Cartan) [54] при исследовании уравнений типа Пфаффа в полных дифференциалах. Инволютивная система ДУЧП содержит в себе все условия интегрируемости и продолжения системы не дают новых условий совместности. Пополнение системы ее условиями интегрируемости называется замыканием. Подход Картана был обобщен Кахлером (Kahler) [147] к произвольным системам внешних дифференциальных уравнений. Для метода Картана имеются реализации на компьютере [129, 234].

Рикье (Riquier) [182], для исследования решений ДУЧП в виде формальных рядов, предложил полное упорядочение для частных производных. Используя упорядочение он выделил часть производных, называемых главными, относительно которых можно разрешить систему ДУЧП. Оставшиеся производные, называемые параметрическими, задают произвол в решении и влияют на постановку начальных условий. В результате Рикье была построена теория содержащая теорему Коши-Ковалевской как частный случай. Упорядочение Рикье было недавно обобщено в [184].

Жане (Janet) [145, 146] было сделано дальнейшие развитие подхода Рикье. Для главных производных он ввел разбиение независимых переменных на мультипликативные и немультипликативные. В результате все продолжения системы разбивались на мультипликативные и немультипликативные и если продолжения по немультипликативным давали ту же систему, что и продолжения по мультипликативным, то такая системы называлась пассивной. Как и для подхода Картана, подход Рикье-Жане имеет несколько компьютерных реализаций [189, 190, 213].

Разбиение переменных введенное Жане неинвариантно, поскольку зависит от порядка переменных и упорядочения производных. С другой стороны формальная теория ДУЧП, развитая в 60-ых и 70-ых годах прошлого века Спенсером (Spencer) и другими (см. [175, 193, 200, 268]) позволяет сформулировать свойство инволютивности инвариантным способом.

Томас в [210] ввел новое разбиение независимых переменных, которое не зависит от порядка переменных, и обобщил подход Рикье-Жане на случай нелинейных алгебраических уравнений относительно главной производной. Он показал как, за конечное число шагов, проверить совместность системы и если она совместна, то разбить ее на подсистемы, состоящие из уравнений и неравенств, разрешенных относительно главной производной. Это разбиение подобно алгоритму Розенфельда-Грёбнера [40, 183].

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

• Ковалевская (1875) — теорема Коши-Ковалевской (частный случай инволютивной системы) [153];

• Картан (1901) — понятие инволютивности (Пфаффовы системы) [54, 55, 56, 129, 147];

• Рикье (1910), Жане (1920), Томас (1937) - инволютивные ДУЧП [145, 146, 178, 179, 180, 182, 189, 190, 210, 213];

• Квиллен (Quillen) (1964), Спенсер (Spencer) (1965), Кураниси (Kuranishi) (1967), Гольдшмидт (Goldschmidt) (1969) — формальная теория инволютивных ДУЧП [175, 188, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 268].

В статье [228] для разбиения независимых переменных Помма-ре (Pommaret) было показано, что инволютивный (пассивный) базис полиномиального идеала является базисом Грёбнера. Реализация инволютивного алгоритма в системе компьютерной алгебры Reduce [10] показало его высокую эффективность. Однако инволютивный алгоритм для разбиения Поммаре не оканчивался для идеалов положительной размерности, в отличии от разбиений Жане и Томаса.

Разбиения независимых переменных на мультипликативные и немультипликативные Жане, Томаса и Поммаре представляют собой частный слу- - . чай инволютивного деления мономов, введенного в [98].

На современном этапе развития инволютивных методов были разработаны следующие концепции и методы:

• Жарков, Блинков (1993) — деление Поммаре [87, 161, 225, 226, 227, 228, 229, 230, 232, 233, 259];

• Гердт, Блинков (1995) — концепция инволютивного деления [82, 83, 93, 94, 95, 96, 235, 249];

• Apel (1995) — сравнение инволютивных базисов и базисов Грёбне-ра [14, 15];

• Гердт, Блинков (1997) — минимальный инволютивный базис [97, 99];

• Гердт (1998) — парность инволютивных делений [84, 86, 90, 201, 202, 203, 204, 248, 271, 272];

• Гердт, Янович, Блинков (2001) - дерево "Жане" [30, 100, 101, 102, 116, 117, 118, 236, 238, 238, 254];

• Блинков (2001) — метод сепарирующих мономов [29, 237? ];

• Гердт, Янович (2002) — параллелизация инволютивных методов [111, ИЗ];

• Семенов (2003) — связь между парностью и аксиомой фильтрации [201, 202, 203, 271, 272];

• Гердт, Блинков (2005) — степенное деление Жане [103, 104, 107, 250];

• Gareth (2006) — некоммутативный инволютивный базис [80].

• Семенов (2006) — неконструктивные деления, "антипод Жане" [204, 273].

Другие результаты относящиеся к развитию и применению инволютив-ных методов представлены в работах [16, 50, 52, 57, 58, 79, 88, 89, 91, 132, 133, 135, 136, 137, 165, 167, 205, 206, 247, 255, 263, 264, 267, 280].

После выхода публикаций [98, 99, 228, 259] инволютивный подход был обобщен на некоммутативный [69] и дифференциальный случаи [59, 82, 83, 85, 174, 190, 230].

Перечислим наиболее известные реализации инволютивных методов. Системы полиномиальных уравнений:

• Жарков, Блинков (1993) - Reduce, модуль INVBASE [134, 231];

• Hong, Neubacher (1995) - С++ [142];

• Блинков (2001) - Reduce и С++ [117, 254];

• Янович (2001) - С [111, 112, 113, 114, 115, 117, 251, 252, 253];

• Гердт, Berth (2002) - Mathematica [25, 92, 93];

• Hausdorf, Seiler (2002) - Mupad [130, 131];

• Блинков, Cid, Гердт, Plesken, Robertz (2003) — Maple, модуль Involutive [31];

• Янович (2003) - Singular [126];

• Блинков, Гердт (2005) - Python, модуль GINV [105, 107, 250]. Системы линейных дифференциальных уравнений в частных производных:

• Reid, Wittkopf, Boulton (1996) - Maple, модуль Rif [180];

• Блинков, Cid, Гердт, Plesken, Robertz (2003) — Maple, модуль Janet [32];

• Zhang, Li (2006) - Maple [224]. Линейные рекуррентные соотношения:

• Гердт, Robertz (2006) - Maple, модуль LDA [110].

В последний годы были защищены несколько кандидатских и докторских диссертаций существенно использующих идеи и методы работ В. П. Гердта и автора настоящей диссертации [94, 98, 99, 249]. Авторы и названия некоторых из этих диссертаций приведены ниже:

• Apel J.: Zu Berechenbarkeitsfragen der IdealTheorie, Universitat Leipzig, 1998 (Habilitation thesis);

• Seiler W. M.: Involution - The Formal Theory of Differential Equations and its Applications in Computer Algebra and Numerical,

Universitat Mannheim, 2002 (Habilitation thesis);

• Hemmecke R.: Involutive Bases for Polynomial Ideals, Universitat Linz, RISC, 2003 (PhD);

• Голубицкий О. Д.: Маршруты Грёбнера, мехмат МГУ, 2004 (к.ф.м.н.- 01.01.06);

• Янович Д. А.: Алгоритмы и программы вычисления инволютив-ных базисов и их применение для решения систем нелинейных алгебраических уравнений, ЛИТ ОИЯИ, 2004 (к.ф.м.н.- 05.13.18);

• Митюнин В. А. : Алгоритмы вычисления базисов Грёбнера и ин-волютивных базисов, мехмат МГУ, 2004 (к.ф.м.н.- 01.01.06);

• Семёнов А. С.: Классификационные свойства инволютивных делений, мехмат МГУ, 2006 (к.ф.м.н.- 01.01.06);

• Gareth А. Е.: Noncommutative Involutive Bases, University of Wales, Bangor, 2006 (PhD);

• Robertz D.: Formal Computational Methods for Control Theory,

RWTH, Aachen, 2006 (PhD).

Для исследования и решения систем алгебраических, дифференциальных и разностных уравнений полиномиального типа инволютивными методами была разработана система компьютерной алгебры GINV [33, 239] (сокращение от Grobner /Л/Volutive). В основе системы лежат авторские алгоритмы построения инволютивных базисов Жане [116, 117] и степенных базисов Жане [103, 104] для полиномиальных идеалов и модулей, а также приведенных базисов Грёбнера. GINV (http://invo.jinr.ru/ ginv/) состоит из библиотеки программ на языке С++, являющейся модулем языка Python, и распространяется на условиях GPL v2. Система GINV используется также в качестве внешней библиотеки для пакета Janet [31, 32, 110] инволютивных алгоритмов в коммутативной алгебре. Пакет Janet написан на языке универсальной системы компьютерной алгебры Maple.

В диссертационной работе предлагается новый подход для построения разностных схем [75, 76, 77, 78, 121, 139, 157, 158, 177, 208, 217, 246, 279]. В нем первоначально задаются базовые разностные соотношения аппроксимирующие исходную систему дифференциальных уравнений, а затем для этих соотношений строится базис Грёбнера разностного идеала [60, 150, 265]. Из этого базиса, иногда, можно извлечь разностную схему, которую невозможно построить традиционными методами генерации разностных схем. Зачастую такие разностные схемы обладают уникальными свойствами хорошо передающими физику процессов описаваемых исходными дифференциальными уравнениями.

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

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

Данная техника позволяет развить новые подходы, например, к применению интегро-интерполяционного метода [240, 266]. В работах [34, 108, 241, 242] продемонстрирована возможность генерации разностных схем для гиперболических уравнений со схемной вязкостью, многослойных разностных схем и схем с переключателями. Преимуществом данного подхода является возможность строить разностные схемы без переключателей и схемной вязкости для уравнений смешанного типа.

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

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

Перечислим типичные области применения базисов Грёбнера [49, 245]:

• алгебраическая геометрия, коммутативная алгебра, теория полиномиальных идеалов,

• теория инвариантов,

• автоматическое доказательство геометрических теорем,

• теория кодирования,

• целочисленное программирование,

• дифференциальные уравнения в частных производных,

• гипергеометрические функции,

• символьное суммирование,

• статистика,

• некоммутативная алгебра,

• численные (например вейвлет-) преобразования, и т.д.

• теория управления.

Ниже приведен список задач, решаемых с помощью базисов Грёбнера:

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

• принадлежность к идеалу и к радикалу идеала,

• эффективные вычисления по модулю идеала,

• построение "сизигий",

• вычисление функции и полинома Гильберта,

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

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

Цель работы. Разработать инволютивные алгоритмы для эффективного построения базисов Грёбнера. Создать на базе этих алгоритмов комплекс компьютерных программ. Применить эти программы к исследованию математических моделей.

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

Методика исследований основана на универсальном алгоритмическом подходе — технике базисов Грёбнера и восходит к инволютивным алгоритмам, разработанным Рикье и Жане. В работе также используются известные методы генерации разностных схем и их обобщения с помощью техники базисов Грёбнера.

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

Связь работы с научными проектами, темами. Данная работа была выполнена при поддержке следующих грантов. Гранты РФФИ:

98-01-00101-а инволютивный анализ динамических систем со связями (1998-2000);

99-01-00192-а развитие кватернионных моделей и методов механики космического полета (1999-2000);

01-01-00708-а компьютерные методы инволютивного анализа дифференциальных уравнений и их применение к калибровочным теориям поля (2001-2003);

07-01 -00660-а компьютерный анализ совместности систем уравнений с приложением к квантовым вычислениям, калибровочным моделям теории поля и численному решению уравнений в частных производных (2007-2009).

Гранты Президента Российской Федерации:

НШ-2339.2003.2 развитие и применение новых аналитических и численных методов в теоретической и математической физике (2003-2005 рук. Д. В. Ширков);

НШ-5362.2006.2 развитие и применение новых аналитических и численных методов в теоретической и математической физике (2006-2008 рук. Д. В. Ширков);

Гранты ИНТАС:

93-0030 Computer algebra, symbolic and combinatorial tools in differential algebra and differential equations (1994-1995);

99-1222 Involutive Systems of Differential and Algebraic Equations (2000-2002).

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

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

2. Для реализации было введено новое понятие — инволютивное деление мономов.

3. Для инволютивных базисов разработан алгоритм построения минимальных инволютивных базисов, дающий каноническое представление.

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

5. Разработаны наиболее оптимальные структуры данных для поиска инволютивного делителя, названные "деревом Жане".

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

7. Для уравнения околозвуковых течений Кармана-Фальковича получена принципиально новая схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и переключателей.

8. Для логистического отображения найдено значения р, при котором происходит образование 9-и периодических циклов.

Практическая значимость.

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

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

3. Модуль INVBASE включен в качестве стандартного в систему компьютерной алгебры Reduce.

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

Личный вклад соискателя. Вклад автора в реализацию специализированной системы компьютерной алгебры GINV, модулей Janet и INVBASE является основным. Все результаты, изложенные в единоличных публикациях, получены автором самостоятельно. Из совместных публикаций в диссертацию включены лишь те результаты, которые получены лично автором.

Апробация работы. Основные результаты, полученные в диссертации, докладывались на следующих семинарах и конференциях:

• на Международной конференции "Симпозиум по символьным вычислениям IMACS" (Lille, Франция, 1993 г.);

• на семинаре по компьютерной алгебре в лаборатории информационных технологий ОИЯИ (Дубна, 1994, 1998, 2001, 2002, 2003, 2004, 2005, 2006, 2007 гг.);

• на Международной конференции "Новые компьютерные технологии в системах управления" (Переславль-Залесский, 1994 г.);

• на Международной конференции "Интервальные и компьютерно-алгебраические методы в научных вычислениях Interval'94" (Санкт-Петербург, 1994 г.);

• Современные тенденции в вычислительной физике (Дубна, 1998, 2000 гг.);

• на Международных конференциях "Rhein Workshop on Computer Algebra RWCA" (Karlsruhe, Германия, 1994 г.; Sankt-Augustin, Германия, 1998 г.; Mannheim, Германия, 2002 г.; Basel, Германия, 2006 г.);

• на Международной конференции "Приложения компьютерной алгебры IM ACS/AC А" (Санкт-Петербург, Россия, 2000 г.);

• в Высшей технической школе Рейна-Вестфалии RWTH (Аахен, Германия, 2001, 2003, 2006 гг.);

• на Международной конференции "Компьютерная алгебра и ее приложения в физике СААР'2001" (Дубна, 2001 г.);

• на пятом Международном конгрессе по математическому моделированию (Дубна, 2002 г.);

• на Международных конференциях "Компьютерная алгебра в научных вычислениях CASC" (Konstanz, Германия, 2001 г.; Passau, Германия, 2003 г.; Kalamata, Греция, 2005 г.);

• на всероссийском семинаре "СЕТОЧНЫЕ МЕТОДЫ ДЛЯ КРАЕВЫХ ЗАДАЧ И ПРИЛОЖЕНИЯ" (Казань 2004 г.);

• на семинаре по компьютерной алгебре на факультете ВМиК МГУ им. М.В.Ломоносова (Москва, 2005 г.);

• на Международной конференции "Symmetry in Nonlinear Mathematical Physics" (Киев, 2005 г.);

• на Международной конференции "Computer Algebra and Differential Equations" (Turku, Финляндия, 2007 г.);

• на семинаре по алгебре на механико-математическом факультете МГУ им. М.В.Ломоносова (Москва, 2007 г.);

• на Международной конференции "Полиномиальная компьютерная алгебра" (Санкт-Петербург, 2008 г.).

Публикации. По теме диссертации опубликовано 32 работы, в том чис

• 13 в российских и зарубежных журналах, рекомендованных ВАК для представления результатов докторских диссертаций,

• 2 в российских рецензируемых журналах,

• 4 в международных рецензируемых журналах,

• 10 в трудах международных конференций,

• 3 в тематических сборниках.

Структура а объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и одного приложения. Работа изложена на 251 страницах машинописного текста, из них основного текста 176 страниц. Работа содержит 23 рисунка, 10 таблиц, 20 описаний алгоритмов и одного приложения. Список литературы включает 281 наименований.

Основные результаты, выносимые на защиту.

1. Создана теория инволютивных, базисов. Теория основана на понятии инволютивной делимости мономов, для которого сформулированы аксиомы и дополнительные свойства (нётеровость, непрерывность и конструктивность), обеспечивающие алгоритмичность построения инволютивных базисов. Доказано, что инволютивные базисы являются базисами Грёбнера специального вида.

2. Разработан новый алгоритм вычисления базисов Грёбнера, альтернативный классическому алгоритма, Бухбергера, названный, инволю-тивным и значительно превосходящий по эффективности алгоритм Бухбергера. Инволютивный алгоритм основан на приведении систем уравнений к инволютивному виду, который определяется заданием инволютивного деления и линейного упорядочения мономов. Для повышения эффективности вычислений установлены критерии распознавания ряда бесполезных нулевых редукций.

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

4. Создана специализированная система компьютерной алгебры GINV с открытым-кодом, написанная на языке G4-+ и организованная в виде модуля языка Python. Ядро системы составляют инволютивные алгоритмы. Система доступна для широкого использования и успешно применяется в ряде организаций для решения научных и прикладных задач. По скорости вычисления базисов Грёбнера система; G/А^У является, самой быстрой в1 мире среди систем с открытым кодом.

5. Предложен: полностью алгоритмический метод генерации.разностных схем, использующий технику базисов Грёбнера. Данный метод позволяет обобщить ряд известных методов, построения разностных схем, включающих некоторые методы построения; многошаговых схем и схем с переключателями.

6. Путем; вычисления разностного идеала,, для нелинейного, уравнения. Кармана-Фальковича, описывающего околозвуковые течения в газог вой динамике,. найдена принципиально новая разностная* схема с: единым шаблоном В; эллиптической и гиперболической; области без схемной вязкости и переключателей. В; частности, для; одномерного течения газа в канале' с прямым скачком уплотнения зона ударного перехода, при использовании данной схемы, имеет протяженность порядка шага сетки.

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

Я очень благодарен двум своим соавторам,.не дожившим до момента на, вместе с кописания данной диссертации:

Алексею Юрьевичу Жаркову торым были получены мои первые результаты по инволютивному подходу, вошедшие, в Главу 1) и Владимиру Викторовичу Мозжилкину с которым. был получен ряд результатов, вошедших в-Главу 4.

Я. благодарен также другим своим соавторам: Денису Александровичу Яновичу,, в сотрудничестве с которым был получен, некоторые из-результатов, вошедших в Главу 2, и Карлосу Сиду, Вильгельму Плескену и Даниэлю. Робертцу, совместная работа с которыми вошла в часть результатов. Главы, 3. .

Существенную, помощь в работе мне постоянно оказывал Владимир. Васильевич Корняк, за что я ему очень-признателен.

Мне приятно также поблагодарить, Евгения Петровича Жидкова , Сергея Ильича Виницкого, Анатолия Михайловича. Рапортиренко, Виталия Александровича Ростовцева и Василия Михайловича .Северьянова. за полезные обсуждения, советы, замечания и критику.

Я весьма признателен Дмитрию Васильевичу Ширкову за поддержку моей научной работы, а также нынешнюю и прошлую дирекцию JIBTA/

ЛИТ ОИЯИ в лице Михаила; Григорьевича Мещерякова , Рудольфа Гейн-цевича; Позе и Игоря Викторовича Пузынина за предоставление мне возможности регулярных поездок в Дубну и создание стимулирующей рабочей атмосферы в. Лаборатории, содействующей получению результатов, представленных в диссертации.

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

Моя особая благодарность Щеглеватых Ивану Михайловичу дедушке, воспитание которого заложило' основу всех моих достижении, включая'работу над материалом диссертации.

Заключение

1. The database of polynomial systems, http://www.math.uic.edu/ ~ j an/demo.html.

2. REDUCE, http://www.reduce-algebra.com.

3. SINGULAR, http: //www. singular .uni-kl. de/.

4. Adams, W. W. An Introduction to Grobner Bases / W. W. Adams, P. Loustaunau. — American Mathematical Society, 1994,— Vol. 3 of Graduate Studies in Mathematics.

5. Amrhein, B. A Case Study of Multi-threaded Grobner Basis Computation / B. Amrhein, O. Gloor, W. Kuchlin // Proceedings of ISSAC / Ed. by Y. Lakshman.- ACM Press, New York, 1996. — Pp. 95-102.

6. Apel, J. A Grobner approach to involutive bases / J. Apel // Journal of Symbolic Computation. — 1995. — Vol. 19, no. 5. — Pp. 441-458.

7. Apel, J. The theory of involutive divisions and an application to Hilbert function computations / J. Apel // Journal of Symbolic Computation. — 1998. Vol. 25, no. 6. - Pp. 683-704.

8. Apel, J. Passive Complete Orthonomic Systems and Involutive Bases / J. Apel; Ed. by F. Winkler, U. Langer. — Springer Berlin, Heidelberg, 2003. — Vol. 2630 of Lecture Notes in Computer Science. — Pp. 88-107.

9. Apel, J. Detecting unnecessary reductions in an involutive basis computation / J. Apel, R. Hemmecke // Journal of Symbolic Computation. 2005. - Vol. 40, no. 4-5. - Pp. 1131-1149.

10. Apel, J. FELIX: an assistant for algebraists / J. Apel, U. Klaus // International Symposium on Symbolic and Algebraic Computation. — Bonn, West Germany, 1991,- Pp. 382-389.

11. Arnold, E. A. Modular algorithms for computing Grobner bases / E. A. Arnold // Journal of Symbolic Computation. — 2003. — Vol. 35, no. 4,- Pp. 403-419.

12. Attardi, G. A strategy-accurate parallel Buchberger algorithm / G. Attardi, C. Traverso // Proceedings International Symposium Parallel Symbolic Computation. — World Scientific, Singapore, 1994,— Lecture Notes Series in Computing. — Pp. 49-54.

13. Bachmann, O. Monomial representations for Grobner bases computations / O. Bachmann, H. Schonemann // Proceedings of ISSAC. ACM Press, 1998. - Pp. 309-321.

14. Bakhturin, Yu. A. Infinite-dimensional Lie superalgebras / Yu. A. Bakhturin, A. A. Mikhalev, V. M. Petrogradsky, M. V. Zaicev. — Walter de Gruyter & Co., Berlin, 1992,— Vol. 7 of De Gruyter Expositions in Mathematics.

15. Bayer, D. Computation of Hilbert functions / D. Bayer, M. Stillman // Journal of Symbolic Computation.— 1992.— Vol. 14, no. 1.— ' Pp. 31-50.

16. Becker, T. Grobner Bases. A Computational Approach to Commutative Algebra / T. Becker, V. Weispfenning, H. Kredel. — Springer-Verlag, New York, 1993. — Vol. 141 of Graduate Texts in Mathematics.

17. Berth, M. Computation of involutive bases with mathematica / M. Berth, V. P. Gerdt // Third International Workshop on "Mathematica" System in Teaching and Research. — University of Podlasie, Seldce, Poland, 2001,- Pp. 29-34.

18. Bigatti, A. M. Computing toric ideals / A. M. Bigatti, R. La Scala, L. Robbiano 11 Journal of Symbolic Computation. — 1999. — Vol. 27. — Pp. 351-365.

19. Bikker, P. On the Bezout construction of the resultant / P. Bikker, A. Yu. Uteshev // Journal of Symbolic Computation.— 1999. — Vol. 28, no. 1-2.- Pp. 45-88.

20. Bini, D. Polynomial Test Suite / D. Bini, B. Mourrain. 1996. http: ' //www-sop.inria.fr/saga/POL.

21. Blinkov, Yu. A. Method of separative monomials for involutive divisions / Yu. A. Blinkov 11 Programming and Computer Software. — 2001.- Vol. 27, no. 3.- Pp. 139-141.

22. Blinkov, Yu. A. Computation of janet bases for toric ideals / Yu. A. Blinkov // Programming and Computer Software. — 2002. — Vol. 28, no. 5. — Pp. 290-292.

23. Blinkov, Yu. A. Specialized computer algebra system GINV / Yu. A. Blinkov, V. P. Gerdt // Programming and Computer Software. — 2008. Vol. 34, no. 2. - Pp. 112-123.

24. Blinkov, Yu. A. Generation of difference schemes for the burgers equation by constructing Grobner bases / Yu. A. Blinkov, V. V. Mozzhilkin // Programming and Computer Software.— 2006.— Vol. 32, no. 2,- Pp. 114-117.

25. Boehm, H. Dynamic memory allocation and garbage collection / H. Boehm // Computers in Physics.— 1995.— Vol. 9, no. 3.— Pp. 297-303.

26. Boge, W. Grobner bases using SAC2 / W. Boge, R. Gebauer, H. Kredel // Proceedings EUROCAL 85.- 1985.- Pp. 272-274.

27. Boge, W. Some examples for solving systems of algebraic equations by calculating Grobner bases / W. Boge, R. Gebauer, H. Kredel // Journal of Symbolic Computation. — 1986. — Vol. 2, no. 1. — Pp. 83-98.

28. Bokut, L. Grobner-Shirshov bases for some braid groups / L. Bokut, A. Vesnin // Journal of Symbolic Computation. — 2006.— Vol. 41.— Pp. 357-371.

29. Boulanger, J.-L. Object oriented method for Axiom / J.-L. Boulanger // ACM SIGPLAN Notices. 1995. - Vol. 30, no. 2. - Pp. 33-41.

30. Boulier, F. Representation for the radical of a finitely generated differential ideal / F. Boulier, D. Lazard, F. Ollivier, Petitot M. // Proceedings of ISSAC / Ed. by Levelt A. H. M. ACM Press, 1995. -Pp. 158-166.

31. Bradford, R. A parallelization of the Buchberger algorithm / R. Bradford // Proceedings of the international symposium on Symbolic and algebraic computation. — Tokyo, Japan, 1990.— Pp. 296-296.

32. Brown, W. C. On Euclid's algorithm and the computation of polynomial greatest common divisors / W. C. Brown // Journal of the ACM. — 1971. Vol. 18, no. 4. - Pp. 476-504.

33. Buchberger, B. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal: Ph.D. thesis / Universitat Innsbruck. — 1965.

34. Buchberger, В. An algorithmic criterion for the solvability of algebraic systems of equations / B. Buchberger // Aequationes Math. — 1970. — Vol. 4. Pp. 374-383.

35. Buchberger, B. A theoretical basis for the reduction of polynomials to canonical forms / B. Buchberger // ACM SIGSAM Bull. 1976. — Vol. 39.-Pp. 19-29.

36. Buchberger, B. A criterion for detecting unnecessary reductions in the construction of grobner bases / B. Buchberger // International Symposium on Symbolic and Algebraic Manipulation / Ed. by E. W. Ng. Springer-Verlag, London, 1979,— Pp. 3-21.

37. Buchberger, B. Grobner bases: an Buchberger algorithmic method in polynomial ideal theory / B. Buchberger // Recent Trends in Multidimensional System Theory / Ed. by N. K. Bose. — Vol. 6. — Reidel, Dordrecht, 1985,- Pp. 184-232.

38. Buchberger, B. Grobner Bases and Applications / B. Buchberger, F. Winkler. — Cambridge University Press, 1998.

39. Calmet, J. A constructive introduction to involution / J. Calmet, M. Hausdorf, W. M. Seiler // Proceedings of the International

40. Symposium on Applications of Computer Algebra / Ed. by P. Akerkar. Allied Publishers, New Delhi, 2001,— Pp. 33-50.

41. Carra-Ferro, G. Grobner Bases and Differential Algebra / G. Carra-Ferro.— 1987.— Vol. 356 of Lecture Notes in Computer Science.- Pp. 129-140.

42. Carra-Ferro, G. On term-orderings and rankings / G. Carra-Ferro, W. Y. Sit // Computational Algebra / Ed. by G. Fischer, P. Loustaunau, J. Shapiro, E. Green, D. Farkas. — Marcel Dekker, New York, 1994. — Pp. 31-77.

43. Cartan, E. Sur certaines expressions differentielles et le ргоЫёте de Pfaff / E. Cartan // Annates scientifiques de I'Ecole Normale Superieure Ser. 3.— 1899.— no. 16.— Pp. 239-332. http://archive.numdam.org/article/ASENSl 8 9 9316 2390 .djvu.

44. Cartan, E. L'integration des systemes d'equations aux differentielles totales / E. Cartan // Annates scientifiques de I'Ecole Normale Superieure Ser. 3.— 1901.- no. 18.- Pp. 241-311. http://archive.numdam.org/article/ASENSl9 01318 2410 .djvu.

45. Cartan, E. Les Systemes 01ГГёгеп1:1е1з Exterieur et leurs Applications Geometrique / E. Cartan. — Hermann, Paris, 1946.

46. Chen, Y. F. Vector representation of involutive divisions / Y. F. Chen, X. S. Gao // Mathematics-Mechanization Research Preprints. — 1999,- no. 18.- Pp. 9-22.

47. Chen, Y. F. Involutive directions and new involutive divisions / Y. F. Chen, X. S. Gao // Computers and Mathematics with Applications. — 2001. Vol. 41, no. 7-8. - Pp. 945-956.

48. Chen, Y. F. Involutive bases of algebraic partial differential equation systems / Y. F. Chen, X. S. Gao // Science in China (A). — 2003. — Vol. 33, no. 2,- Pp. 97-113.

49. Cohn, R.M. Difference algebra / R.M. Cohn. — Interscience Publishers, 1965. — Vol. 17 of Tracts in Mathematics. — P. 367.

50. Conti, P. Buchberger algorithm and integer programming / P. Conti,

51. C. Traverso // Proceedings of AAECC-9. — Springer-Verlag, 1991. — Lecture Notes in Computer Science no. 539.— Pp. 130-139.

52. Cox, D. Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra /

53. D. Cox, J. Little, D. O'Shea. Springer-Verlag, New York, 1998. — 2nd Edition.

54. Cox, D. Using Algebraic Geometry / D. Cox, J. Little, D. O'Shea. — Springer-Verlag, New York, 1998.— Vol. 185 of Graduate Texts in Mathematics.

55. Czapor, S. R. A heuristic selection strategy for lexicographic Grobner bases? / S. R. Czapor // International Symposium on Symbolic and Algebraic Computation. — Bonn, West Germany, 1991. — Pp. 39-48.

56. Czapor, S. R. On implementing Buchberger's algorithm for Grobner bases / S. R. Czapor, К. O. Geddes // Proceedings of the fifth ACM symposium on Symbolic and algebraic computation. — Waterloo, Ontario, Canada, 1986,- Pp. 233-238.

57. Davenport, J. H. Computer Algebra: Systems and Algorithms for Algebraic Computation / J. H. Davenport, Y. Siret, E. Tournier. — Academic Press, 1988.- P. 267.

58. Davenport, J. H. Scratchpad's view of algebra I: Basic commutative algebra: Tech. Rep. TR3/92 (ATR/1) (NP2490) / J. H. Davenport, В. M. Trager. inst-NAG:adr: inst-NAG, 1992.

59. Eisenbud, D. Commutative Algebra with a View Toward Algebraic Geometry / D. Eisenbud.— Springer-Verlag, New York, 1995.— Vol. 150 of Mathematics and its Applications.

60. Evans, G. A. Noncommutative involutive bases / G. A. Evans // International Conference on Applications of Computer Algebra. — Beaumont, Texas, U.S.A., 2004.

61. Faugere, J. C. Parallelization of Grobner basis / J. C. Faugere // Proceedings International Symposium Parallel Symbolic Computation / Ed. by H. Hong. — Lecture Notes Series in Computing. — World Scientific, Singapore, 1994.- Pp. 124-132.

62. Faugere, J. C. A fast, easy to use algorithm for dynamic memorymanagement: Tech. rep. / J. C. Faugere: LIP6, universite Paris VI, 1998.

63. Faugere, J. C. A new efficient algorithm for computing Grobner bases (f4) / J. C. Faugere 11 Journal of Pure and Applied Algebra. — 1999. — Vol. 139, no. 1-3.- Pp. 61-88.

64. Faugere, J. C. A new efficient algorithm for computing Grobner bases without reduction to zero (F5) / J. C. Faugere // Proceedings of ISSAC / Ed. by New York ACM Press.- ACM Press, New York, 2002. Pp. 75-83.

65. Faugere, J. C. Efficient computation of zero-dimensional Grobner bases by change of ordering / J. C. Faugere, P. Gianni, D. Lazard, T. Mora // Journal of Symbolic Computation. — 1993. — Vol. 16. — Pp. 329-344.

66. Fournie, M. Symbolic derivation of different class of high-order schemes for partial differential equations / M. Fournie // Computer Algebra in Scientific Computing. — Springer-Verlag, 1999.— Lecture Notes in Computer Science. — Pp. 93-100.

67. Ganzha, V. G. Computer-aided analysis of difference schemes for partial differential equations / V. G. Ganzha, E. V. Vorozhtsov. — New York, ■ ■ Wiley-Interscience, 1996.

68. Ganzha, V. G. Numerical solutions for partial differential equations: problem solving using Mathematica / V. G. Ganzha, E. V. Vorozhtsov. — Boca Raton, CRC Press, 1996.

69. Ganzha, V. G. Symbolic-numeric stability investigations of Jameson's schemes for thin-layer Navier-Stokes equations / V. G. Ganzha, E. V.

70. Vorozhtsov, J. Boers, J. A. van Hulzen // Symbolic and Algebraic Computation / SIGSAM. ISSAC. - ACM, 1994. - Pp. 234-241.

71. Garcia-Sanchez, P. A. Grobner bases and involutive bases for zero-dimensional ideals / P. A. Garcia-Sanchez // SIGSAM Bulletin. — 1995. Vol. 29, no. 2. - Pp. 12-15.

72. Gareth, A. E. Noncommutative Involutive Bases: Ph.D. thesis / University of Wales, Bangor. — 2006.

73. Gebauer, R. On an installation of Buchberger's algorithm / R. Gebauer, H. M. Moller // Journal of Symbolic Computation. — 1988. — Vol. 6, no. 2-3. Pp. 275-286.

74. Gerdt, V. P. Grobner bases and involutive methods for algebraic and • differential equations / V. P. Gerdt // Mathematical and computer modelling. 1997.- Vol. 8/9, no. 25.- Pp. 75-90.

75. Gerdt, V. P. Involutive Division Technique: Some Generalizations and Optimizations / V. P. Gerdt.- 1998,- (Preprint E5-98-151, Joint Institute for Nuclear Research).

76. Gerdt, V. P. Involutive division technique: Some generalizations and optimizations / V. P. Gerdt // Journal of Mathematical Sciences. — 2000. no. 258. - Pp. 185-206.

77. Gerdt, V. P. On an algorithmic optimization in computation of involutive bases / V. P. Gerdt // Programming and Computer Software. 2002. - Vol. 28, no. 2. - Pp. 62-65.

78. Gerdt, V. P. Involutive algorithms for computing Grobner bases / V. P. Gerdt // Proceedings of the NATO Advanced Research Workshop "Computational commutative and non-commutative algebraic geometry". — IOS Press, 2004. P. 27.

79. Gerdt, V. P. Involutive division techniques: Some generalizations and optimizations / V. P. Gerdt // Journal of Mathematical Sciences. — 2004.-Vol. 108, no. 6.-Pp. 1034-1051.

80. Gerdt, V. P. Completion of monomial sets to involution with mathematica: Tech. Rep. Preprint / V. P. Gerdt, M. Berth,

81. G. Czichowski: Greifswald, 1998.- submitted to CASC '98, St. Petersburg.

82. Gerdt, V. P. Involutive Polynomial Bases / V. P. Gerdt, Yu. A. Blinkov. — Publication IT-95-271, Laboratoire d'Informatique Fondamentale de Lille, 1995.

83. Gerdt, V. P. Involutive Bases of Polynomial Ideals / V. P. Gerdt, Yu. A. Blinkov. — Preprint-Nr.1/1996, Naturwissenschaftlich-Theoretisches Zentrum, University of Leipzig, 1996.

84. Gerdt, V. P. Involutive Bases of Polynomial Ideals / V. P. Gerdt, Yu. A. Blinkov. Preprint Preprint E5-97-3, JINR, 1997. - P. 26.

85. Gerdt, V. P. Minimal Involutive Bases / V. P. Gerdt, Yu. A. Blinkov. -Preprint E5-97-4, JINR, Dubna, 1997.- P. 20.

86. Gerdt, V. P. Involutive bases of polynomial ideals / V. P. Gerdt, Yu. A. Blinkov // Mathematics and Computers in Simulation.— 1998.— Vol. 45.- Pp. 519-542.

87. Gerdt, V. P. Minimal involutive bases / V. P. Gerdt, Yu. A. Blinkov // Mathematics and Computers in Simulation.— 1998.— Vol. 45,— Pp. 543-560.

88. Gerdt, 1/. P. Janet Bases of Toric Ideals / V. P. Gerdt, Yu. A. Blinkov. -Preprint E5-11-2001-279, JINR, Dubna, 2001.- P. 19.

89. Gerdt., I/. P. Janet bases of toric ideals / V. P. Gerdt, Yu. A. Blinkov // Proceedings of the Rhein Workshop on Computer Algebra. — Mannheim, Germany: 2002,- Pp. 125-135.

90. Gerdt, V. P. Janet trees in computing of toric ideals / V. P. Gerdt, Yu. A. Blinkov // Computer algebra and its applications to physics. — Dubna, Russia: 2002.- Pp. 71-82.

91. Gerdt, I/. P. Janet-like Grobner bases / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra in Scientific Computing. — Springer Berlin / Heidelberg, 2005. — Vol. 3718 of Lecture Notes in Computer Science. — Pp. 184-195.

92. Gerdt, V. P. Janet-like monomial division / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra in Scientific Computing. — Springer Berlin / Heidelberg, 2005,— Vol. 3718 of Lecture Notes in Computer Science. Pp. 174-183.

93. Gerdt, V. P. On computing Janet bases for degree compatible orderings / V. P. Gerdt, Yu. A. Blinkov // Proceedings of the Rhein Workshop on Computer Algebra / Ed. by J. Draisma, H. Kraft. — University of Basel, 2006.- Pp. 107-117.- math.AC/0603161.

94. Gerdt, V. P. On computer algebra-aided stability analysis of difference schemes generated by means of Grobner bases / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra and Differential Equations / Ed. by

95. A. Myllari, V. Edneral, N. Ourusoff. — Acta Academiae Aboensis, Ser.

96. B, 2007. Vol. 67. - Pp. 168-177.

97. Gerdt, V. P. On selection of nonmultiplicative prolongations in computation of Janet bases / V. P. Gerdt, Yu. A. Blinkov // Programming and Computer- Software. — 2007. — Vol. 33, no. 3. — Pp. 147-153.

98. Gerdt, V. P. A Maple package for computing Grobner bases for linear recurrence relations / V. P. Gerdt, D. Robertz // Nuclear Instruments and Methods in Physics Research. — 2006. — Vol. A559. Pp. 215-219. - arXiv:cs.SC/0509070.

99. Gerdt, V. P. Parallelization of an algorithm for computation of involutive janet bases / V. P. Gerdt, D. A. Yanovich // Programming and ■ Computer Software. 2002. - Vol. 28, no. 2. - Pp. 66-69.

100. Gerdt, V. P. Implementation of the fglm algorithm and finding roots of polynomial involutive systems / V. P. Gerdt, D. A. Yanovich // Programming and Computer Software. — 2003. — Vol. 29, no. 2. — Pp. 72-74.

101. Gerdt, V. P. Experimental analysis of involutive criteria / V. P. Gerdt, D. A. Yanovich // Algorithmic Algebra and Logic / Ed. by A. Dolzmann, A. Seidl, T. Sturm. — BOD Norderstedt, Germany,2005.- Pp. 105-109.

102. Gerdt, V. P. Parallel computation of janet and grobner bases over rational numbers / V. P. Gerdt, D. A. Yanovich // Programming and Computer Software. 2005. - Vol. 31, no. 2. - Pp. 73-80.

103. Gerdt, V. P. Fast search for the Janet divisor / V. P. Gerdt, D. A. Yanovich, Yu. A. Blinkov // Programming and Computer Software. — 2001.- Vol. 27, no. 1.- Pp. 22-24.

104. Gianni, P. Algebraic solution of systems of polynomial equations using Grobner bases / P. Gianni, T. Mora. 1989,- Pp. 247-257.

105. Giovini, A. 'one sugar cube, please' or selection strategies in the Buchberger algorithm / A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. Traverso. 1991.— Pp. 49-54. http: //www.acm.org:80/pubs/citations/proceedings/issac/ 120694/p4 9-giovini/.

106. Godunov, S. K. Difference schemes. An introduction to the underlying theory / S. K. Godunov, V. S. Ryaben'kii. — New York, Elsevier, 1987.

107. Gordan, P. Les invariants des formes binaires / P. Gordan // Journal de Mathematiques Puves et Appliques. — 1900. — Vol. 6. — Pp. 141-156.

108. Grabe, H.-G. Algorithms in local algebra / H.-G. Grabe // Journal of Symbolic Computation. — 1995. — Vol. 19, no. 6. — Pp. 545-558.

109. Greuel, G.-M. A Singular Introduction to Commutative Algebra / G.-M. Greuel, G. Pfister. — Springer Berlin, Heidelberg, 2002.

110. Greuel, G.-M. Singular: A Computer Algebra System for Polynomial Computation / G.-M. Greuel, G. Pfister, H. Schonemann. — Department of Mathematics, University of Keiserslautern, 2001. http: //www.singular.uni-kl.de/Manual/2-0-0/.

111. Greuel, G.-M. Singular 3.0: A Computer Algebra System for Polynomial Computations / G.-M. Greuel, G. Pfister, H. Schonemann. — University of Kaiserslautern: Centre for Computer Algebra, 2005. — http://www.singular.uni-kl.de.

112. Grobner, W. Uber die eliminationstheorie / W. Grobner // Monatsh. der Math. 1939. - Vol. 54. - Pp. 71-78.

113. H., Hong. Algorithmic Theory of Admissible Term Orders / Hong H., Weispfenning V. http://www4 . ncsu. edu: 8030/~hong/papers/ Hong99c.dvi.

114. Hartley, D. A constructive implementation of the Cartan-Kahler theory of exterior differential systems / D. Hartley, R. W. Tucker // Journal of Symbolic Computation. — 1991.— Vol. 12, no. 6,— Pp. 655-668.

115. Hausdorf, M. Involutive Bases in MuPAD II: Polynomial Algebras of Solvable Type / M. Hausdorf, W. M. Seiler. — (to apper).

116. Hausdorf, M. Involutive bases in MuPAD I: Involutive divisions / M. Hausdorf, W. M. Seiler // mathPAD.- 2002,- Vol. 11.-Pp. 51-56.

117. Hausdorf, M. An efficient algebraic algorithm for the geometric completion to involution / M. Hausdorf, W. M. Seiler // Journal Applicable Algebra in Engineering, Communication and Computing. — 2004. Vol. 13, no. 3. - Pp. 163-207.

118. Hausdorf, M. Involutive bases in the Weyl algebra / M. Hausdorf, W. M. Seiler, R. Steinwandt // Journal of Symbolic Computation. — 2002. Vol. 34, no. 3. - Pp. 181-198.

119. Hearn, A. C. REDUCE User's Manual, Version 3.7: Report / A. C. Hearn: Anthony C. Hearn, 1999. http://www.zib.de/ Optimization/Software/Reduce/moredocs/reduce.pdf.

120. Hemmecke, R. Dynamical Aspects of Involutive Bases Computations / R. Hemmecke. — RISC report 01-28, 2001.

121. Hemmecke, R. Dynamical Aspects of Involutive Bases Computations / R. Hemmecke; Ed. by F. Winkler, U. Langer. — Springer Berlin, Heidelberg, 2003. — Vol. 2630 of Lecture Notes in Computer Science. — Pp. 88-107.

122. Hildebrand, F.B. Finite-Difference Equations and Simulations / F.B. Hildebrand. — Prentice-Hall, 1968.- P. 338.

123. Hiroyuki, S. Parallel computation of Grobner bases on distributed memory machines / S. Hiroyuki, T. Satoshi, A. Akira // Journal of Symbolic Computation. 1994. - Vol. 18, no. 3. - Pp. 207-222.

124. Hong, H. Grobner basis under composition I / H. Hong 11 Journal of Symbolic Computation. — 1998. — Vol. 25, no. 5. — Pp. 643-664.

125. Hong, H. Implementation of an involutive method for computing • Grobner bases of zero-dimensional ideals: Tech. Rep. A-4040 / H. Hong, A. Neubacher. — Linz, Austria: Research Institute for Symbolic Computation, Johannes Kepler University, 1995.

126. Jameson, A. Transonic flow calculations / A. Jameson // Numerical Methods in Fluid Dynamics / Ed. by H. J. Wirz, J. J. Smolderen. — Hemisphere, 1976.— Vol. 87 of von Karman Institute for Fluid Dynamics Lecture Series. — Pp. 1-87.

127. Janet, M. Systemes d'equations aux derivees partielles / M. Janet // Journals de mathematiques, 8e serie. — 1920. — Vol. 3. — Pp. 65-151.

128. Janet, M. Legons sur les systemes d'equations aux derivees partielles / . M. Janet. Cahiers Scientifiques, fascicule IV. — Gauthier-Villars, Paris, 1929.

129. Kahler, E. Einfiihrung in die Theorie der Systeme von Differentialgleichungen / E. Kahler; Ed. by B. G. Teubner. — Hamburger mathematische Einzelschriften 16. Leipzig, 1934. — Vol. IV. P. 80.

130. Kandri-Rody, A. Computing the Grobner-basis of an Ideal in Polynomial Rings over the Integers / A. Kandri-Rody, D. Kapur //

131. Proceedings 1984 MACSYMA User's Conference.- 1984. — Pp. 436-451.

132. Kandri-Rody, A. Non-commutative Grobner bases in algebras of solvable type / A. Kandri-Rody, V. Weispfenning // Journal of Symbolic Computation. — 1990. Vol. 9, no. 1. - Pp. 1-26.

133. Kondratieva, M. V. Differential and Difference Dimension Polynomials / M. V. Kondratieva, A. B. Levin, A. V. Mikhalev, E. V. Pankratiev. Kluwer, 1999.

134. Koppenhagen, U. An optimal algorithm for constructing the reduced Grobner basis of binomial ideals / U. Koppenhagen, E. W. Mayr. — 1996. Pp. 55-62.

135. Kotsireas, I. S. Exact computation of the bifurcation point b4 of the logistic map and the bailey-broadhurst conjectures / I. S. Kotsireas, K. Karamanos // Journal Bifurcation and Chaos. — 2004. — Vol. 14. — Pp. 2417-2423.

136. Kovalevskaya, S. V. Zur theorie der partiellen differential-gleichungen / S. V. Kovalevskaya // Journal fiir die Reine und Angewandte Mathematik. 1875. - Vol. 80. - Pp. 1-32.

137. Kreutzer, M. Computational Commutative Algebra 1 / M. Kreutzer, L. Robbiano. — Springer Berlin, Heidelberg, 2000.

138. Latyshev, V. N. A combinatorial complexity of Grobner bases / V. N. Latyshev // Journal of Mathematical Sciences. — 2000.— Vol. 102, no. 3,- Pp. 4134-4138.

139. Lazard, D. Solving zero-dimensional algebraic systems / D. Lazard // Journal of Symbolic Computation.— 1992,— Vol. 13, no. 2.— Pp. 117-132.

140. Liska, R. Algorithms for difference schemes construction on non-orthogonal logically rectangular meshes / R. Liska, M. Yu. Shashkov // Proceedings of ISSAC. — New York, ACM Press, Addison Wesley, 1991.- Pp. 419-426.

141. Liska, R. Support-operators method for pde discretization: symbolic algorithms and realization / R. Liska, M. Yu. Shashkov, A. V. Solovjov // Mathematics and Computers in Simulation. — 1994. — Vol. 35.-Pp. 173-183.

142. Lun, С. C. Non-steady motion of a slender body in a compressible fluid / С. C. Lun, E. Reissner, H. S. Tslen // Journal of Mathematic and Physics. 1948. - Vol. 27, no. 3.

143. Macaulay, F. S. Some properties of enumeration in the theory of modular systems / F. S. Macaulay // Proc. London Math. Soc. — 1927,- Vol. 26.- Pp. 531-555.

144. Mall, D. On the relation between Grobner and Pommaret bases / D. Mall // AAECC. 1998. - no. 9. - Pp. 117-123.

145. Mandache, A. M. The Grobner basis algorithm and subresultant theory / A. M. Mandache // Proceedings of the international symposium on Symbolic and algebraic computation.— 1994. — Pp. 123-128.

146. Manizini, M. Numerical methods for ID compressible flows, http: //www.crs4.it/HTML/intbook/metapage.html.

147. Mansfield, E. Application of the differential algebra package diffgrob2 to classical symmetries of differential equations / E. Mansfield, P. A. Clarkson // Journal of Symbolic Computation. — 1997. Vol. 5-6, no. 23. - Pp. 517-533.

148. Marotta, V. Involutive division and involutive autoreduction / V. Marotta, G. Carra-Ferro // Proceedings of the Rhein Workshop on Computer Algebra / Ed. by H. Kredel, W. M. Seiler. — University of Mannheim, 2002.- Pp. 115-124.

149. Melenk, H. On grobner bases computation on a supercomputer using REDUCE: Technical Report Preprint SC 88-2 / H. Melenk, H. M. Moller, W. Neun. — Berlin, Germany: Konrad-Zuse-Zentrum ftir Informationstechnik Berlin ZIB, 1988.

150. Mesyanzhin, A. V. On a method for finding the roots of an ideal / A. V. Mesyanzhin // Programming and Computer Software. — 2005. — Vol. 31, no. 2,- Pp. 97-102.

151. Mishra, B. Algorithmic Algebra / B. Mishra. — Springer-Verlag, New York, 1993.

152. Moller, H. M. Grobner bases computation using syzygies / H. M. Moller, T. Mora, C. Traverso. 1992,- Pp. 320-328.

153. Monagan, Michael B. Maple 10 Programming Guide / Michael B. Monagan, Keith O. Geddes, K. Michael Heal, George Labahn, Stefan M. Vorkoetter, James McCarron, Paul DeMarco. — Waterloo ON, Canada: Maplesoft, 2005.

154. Mora, T. An introduction to commutative and non-commutative

155. Mansfield, E. Application of the differential algebra package diffgrob2 to classical symmetries of differential equations / E. Mansfield, P. A. Clarkson // Journal of Symbolic Computation. — 1997. Vol. 5-6, no. 23. - Pp. 517-533.

156. Marotta, V. Involutive division and involutive autoreduction / V. Marotta, G. Carra-Ferro // Proceedings of the Rhein Workshop on Computer Algebra / Ed. by H. Kredel, W. M. Seiler. — University of Mannheim, 2002. Pp. 115-124.

157. Melenk, H. On grobner bases computation on a supercomputer using REDUCE: Technical Report Preprint SC 88-2 / H. Melenk, H. M. Moller, W. Neun. — Berlin, Germany: Konrad-Zuse-Zentrum fur Informationstechnik Berlin ZIB, 1988.

158. Mesyanzhin, A. V. On a method for finding the roots of an ideal / A. V. Mesyanzhin // Programming and Computer Software. — 2005.^ Vol. 31, no. 2,- Pp. 97-102.

159. Mishra, B. Algorithmic Algebra / B. Mishra. — Springer-Verlag, New York, 1993.

160. Moller, H. M. Grobner bases computation using syzygies / H. M. Moller, T. Mora, C. Traverso. 1992.- Pp. 320-328.

161. Monagan, Michael B. Maple 10 Programming Guide / Michael B. Monagan, Keith O. Geddes, K. Michael Heal, George Labahn, Stefan M. Vorkoetter, James McCarron, Paul DeMarco. — Waterloo ON, Canada: Maplesoft, 2005.

162. Mora, T. An introduction to commutative and non-commutative

163. Grobner bases / Т. Mora // Theoretical Computer Science. — 1994. — Vol. 134,- Pp. 131-173.

164. Morton, K. W. Numerical solution of partial differential equations / K. W. Morton, D. F. Mayers. —. Cambridge, Cambridge University Press.

165. Ollivier, F. Standard Bases of Differential Ideals / F. Ollivier. 1990. — Vol. 508 of Lecture Notes in Computer Science. — Pp. 304-321.

166. Plesken, W. Janet's approach to presentations and resolutions for polynomials and linear pdes / W. Plesken, D. Robertz // Archiv der Mathematik. 2005. - Vol. 84, no. 1. - Pp. 22-37.

167. Pommaret, J. F. Partial Differential Equations and Group Theory. New Perspectives for Applications / J. F. Pommaret. — Kluwer, Dordrecht, 1994.

168. Pottier, L. Grobner bases of toric ideals: Tech. Rep. 2224 / L. Pottier: Rapport de recherche, INRIA Sophia Antipolis, 1997.

169. Quarteroni, A. Numerical approximation of partial differential equations / A. Quarteroni, A. Valli. — Berlin, Springer-Verlag, 1997.

170. Reid, G. J. Algorithms for reducing a system of pdes to standard form, determining the dimension of its solution space and calculating its taylor series solution / G. J. Reid // Journal of Applied Mathematics. — 1991.- Vol. 21.- Pp. 293-318.

171. Reid, G. J. Finding abstract lie symmetry algebras of differential equations without integrating determaning equations / G. J. Reid // Journal of Applied Mathematics. — 1991. — no. 2. — Pp. 319-340.

172. Reid, G. J. Reduction of systems of nonlinear partial differential equations to simplified involutive forms / G. J. Reid, A. D. Wittkopf, A. Boulton // Journal of Applied Mathematics. — 1996. — Vol. 7. — Pp. 604-635.

173. Richtmyer, R. D. Difference methods for initial-value problems / R. D. Richtmyer, K. W. Morton. New York, John Wiley & Sons, 1976. — P. 238.— reprinted Krieger Publishing Company, New York, 1994.

174. Riquier., C. Les Systemes d'Equations aux Derivees Partielles / C. Riquier. — Gauthier-Villars, Paris, 1910.

175. Rosenfeld, A. Specializations in differential algebra / A. Rosenfeld // Transaction of the American Mathematical Society. — 1959. — Vol. 90. Pp. 394-407.

176. Rust, C. J. Rankings of partial derivatives / C. J. Rust, G. J. Reid // Proceedings of ISSAC / Ed. by W. Kuchlin. ACM Press, 1997. — Pp. 9-16.

177. Saha, S. The birth of period three / S. Saha, H. S. Steven // Mathematics Magazine. — 1995. — Vol. 68, no. 1. — Pp. 42-47.

178. Saito, M. Grobner deformations of hypergeometric differential equations / M. Saito, B. Sturmfels, N. Takayama. — Springer-Verlag, New York, 1999.

179. Samarskii, A. A. The theory of difference schemes / A. A. Samarskii. — New York, Marcel Dekker, 2001.

180. Schii, J. Algorithmic methods for lie pseudogroups / J. Schii, W. M. Seiler, J. Calmet // Modern Group Analysis: Advanced Analyticaland Computational Methods in Mathematical Physics / Ed. by N. H. Ibragimov. — Kluwer, Dordrecht, 1993.— Pp. 337-344.

181. Schwarz, F. The riquier-janet theory and its application to nonlinear evolution equations . / F. Schwarz // Journal of Mathematical Physics.- 1984. Vol. 11D. - Pp. 243-251.

182. Schwarz, F. Janet bases of 2nd order ordinary differential equations / F. Schwarz // Proceedings of ISSAC / Ed. by Y. N. Lakshman. ACM Press, 1996.- Pp. 179-188.

183. Seller, W. M. On the Arbitrariness of the General Solution of an Involutive Partial Differential Equation / W. M. Seiler. — Montr'eal, Canada, 1993,- Preprint CRM-1873, Montr'eal.

184. Seiler, W. M. Analysis and Application of the Formal Theory of Partial Differential Equations: Ph.D. thesis / Lancaster University. — 1994.

185. Seiler, W. M. On the arbitrariness of the general solution of an involutive partial differential equation / W. M. Seiler // Journal of Mathematical Physics. 1994. - Vol. 35. — Pp. 486-498.

186. Seiler, W. M. Applying axiom to partial differential equations: Tech. Rep. Internal Report 95-17 / W. M. Seiler: 1995.

187. Seiler, W. M. A combinatorial approach to involution and ^-regularity I: Involutive bases in polynomial algebras of solvable type /

188. W. M. Seiler. — Mannheim, Germany, 2002. — Preprint Universit at Mannheim.

189. Seiler, W. M. A combinatorial approach to involution and ^-regularity I: Structure analysis of polynomial modules with Pommaret bases / W. M. Seiler. — Mannheim, Germany, 2002. — Preprint Universit at Mannheim.

190. Seiler, W. M. Involution-the formal theory of differential equations and its applications in computer algebra and numerical analysis. — 2002.

191. Seiler, W. M. Involution analysis of the partial differential equations characterizing Hamiltonian vector fields / W. M. Seiler // Journal of Mathematical Physics. 2003,- Vol. 44, no. 3.- Pp. 1173-1182.

192. Seiler, W. M. Involution and constrained dynamics / W. M. Seiler, R.W. Tucker // Journal of Mathematical Physics. — 1995. — Vol. 28. — Pp. 4431-4451.

193. Semenov, A. S. Slice and pair properties / A. S. Semenov //

194. Programming and Computer Software. — 2005.— Vol. 31, no. 2.— Pp. 81-86.

195. Semenov, A. S. On constructivity of involutive divisions / A. S. Semenov // Programming and Computer Software. — 2006. — Vol. 32, no. 2. Pp. 96-102.

196. Shemyakova, E. S. Involutive divisions, graphs / E. S. Shemyakova // Programming and Computer Software. — 2004. — Vol. 30, no. 2. — Pp. 68-74.

197. Shemyakova, E. S. Involutive divisions for effective involutive algorithms / E. S. Shemyakova // Journal of Mathematical Sciences. — 2006. Vol. 135, no. 5. - Pp. 3425-3436.

198. Sit, W. Y. The ritt-kolchin theory for differential polynomials / W. Y. Sit // Differential Algebra and Related Topics. — World Scientific, 2001.

199. Strikwerda, J. C. Finite difference schemes and partial differential equations / J. C. Strikwerda. Philadelphia, SIAM, 2004.

200. Sylvester, J. J. A method of determining by mere inspection the derivatives from two equations of any degreev / J. J. Sylvester // Phil. Mag. 1840,-Vol. 16.-Pp. 132-135.

201. Thomas, J. Differential Systems / J. Thomas.— American Mathematical Society, New York, 1937.

202. Thomas, J. W. Numerical partial differential equations: finite difference methods / J. W. Thomas. — New York, Springer-Verlag, 1998.

203. Thomas, J. W. Numerical partial differential equations: conservationlaws and elliptic equations / J. W. Thomas. — New York, Springer-Verlag, 1999.

204. Topunov, V. L. Reducing systems of linear differential equations to a passive form / V. L. Topunov // Acta Appl. Math. — 1989. — Vol. 16. — Pp. 191-206.

205. Того, E. F. Riemann solvers and numerical methods for fluid dynamics / E. F. Того, — Berlin, Springer-Verlag, 1997.

206. Trari, Q.-N. Parallel computation and Grobner bases: An application for converting bases with the Grobner walk / Q.-N. Tran. — 1998.— Pp. 519-531.

207. V., Weispfenning. Differential term-orders / Weispfenning V. // International Symposium on Symbolic and Algebraic Computation. — Kiev: ACM press, 1993. Pp. 245-253.

208. Wu, W.-T. On the foundation of algebraic differential geometry / W.-T. Wu // System Sciences and Mathematical Sciences. — 1989. — Vol. 2. Pp. 289-312.

209. Yan, T. The geobucket data structure for polynomials / T. Yan // Journal of Symbolic Computation.— 1998.— Vol. 25, no. 3.— Pp. 285-294.

210. Zhang, S. An implementation for the algorithm of janet bases of linear differential ideals in the maple system / S. Zhang, Z. Li // Acta Mathematicae Applicatae Sinica.— 2006.— Vol. 20, no. 4.— Pp. 605-616.

211. Zharkov, A. Yu. Involutive Polynomial Bases: General Case / A. Yu. Zharkov. Preprint JINR E5-94-224, Dubna, 1994.- (Preprint E5-94-224, Joint Institute for Nuclear Research).

212. Zharkov, A. Yu. Private communication / A. Yu. Zharkov.

213. Zharkov, A. Yu. Solving zero-dimensional involutive systems / A. Yu. Zharkov // Algorithms in Algebraic Geometry and Applications / Ed. by L. Gonzales-Vega, T. Recio. — Vol. 143 of Progress in Mathematics. Birkhauser, Basel, 1996,- Pp. 389-399.

214. Zharkov, A. Yu. Algorithm for reducing systems of PDEs to involutive form / A. Yu. Zharkov, Yu. A. Blinkov // Proceeding of the International Workshop New Computer Techologics in Control Systems. — Pereslavl-Zalessky, Russia: 1994,— Pp. 90-92.

215. Zharkov, A. Yu. Involutive Bases of Zero-Dimensional Ideals / A. Yu. Zharkov, Yu. A. Blinkov. Preprint E5-94-318 JINR, Dubna, 1994. — P. 10.

216. Zharkov, A. Yu. Involution approach to investigating polynomial systems / A. Yu. Zharkov, Yu. A. Blinkov // Mathematics and Computers in Simulation. — 1996.— Vol. 42, no. 4-6.— Pp. 323-332.

217. Арайс, E. А. Реализация метода внешних форм Картана на ЭВМ /

218. Е. А Арайс, В. П. Шапеев, Н. Н. Яненко // Доклады АН СССР. — 1974. Т. 214, № 4. - С. 737-738.

219. Блинков, Ю. А. Деление и алгоритмы в задаче о принадлежности к идеалу / Ю. А. Блинков // Известия Саратовского университета. 2001.- Т. 1, № 2,- С. 156-167.

220. Блинков, Ю. А. Инволютивные базисы торических идеалов / Ю. А. Блинков // Математика-Механика. Сб. науч. тр.— 2001.— Т. 3.- С. 14-16.

221. Блинков, Ю. А. Метод сепарирующих мономов для инволютивных делений / Ю. А. Блинков // Программирование. — 2001.— Т. 27, № 3. С. 43-45.

222. Блинков, Ю. А. Вычисление базисов Жане торических идеалов / Ю. А. Блинков // Программирование. — 2002. — Т. 28, № 5. — С. 65-68.

223. Блинков, Ю. А. Специализированная система компьютерной алгебры GINV / Ю. А. Блинков, В. П. Гердт // Программирование. — 2008. Т. 34, № 2. - С. 67-80.

224. Блинков, Ю. А. Метод конечных объемов для уравнения высших порядков / Ю. А. Блинков, В. В. Мозжилкин // Аэродинамика: Нелинейные проблемы. Межвуз. науч. сб. — 1997.— Т. 14(17).— С. 141-149.