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

• Янович, Денис Александрович
• кандидат физико-математических наук
• 2003

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

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. Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Янович, Денис Александрович, 2003 год

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.