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

ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ

11-2004-15

На правах рукописи УДК 004.421.2:512.714+ 519.615.5:530.145.61

ЯНОВИЧ

Денис Александрович

АЛГОРИТМЫ И ПРОГРАММЫ ВЫЧИСЛЕНИЯ ИНВОЛЮТИВНЫХ БАЗИСОВ И ИХ ПРИМЕНЕНИЕ ДЛЯ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Специальность: 05.13.18 — математическое моделирование, численные методы и комплексы программ

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

Дубна 2004

Работа выполнена в Лаборатории информационных технологий Объединенного института ядерных исследований.

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

профессор Гердт В. П.

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

профессор Абрамов С. А., ВЦ РАН

кандидат физико-математических наук Васильев Н. Н., ПОМИ РАН

Ведущая организация: Научно-исследовательский институт ядерной

физики им. Д.В.Скобельцына Московского государственного университета им. М.В. Ломоносова

Защита состоится " " и^^А^_2004 г. в IЦ ч. 00 мин на заседании диссертационного совета Д720.001.04 в Объединенном институте ядерных исследований (Лаборатория информационных технологий), г. Дубна, Московской области.

С диссертацией можно ознакомиться в библиотеке Объединенного института ядерных исследований.

Автореферат разослан

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

кандидат физико-математических наук ¡ДА З.М. Иванченко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

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

♦ погрешности решения

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

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

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

Цель и задачи исследования

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

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

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

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

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

»ос. ианиомллымя ] 1 ИМИОТШ |

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

1. На многочисленных тестовых примерах и в сравнении со специализированными системами компьютерной алгебры Singular1 и Magma2, обладающими самыми быстрыми реализациями классического алгоритма Бухбергера3 вычисления базисов Грёбнера выявлены преимущества базисов Жане по скорости вычислений и по потребляемой памяти.

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

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

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

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

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

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

'Greuel G.-M., PfisterG. A Singular Introduction to Commutative Algebra. Springer-Verlag, Berlin, 2002. http://www.singular.Tmi-kl.de.

2Bosma W., Cannon J., Playoust C.: The Magma algebra system I: The user language. J. Symb. Сотр., 24(3/4):235-265,1997.

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

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

Основные результаты и положения диссертационной работы доложены и обсуждены на:

♦ научных семинарах ЛИТ ОИЯИ;

♦ семинарах по компьютерной алгебре ВМК МГУ;

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

♦ VI международной конференции по применению компьютерной алгебры АСА'2000, Ст.-Петербург, июнь 2000;

♦ 2й международной конференции «Современные тенденции в вычислительной физике», Дубна, июль 2000;

♦ IV международной конференции по компьютерной алгебре в научных вычислениях САБС2001, Констанц, ФРГ, 2001;

♦ международной конференции по компьютерной алгебре и ее применению в физике, СААР'2001, Дубна, июнь 2001;

♦ международной конференция «Недоопределенные и переопределенные системы алгебраических и дифференциальных уравнений», Карлсруе, ФРГ, март 2002;

♦ V международном конгрессе по математическому моделированию, Дубна, сентябрь-октябрь 2002;

♦ V международной конференции «Симметрии в нелинейной математической физике», Киев, июнь 2003;

♦ VI Международной конференции по компьютерной алгебре в научных вычислениях САБС2003, Пассау, ФРГ, сентябрь, 2003;

По теме диссертации опубликовано 8 работ.

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

В разделе 1.1.3 описывается метод решения систем уравнений, основанный на использовании базисов Грёбнера4 и состоящий из трех этапов:

1. Проверка совместности системы и конечности числа решений.

2. Получение лексикографического5 базиса Грёбнера, который имеет следующую структуру для переменных ... У хп: единственный полином /(х„) = 0, несколько полиномов /(x„_i,x„) = 0 и т.д. Его форма чрезвычайно удобна для вычисления корней системы.

3. Собственно вычисление корней аналогично обратному ходу метода Гаусса.

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

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

*СохD.,LitUe J., O'Shea D.: Using Algebraic Geometry. Springer- Verlag, pp.24-51,1998.

'Robbiano, L.: On the theory of graded structures, J. Symb. Сотр. 2 (1986) 139-170

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

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

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

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

1. Выбор минимального по упорядочению элементар множества полиномов Q.

2. Вычисление его инволютивной нормальной формы - NFi(p,T).

3. Занесение его в промежуточный базис Т и затем занесение его продолжений в Q.

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

1. Выполнение полной редукции старших мономов для всех полиномов, входящих в Q.

2. Выбор минимального по упорядочению элемента р множества полиномов Q.

3. Полная инволютивная редукция р.

4. Занесение его в базис и затем занесение его продолжений в Q.

'Gerdt V.P., Blinkov Yu.A.: Involutive Bases of Polynomial Ideals Math. Сотр. Sim. 1998, 45. P.519- • 542.

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

Алгоритм 1 ParallelJanetBasis(F, х, Jmp) Input: FeR\ {0}, конечное полиномиальное множество; -<, допустимое упорядочение; Jmp - число одновременных редукций Output: G, минимальный базис Жане Id(F) 1: choose / € F с минимальным 1тп(д) по >-

2: р:={/,М/)} Г:={р} 3: Q :={{<?, lm(q)}\q&F\{f}} 4: InvoIutiveReduction(Q,T, Jmp) 5: while Q + 0 do

6: choose peQy которого Im(pol(p)) не имеет делителя в

{lm(pol(g)) | 9 е Q \ {p}} 7: if lm(poI(p)) = 1 then 8: return {1} 9: else

10: Q-Q\{p}

11: pol(p) := NFj(po\(p), {pol(f) | / € T}) 12: if lm(pol(p)) = anc(p) then 13: for all {/ € T | Zm(pol(/)) У Im(pol(p))} do

14: Q:=QU{/} T:=T\{f}

15: Od

16: fi 17: fi

18: T:=T Up Q :— Q U {p • x,x £ NMj(p, T)} 19: InvolutiveReduction(Q, T, J up) 20: od

21: G := {pol(f) | / 6 T}

Есть несколько возможностей распараллеливания этого алгоритма:

♦ Распараллеливание инволютивной редукции старших мономов множества О по Т (строки 4,19) - именно этот пункт и позволяет получить существенный прирост производительности.

♦ «Заглядывание вперед» при выборе полинома для очередного занесения в Т: мы можем выбрать несколько кандидатов, подсчитать их полные инволютивные нормальные формы (строка 11) и выбрать ту, которая нам больше подходит.

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

Раздел 2.3 посвящен решению исходной системы путем символьного (если это возможно) или численного нахождения корней лексикографического базиса Грёбнера. Процесс этот напоминает обратный ход метода Гаусса: сначала получаем корни полинома от одной переменной (который всегда единственен в лексикографическом базисе); затем подставляем полученные значения в систему и опять получаем полином от одной переменной и т.д. Есть два пути нахождения корней полинома:

1. Универсальный численный (но тут нас опять ждут трудности с погрешностями).

2. Аналитический (путем символьных вычислений), применимый в отдельных, описанных ниже, случаях.

Если полином факторизуется, и степени факторов не превосходят 4 - для нахождения корней используется программа на языке системы Reduce8 и корни выводятся в аналитическом виде. Иначе, при помощи написанного автором на основе библиотеки научных вычислений PARP компонента программного комплекса ROOTS, производится численное вычисление корней полинома и соответственно системы уравнений.

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

Рассмотрим множество полиномов с лидирующими мономами, образующими множество и отобразим его в виде дерева Жане, как показано на следующем рисунке.

' Amrhetm В., Gloor О., КпсЫт W. A Case Study of Multi-Threaded Grobner Basis Completion. Proceedings oflSSAC'96 (1996) 95-102.

8http://www.uni-koeln.de/REDUCE/

•http://www.parigp-home.de

Рис. 1: Дерево Жане

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

Рассмотрим теперь структуру бинарного дерева Жане {JanetTree, сокращенно JT) общего вида, как множества вершин и листьев JT = U{f}, сопоставляемого непустому множеству мономов. Каждой элементу дерева и будем сопоставлять множество из четырех элементов v = со следующей структурой:

IDeg{v) = d — степень переменной,

M(m{v) = и — моном, сопоставляемый данной вершине ,

Ndg{v) = nd — указатель на следующую по степени вершину,

Nvr(v) = nv — указатель на следующую по переменной вершину.

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

Корню дерева, который обозначим v0, мы сопоставим нулевую степень текущей переменной и единичный моном и = 1. Вершины и листья дерева JT обладают состояниями:

Вершина: Nvr{v) ф nil V (Ndg(v) ф nil Л Deg{v) < Deg{Ndg(v))) Лист: Nvr{v) = nil Л Ndg(y) = nil

Для быстрого поиска делителя Жане монома w ф 1 в заданном дереве, соответствующем моном иалыюму. множеству U ф {1}, мы использовали алгоритм JanetDivisor приведенный ниже.

Алгоритм 2 JanetDivisor(JT, w) Input: JT - дерево Жане, w - моном

Output: моном и | j w листа JT или nil в противном случае ' 1: d := deg(w) 2: г := 1 3: v := va 4: while d > 0 do

5: while Deg(v) < degt(w) and Ndg(v) do 6: v := Ndg(v) 7: od

8: if Nvt(l>) then 9: d:—d — degi(w) 10: г := г + 1 11: v ■.— Nvr(u) 12: elif Ndg(v) then 13: return nil 14: else

15: return Mon{v) 16: fi 17: od

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

Теорема 1 Пусть d наибольшая полная степень мономов от п переменных из мономиального множества U. Тогда временная сложность алгоритма JanetDivisor и алгоритма бинарного поиска делителя Жане ограничены соответственно

¿BmarySearch(l7) = 0(n((d + п) log(d + п) - П log(n) - dlog(d))).

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

В разделе 3.1 описывается представления данных, которые позволили эффективно реализовать алгоритмы, предложенные в диссертации. Как известно10, в вычислениях с полиномами над полем целых чисел (которые доминируют в нашем комплексе) очень важны два фактора: быстрые операции над коэффициентами и мономами. Для операций над целыми произвольной длины мы использовали библиотеку СМР11, которая является одной из быстрейших в мире. Все вычисления, производящиеся в нашем программном комплексе над мономами, можно разбить на несколько классов: вычисление полной степени монома про-

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

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

где (t'i,..., in)T - вектор степеней монома в исходном упорядочении -<i, M^l = {cjtj|fc = l,n,I = l,n} - матрица преобразования, (ji,-..,jn)T

- вектор степеней монома в лексикографическом упорядочении -<2- То есть, для максимально быстрых операций с мономами следует действовать по такой схеме:

1. Кодируем все мономы входного набора в нужное нам упорядочение.

2. Проводим все необходимые операции.

3. Перед выводом результатов декодируем опять же весь набор.

10Кнут Д. Искусство программирования на ЭВМ. М., Мир,т 2, с.354-384,1977. 1 * http: //Www. 8 wox. com/gmp

'2Robbiano, L.: On the theory of graded structures, J. Symb. Сотр. 2 (1986) 139-170.

Раздел 3.2 посвящен описанию форматов входных файлов комплекса и схемы его работы (см. рис. 2). Комплекс состоит из трех, функционально различных, программ:

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

2. FGLM, конвертирующей13 базис Грёбнера в исходном упорядочении в базис Грёбнера в лексикографическом упорядочении.

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

следовательно и исходной системы.

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

Раздел 4.1 содержит постановку задачи о решении уравнения Шре-дингера с центральным полиномиальным потенциалом

(г) = д0 г2 + <71 Г4 + ... + д2д г4'+2, <72? = 72>0, (1)

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

В разделе 4.2 приведен вывод системы Магьяри (решение которой эквивалентно решению исходной задачи). Рассмотрим уравнение Шре-дингера в радиальной форме

с потенциалом вида (1). Рассмотрим представления

и«>(г) = £/('>(г)+г2[И^(г)]2, и{ч\г) = G0r2 + G1r4 + ...+Gg:1r2"1

13Fougère J. С., Gianni P., Lazard D. and Мота T.: Efficient Computation of Zero-dimensional Grôbner Bases by Change of Ordering, J. Symi. Сотр. 16 (1993) 329-344.

Исходная система Example.in

Ф t

Инволютивный базис в упорядочении DegRevLex

JB

example.ibasis example.gbasis

Базис Грёбнера в упорядочении 1ех

example.ses

[fglm|i=^> example.lex

example.ses f.

Решение треугольной системы

roots

example.ses

о

Корни исходной ехатр1е.гоо18 системы

Рис. 2: Схема программного комплекса

W{4\r) = а0 + аУ + ..'. + agr2q

(3)

Эти формулы дают репараметризацию полинома (1), как функции от г и приводят к однозначному соотношению между двумя наборами констант взаимодействия

При а„ > 0 можно проверить, что

и подстановка

преобразует радиальное уравнение (2) + (1) в эквивалентную линейную алгебраическую задачу

(6)

с асимметричной прямоугольной матрицей

Элементы этой матрицы билинейно зависят от параметров

При любом фиксированном конечном N — 1,2,... прямоугольная система (6) представляет собой переопределенную систему из N + q линейных уравнений для неизвестных, являющихся первыми N компонентами вектора При q = 0 эти уравнения имеют вид рекурсий и определяют

состояния гармонического осциллятора' При q = 1 мы приходим к модели осциллятора шестой степени по г. При этом "выпадающая" последняя строка фиксирует одну из констант связи и мы получаем диагональную матрицу NxN которая определяет N— плет вещественных энергий. При q > 1 ситуация намного сложнее. Подсчет числа параметров и уравнений показывает, что лишь малая часть мультиплетов связанных состояний может быть получена в замкнутой форме14.

В разделе 4.3 система Магьяри переписывается и упрощается для случая большой пространственной размерности D. При q > 1 вычислительная трудность решения задачи сильно возрастает при росте N. Поэтому необходимы некоторые упрощения для рассматриваемого нами случая D > 1. При любом значении D последнее уравнение в (6) не связано с остальными и значит при любом q > 1 оно может рассматриваться как условие на последнюю константу связи

Подстановка этого определения константы gq_j упрощает вид нижней диагонали

Так как j = 0 мы можем переписать (б) в более компактной форме

при размере прямоугольной матрицы

Пусть в исходном дифференциальном уравнении (2) значение пространственной размерности D будет достаточно большим. Преобразуем элементы старой матрицы

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

СМ = (2га+2) D, = -<м-а0£>, = -gk^-akD,k< q

14Znojil, M., Leach, P. G. L.: On the elementary Schrödinger bound states and their multiplets. J. Math. Phys. 33 (1992) 2785 - 2794.

(заметим что = .А^0' оставлено неизменным). Затем преобразуем координаты (то есть и коэффициенты) следующим образом

А™ (13)

Далее заменим энергии и константы связи {#-1, до,..., дч-ъ\ параметрами

дк-2 = -<хк-10--ггт «Ь к = 1,2,..., я. (14)

1

где

М = , т = т(1)) = (29+2 Б'7) . (15)

В результате всех этих преобразований наша система Магьяри может

быть записана в следующей компактной форме ( 4

«2 N-1

\

В разделе 4.4 приводятся полученные решения уравнения Шредин-гера для различных значений пространственной размерности и степени потенциала.

Для осциллятора с потенциалом шестой степени при д = 1 и для любого N все вещественные (т.е. физические) корни в = в^") - суть целые числа. Более того, они могут быть представлены одной компактной фор-

Ясно, что все коэффициенты также могут быть преобразованы к целым

N = 2,

РУ = -Р?]=2,

Р? = о,

N = 3,

и т.д.

Записывая эти решения в компактном виде, мы получили следующую форму волновой функции

N-3 / г2\

= /+1 (l + ' (l - ^У ехр (-¿щг2 - ,

¿ = 1,2,...,ЛГ.

(18)

Значения энергии, определяемые уравнением (17) образуют регулярный мультиплет. Возникает вопрос - сохранится ли подобная регулярность при больших целых значениях q >1? Ответ - да, сохранится.

Для осциллятора с потенциалом десятого порядка при q = 2 и для любого Ы, если обозначить вх = в и вг = то обнаруживается, что задача

я ( Н+ '

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

плексными корнями 5 при любых N, а все физические корни (значения энергии) могут быть описаны следующей формулой

то з;

ком-

После многократного применения нашего программного комплекса для решения систем при более высоких измерениях N, получается правило (19): при любых значениях измерения N существуют только такие вещественные корни, что з^') = ¿И) Это означает, что для каждого значения энергии, которое «допустимо», конструируется «допустимая» константа связи

Далее в диссертации приведены все решения подобного вида вплоть до случая q = 5 и N = 9.

Приложения к диссертации содержат таблицы времен выполнения и набор примеров, которые выступали в роли тестовых. Программный комплекс для решения систем уравнений может быть загружен с сайта автора http: //invo. j inr. ru, там же находятся в открытом доступе ряд публикаций, связанные с тематикой диссертации.

Заключение

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

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

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

3. На языке С разработан переносимый универсальный программный комплекс для численно-аналитического решения систем алгебраических уравнений с конечным числом корней, основанный на вычислении базиса Жане в упорядочении сначала по полной степени

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

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

Основное содержание диссертационной работы изложено в публикациях:

1. Гердт В. П., Блинков Ю.А., Янович ДА. Быстрый поиск делителя Жане. // Программирование-2001.—т. 27, EP1.— С. 22-24, Москва.

2. Gerdt, V.P., Blinkov, Yu.A., Yanovich, DA. Construction of Janet Bases. I. Monomial Bases. // Computer Algebra in Scientific Computing / CASC'Ol, V.G.Ganzha, E.W.Mayrand E.V.Vorozhtsov (Eds.), Springer-Verlag, Berlin, 2001, pp.233-247.

3. Gerdt, V.P., Blinkov, YuA., Yanovich, DA. Construction of Janet Bases. II. Polynomial Bases. // Computer Algebra in Scientific Computing / CASC'Ol, V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp.249-263.

4. Gerdt, V.P., Yanovich, DA. Parallelism in Computing Janet Bases. // Proceedings of CAAP'01, June 28-30, 2001, Dubna, Russia.

5. Gerdt V.P., Yanovich DA. Parallelization of an Algorithm for Computation of Involutive Janet Bases. // Programming and Computing Software.— 2002- Vol. 28, ISP2. - pp. 66-69, Москва.

6. Gerdt V.P., Yanovich DA. Implementation of the FGLM Algorithm and Finding Roots of Polynomial Involutive Systems. // Programming and Computing Software — 2003 —Vol. 29, ISP2.— pp. 72-74, Москва.

7. Znojil, M., Yanovich, DA., Gerdt, V.P. New exact solutions for polynomial oscillators in large dimensions. // J. Phys. A: Math. Gen.— 2003.— (36) pp.6531-6549 (LANL arXiv math-ph/0302046).

8. Gerdt V.P, Yanovich DA., Znojil M. On Exact Solvability of Anharmonic Oscillators in Large Dimensions. // Computer Algebra in Scientific Computing / CASC 2003, V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov (Eds.). Institute of Informatics, Technical University of Munich, Garching, 2003, pp.143162 (LANL arXiv math-ph/0310012)

Получено 13 февраля 2004 г.

Р- 80 6 1

Макет Н. А. Киселевой

Подписано в печать 16.02.2004. Формат 60 X 90/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,12. Уч.-изд. л. 1,35. Тираж 100 экз. Заказ № 54303.

Издательский отдел Объединенного института ядерных исследований 141980, г. Дубна, Московская обл., ул. Жолио-Кюри, 6. E-mail: publish@pds.jinr.ru www.jinr.ru/publish/

1 Введение

1.1 Некоторые методы решения систем нелинейных алгебраических уравнений .^

1.1.1 Метод интервалов.

1.1.2 Метод гомотопичного продолжения решения

1.1.3 Метод, использующий базисы Грёбнера

2 Символьно-численный метод решения систем уравнений на основе инволютивных базисов

2.1 Определения и алгоритмы вычисления

2.2 Параллельный алгоритм вычисление инволютивного базиса

2.3 Символьное и численное вычисление корней

2.4 Быстрый поиск делителя Жане

3 Особенности программной реализации

3.1 Представление данных

3.1.1 Числа

3.1.2 Мономы

3.1.3 Полиномы.

3.1.4 Частичный базис (Т) и множество продолжений

3.2 Схема программного комплекса и форматы файлов

4 Решение уравнения Шредингера с центральным полиномиальным потенциалом

4.1 Ангармонические осцилляторы и проблема их решения

4.2 Вывод уравнений Магьяри.

4-3 Уравнения Магьяри для большой пространственной размерности

4.4 Результаты для полиномиальных потенциалов при различных д

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

Системы нелинейных алгебраических полиномиальных уравнений часто возникают в различных областях науки и техники: в построении формул (см. пример 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,., ж„] — кольцо полиномов над полем К характеристики нуль. В работе будут использованы следующие обозначения:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Заключение

1. Kearfott R.: 1.terval arithmetic techniques in the computational solution of ' nonlinear systems of equations: Introduction, examples and comparsion. In

2. E.Lu Allgower and K. Georg, editors, Computational Solutions of Nonlinear Systems of Equations, pp. 337-357, Providence, Rhode Island, 1990. AMS.

3. Vrahatis M.N.: Solving systems of nonlinear equations using the nonzero value of the topological degree. ACM Trans. Math. Softw., 14(4):312-329,1988.

4. Verschelde J., Verlinden P., Cools R.: Homotopies exploiting Newton polytopes for solving sparse polynomial systems. SIAM J. Numer. Anal., 31(3):915-930, 1994.

5. Li T.Y.: Solving polynomial systems. The Mathematical Intelligencer, 9(3):33-39, 1987.

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

7. Grabe H.G.: On Factorized Grobner Bases: Proceedings of «Computer Algebra in Science and Engineering» Bielefeld, August 28-31, 1994.

8. Дэвенпорт Дж., Сире И., Турнье Э.: Компьютерная алгебра. Системы и алгоритмы алгебраических вычислений. М., "Мир", 1991.

9. Gerdt V.P., Blinkov Yu.A.: Minimal Involutive Bases Math. Comp. Simul. 1998, 45. P.543-560.

10. J.3. Gerdt V.P.: Involutive Division Technique: Some Generalizations and Optimizations. Записки научных семинаров СПОМИС.Петербург, 1999, 258. С.185-206.

11. Janet M.: Leçons sur les Systèmes d'Equations aux Dérivées Partielles / Cahiers Scientifiques, IV, Gauthier-Villars, Paris, 1929.

12. J.5. Pommaret, J.F.: Systems of Partial Differential Equations and Lie Pseudogroiips. Gordon Sz Breach, New York, 1978.

13. J.6. Zharkov A. Yu.: Involutive Polynomial Bases: General Case. Preprint JINR E5-94-224, Dubna, 1994.

14. Becker, T., Weipfenning, V., Kredel, H.: Gröbner Bases. A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics 141, Springer-Verlag, New York, 1993.

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

16. J.9. Жарков А.Ю., Блинков Ю.А.: Инволютивные системы алгебраических уравнений. Программирование. 1994, 1. С.53-56.

17. Gerdt, V.P., Blinkov, Yu.A., Yanovich, D.A.: Construction of Janet Bases. I. Monomial Bases. Computer Algebra in Scientific Computing / CASC'Olr V.G.Ganzha, E.W.Mayr and E.V.Vorozhtsov (Eds.), SpringerVerlag, Berlin, 2001, pp.233-247.

18. Robbiano, L.: On the theory of graded structures, J. Symb. Comp. 2 (1986) 139-170

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

20. Verschelde J. The Database with Test Examples. http: / / www. math .uic.edu/~j an/demo. html.

21. Amrheim B., Gloor O., Kuchlin W. A Case Study of Multi-Threaded Grobner Basis Completion. Proceedings of ISSAC'96 (1996) 95-102.

22. Greuel G.-M., Pfister G. A Singular In troduction to Commutative Algebra. Springer- Verlag, Berlin, 2002. http://www.singular.uni-kl.de.28. httpr//www:swox.com/gmp.

23. Schrans S., Troost W.: Generalized Virasoro constructions for SU(3). Nuclear Phys. B, 345(2-3):584-606, 1990.

24. Bjdrk G., Froberg R.: A faster way to count the solutions of inhompgeneous systems of algebraic equations, with applications to cyclic n-roots. J. Symbolic Computations, 12(3):329-336, 1991.

25. Van Hentenryck P., McAlister D., Kapur D.: Solving polynomial systems using a branch and prune approach. Technical Report No. CS-95-01, Department of Computer Science, Brown University, 1995.

26. Butcher C.: An application of the Runge-Kutta space. BIT, 24, pages 425440, 1984.

27. Herbert Melenk, H. Michael Moeller, Winfried Neun: Symbolic Solution of Large Stationary Chemical Kinetics Problems. IMPACT Comp. Sei. Eng. 1, p.138-167, 1989.

28. H. Hong and V. Stahl: Safe Starting Regions by Fixed Points and Tightening. Computing 53(3-4): 322-335, 1995.

29. Faugtre J.C.: A new efficient algorithm for computing Grobner Basis (F4). Technical report, Task 3.3.2.1 Frisco report, 1997. preprint.

30. Jan Verscheide: Homotopy Continuation Methods for solving Polynomial Systems. PhD thesis, Katholike Univ. Leuven, May 1996.

31. Alexander Morgan: Solving polynomial systems using continuation for engineering and scientific problems. Prentice-Hall, Englewood Cliffs, New Jersey, 1987, p. 148.

32. V 46. T. Sasaki and T. Takeshima: J. Info. Process. 12, pp. 371-379, 1989.

33. H Kobayashi, S. Moritsugu and P. W. Hogan: ISSAC-88, K1-K5.

34. Moritsugui Doctoral Thesis at the University of Tokyo, 1989, K2-K5.

35. P. Van Hentenryck, D. McAllester and D. Kapur: Solving Polynomial Systems Using a Branch and Prune Approach. SIAM J. Numerical Analysis, Vol. 34, No. 2, pp 797-827, 1997.

36. H. Hong and V. Stahl: Safe Starting Regions by Fixed Points and Tightening ^ Computing 53(3-4): 322-335, 1995.5L К W. Noonburg: A neural network modeled by an adaptive Lotka-Volterra system. SIAMJ.Appl. Math., Vol. 49, No. 6, 1779-1792, 1989.

37. Jan Verschelde and Ann Haegemans:'The GBQ-Algorithm for constructing start systems of homotopies for polynomial systems. SIAM J. Numer. Anal, Vol. 30, No. 2, pp 583-594, 1993.

38. B. Mourrain: The 40 generic positions of a parallel robot. M. Bronstein, editor, ISSAC'93, ACM Press, pages 173-182, Kiev (Ukraine), 1993.

39. Bosma W., Cannon J., Play oust C.: The Magma algebra system I: The user language. J. Symb. Сотр., 24(3/4):235-265,1997.

40. Singh, V., Biswas, S. N., Datta, K.: Anharmonic oscillator and the analytic theory of continued fractions. Phys. Rev. D 18 (1978) 1901 1908.

41. Magyari, E.: Exact quantum-mechanical solutions for anharmonic oscillators, Phys. Lett. A 81 (1981) 116 118.

42. Znojil, M.: Elementary bound states for the power-law potentials. J. Phys. Ai Math. Gen. 15 (1982) 2111 2122.

43. Znojil, M.: Quasi-exact states in the Lanczos recurrent picture. Phys. Lett. A 161 (1991) 191 196;

44. Fliigge, S.: Practical quantum mechanics I. Springer, Berlin, 1971, p. 168;

45. Abramowitz, M., Stegun, I. A.: Handbook of Mathematical Functions. Dover, New York, 1970.

46. Ushveridze, A. G.: Quasi-Exactly Solvable Models in Quantum Mechanics. IOPP, Bristol, 1994.

47. Znojil, M., Leach, P. G. L.: On the elementary Schrodinger bound states and their multiplets. J. Math. Phys. 33 (1992) 2785 2794.

48. Znojil, M.: Classification of oscillators in the Hessenberg matrix representation. J. Phys. A: Math. Gen. 27 (1994) 4945 4968.

49. Znojil, M.: Generalized Rayleigh-Schrodinger perturbation theory as a method of linearization of the so called quasi-exactly solvable models. Proc. Inst. Math. NAS (Ukraine) 43 (2002) 777-788.

50. Znojil, M., Yanovich, D., Gerdt, К P.; New exact solutions for polynomial oscillators in large dimensions. J. Phys. A: Math. Gen., (36) pp.6531-6549, 2003 (LANL arXiv math-ph/0302046).

51. ВЛ: Гердт, Ю.А: Блинков, Д.А. Янович: БЫСТРЫЙ ПОИСК ДЕЛИТЕЛЯ ЖАНЕ. Программирование, том 27, № 1, 2001, стр.22-24.

52. Gerdt, V.Р., Yanovich, D.A.: Parallelism in Computing Janet Bases. In: Proceedings of СААР'01 (June 28-30, 2001, Dubna, Russia)

53. АЛ. Гусев, В.Н.Самойлов, В.А. Ростовцев, С.И. Виницкий: Алгебраическая теория возмущений для атома водорода в слабых электрических полях. Программирование 1, 27-31 (2001).

54. Ye.M. Hakobyan, S.I. Vinitsky, G.S. Pogosyan, A.N.Sissakian: Isotropic oscillator in a space of constant positive Curvature: Interbasis expansion. Physics of Atomic Nuclei, v.62, N 4,p.623-637, 1999.