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

Объект исследования и актуальность темы.

Системы нелинейных алгебраических полиномиальных уравнений часто возникают в различных областях науки и техники: в построении формул (см. пример 1.0.4), проблеме пересечения поверхностей в геометрии (см. пример 1.0.5), в обратной кинематической задаче (см. пример 1.0.6), в задаче об ангармонических осцилляторах, которую мы рассмотрим в главе 4 и т. д.

Численное решение систем полиномиальных уравнений сопряжено с некоторыми проблемами:

• погрешности решения.

• невозможность распознать и тем более решить недоопределенные системы.

• возможная потеря корней и т. п.

Этих проблем можно избежать, если использовать символьные или гибридные численно-символьные методы решения.

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

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

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

2- Исследование поведения алгоритма на различных тестовых примерах и прикладных задачах;

3. Разработка параллельной версии алгоритма и исследование ее особенностей;

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

1. На многочисленных тестовых примерах и в сравнении со специализированными системами компьютерной алгебры Singular [27] и Magma [54], обладающими самыми быстрыми реализациями классического алгоритма Бухбергера [6] вычисления базисов Грёбнера выявлены преимущества базисов Жане по скорости вычислений.

2. Показана естественная параллелизуемость с высокой степенью масштабируемости алгоритма вычисления базисов Жане.

3. Создан эффективный комплекс программ для численного нахождения корней полиномиальных систем основанный на вычислении ин-волютивных базисов Жане.

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

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

Отдельный модуль для вычисления инволютивных полиномиальных базисов Жане встроен в специализированную систему компьютерной алгебры Singular, созданную в университете Кайзерслаутерна, ФРГ и являющуюся ведущей из специализированных систем, ориентированных на задачи коммутативной алгебры и алгебраической геометрии.

Апробация работы. Основные результаты и положения диссертационной работы доложены и обсуждены на: научных семинарах ЛИТ ОИЯИ t семинарах по компьютерной алгебре ВМК МГУ.

• научном семинаре в университете Кайзерслаутерна.

VI международной конференции по применению компьютерной алгебры АСА'2000, Ст.-Петербург, июнь 2000 2й международной конференции «Современные тенденции в вычислительной физике», Дубна, июль 2000 t IV международной конференции по компьютерной алгебре в научных вычислениях CASC'2001, Констанц, ФРГ, 2001.

• международной конференции по компьютерной алгебре и ее применению в физике, СААР'2001 Дубна, июнь 2001 щ международной конференция «Недоопределенные и переопределенные системы алгебраических и дифференциальных уравнений» Карлсруе, ФРГ, март 2002.

V международном конгрессе по математическому моделированию, Дубна, сентябрь-октябрь 2002. щ V международной конференции «Симметрии в нелинейной математической физике» Киев, июнь 2003.

• VI Международная конференция по компьютерной алгебре в научных вычислениях CASC'2003 Пассау, ФРГ, сентябрь, 2003.

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

Диссертация состоит из введения, трех глав, заключения, приложения и списка литературы. Диссертация содержит 111 страниц, 4 таблицы, 4 рисунка.

Список литературы

содержит 78 работ, из них 5 на русском, 73 на иностранных языках.

Основные результаты полученные в диссертации.

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

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

3. На языке С разработан переносимый универсальный программный комплекс для численно-аналитического решения систем алгебраических уравнений с конечным числом корней, основанный на вычислении базиса Жане в упорядочении сначала по полной степени и затем по обратному лексикографическому порядку с последующим преобразованием этого базиса в чисто лексикографический базис Грёбнера и нахождением корней этого базиса аналитическими (где это возможно) или численными методами.

4. С помощью разработанного программного комплекса впервые найдены условия точной разрешимости уравнения Шредингера для двух-параметрического класса центральных потенциалов полиномиального типа при больших значениях пространственной размерности. При выполнении этих условий явно найдены решения переопределенной системы нелинейных уравнений (системы Магьяри), эквивалентной.

5.1. 1. задаче решения уравнения Шредингера.

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

Выражаю глубокую благодарность своему соавтору Милославу Зной-луза совместную работу, результаты которой вошли в Главу 4. Я также признателен сотрудникам сектора компьютерной алгебры ЛИТ В.В. Кор-няку, В. А. Ростовцеву, В. М. Северьянову, A.M. Рапортиренко и А. Бого-любской за полезные обсуждения и поддержку.

Я также благодарю профессоров Жидкова Е. П. и Пузынина И. В. за полезные замечания, высказанные во время научных семинаров ЛИТ, на которых были представлены результаты, вошедшие в диссертацию.

Автор искренне признателен дирекции ЛИТ в лице Р. Г. Позе, И. В. Дузынина и В. В. Иванова за создание благоприятных условий в процессе работы над диссертацией.

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

Основные обозначения.

Пусть К = К[х 1,., ж&bdquo-] — кольцо полиномов над полем К характеристики нуль. В работе будут использованы следующие обозначения:

С — поле комплексных чисел.

X =, хп) — вектор в Сп. д, Л, р, 4 — полиномы из К. а, Ь, с — элементы поля К. х = (хи,., хп) — а — вектор в Мп.

Г, <2, Н — конечные подмножества М.

М = {ха | а € Кп} — множества мономов в М.

Т = {аа:а | ха € М, а € К} — множества термов Ж.

V, — мономы или термы с ненулевыми коэффициентами. и, V, IV — подмножества в М. 4едг{и) — степень переменной х, — в и. х1ед (и) — полная степень и. с/(/, и)? К — коэффициент терма и полинома /.

Р) — идеал в М порожденный множеством полиномов Р.

— — допустимое упорядочение термов, причем будем полагать что х >агг >-•••>- хп.

И (/) — лидирующий терм / для данного допустимого упорядочения >-.

М/) = с/(/,/£(/)) — лидирующий коэффициент /.

1тп (/) = И (/)/1с (/) — лидирующий моном /.

И{Р} = {/?(/)|/ множество лидирующих термов из .Р.

1ст{Е) — наименьшее общее кратное элементов множества {/?(/) |/ € .Р}.

Если моном и делит моном и, то это будем записывать в виде.

А. Таблицы времен исполнения.

5.

Заключение

.