Построение алгоритмов компьютерной алгебры на основе методов теории функций

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

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

.

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

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

За три последних десятилетия было создано огромное число систем компьютерной алгебры, большинство из которых широко применяется в научных вычислениях, при решении прикладных проблем, в индустрии. В зависимости от набора стандартных задач, которые могут быть решены при помощи данных систем, последние подразделяются на универсальные (или, иначе, системы общего назначения, такие как MAPLE, MATHEMATICA, MAXIMA и др.) и специализированные.

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

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

Одним из наиболее эффективных инструментов для исследования таких систем является формула многомерного логарифмического вычета. Первые попытки в создании математического аппарата и алгоритмов компьютерной алгебры для исследования систем нелинейных уравнений с помощью многомерного логарифмического вычета были даны в работах В. И. Быкова, А. М. Кытманова, М. З. Лазмана, Т. А. Осетровой, З. Е. Потаповой [5−8,23,24,40]. В данных работах формула многомерного логарифмического вычета применялась для создания алгоритма исключению неизвестных из систем алгебраических уравнений. Этот модифицированный метод исключения неизвестных, предложенный Л. А. Айзенбергом в [3], был затем развит в [6,40]. Но для систем неалгебраических уравнений (содержащих, например, голоморфные функции) такие разработки отсутствовали.

Неалгебраические системы уравнений возникают в различных областях знания. В частности, в процессах, описываемых системами дифференциальных уравнений с правыми частями, разложимыми в ряд Тейлора, актуален вопрос об определении числа стационарных состояний в множествах определенного вида (и их локализации). Эта проблема приводит к задачам построения алгоритмов для определения числа корней заданной системы уравнений в разных множествах, определения самих корней, исключения части неизвестных из системы. В частности в монографиях [6, 40] приведены многочисленные примеры из химической кинетики, где работают алгоритмы исключения неизвестных.

Цель диссертации.

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

Методика исследования.

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

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

Основные результаты работы являются новыми и состоят в следующем.

1. Получены многомерные аналоги рекуррентных формул Ныотоиа для систем неалгебраических уравнений.

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

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

4. Создан аппарат для разработки алгоритмов построения интегральных представлений в полиэдрах многомерного комплексного пространства по веерам торических многообразий.

5. Получены аналоги многомерного логарифмического вычета и интегральная реализация локального вычета.

6. Выведены типовые алгоритмы компьютерной алгебры и дана их компьютерная реализация в системе компьютерной алгебры МАРЬЕ.

Теоретическая и практическая ценность.

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

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

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

Основные результаты диссертации обсуждались и докладывались на следующих международных и всероссийский конференциях: международной конференции «Симметрия и дифференциальные уравнения» (Красноярск, Россия, 2000) — международной конференции «Математические модели и методы их исследования» (Красноярск, Россия, 2001) — международной конференции «Многомерный комплексный анализ» (Красноярск, Россия, 2002) — международной конференции-школе по геометрии и анализу (Новосибирск, Россия, 2002) — международной конференции «Геометрический анализ и его приложения», (Волгоград, Россия, 2004) — международной математической конференции «Теория функций. Дифференциальные уравнения. Вычислительная математика» (Уфа, Россия, 2007) — международной конференции «Анализ и геометрия на комплексных многообразиях» (Красноярск, Россия, 2007) — школе-конференции по алгебраической геометрии для молодых математиков (Ярославль, Россия, 2008) — международной конференции «Дифференциальные уравнения. Функциональные пространства. Теория приближений» (Новосибирск, Россия, 2008).

Результаты работы докладывались на научном семинаре по компьютерной алгебре факультета вычислительной математики и кибернетики и НИИ ядерной физики имени Д. В. Скобельцына МГУ имени М. В. Ломоносова (г. Москва), научном семинаре института программных систем РАН (г. Переславль-Залесский), а также на научных семинарах института космических и информационных технологий Сибирского федерального университета (г. Красноярск).

Публикации.

Основные результаты диссертации опубликованы в работах [67−87], из них 1 монография [85], 8 работ [74,75,79−81,84,86,87] в ведущих отечественных и международных рецензируемых изданиях, рекомендованных ВАК, 12 публикаций [67−73,76−78,82,83] в других научных изданиях. Кроме того, автором получены два свидетельства о государственной регистрации программ для ЭВМ [88,89].

Личный вклад автора.

Результаты диссертации получены автором самостоятельно. В соавторстве выполнена одна работа [86], в которой вклады авторов равнозначны.

Структура и объем работы.

Диссертация состоит из введения, трех глав, приложения и списка литературы из 89 наименований, содержит 7 рисунков. Общее число страниц диссертационной работы — 228, в том числе 23 страницы — приложения.

1. Айзенберг J1.A. Интегральные представления и вычеты в многомерном комплексном анализе / Л. А. Айзенберг, А. П. Южаков. — Новосибирск: Наука, — 1979. — 366 с.

2. Айзенберг JI.A. Многомерные аналоги формул Ньютона для систем нелинейных алгебраических уравнений и некоторые их приложения / Л. А. Айзенберг, А. М. Кытманов // Сиб. матем. журн. 1981. — Т. 22. — № 2. — С. 19−30.

3. Айзенберг Л. А. Об одной формуле обобщенного многомерного логарифмического вычета и решении систем нелинейных уравнений / Л. А. Айзенберг // Докл. АН СССР. 1977. — Т. 234. — № 3. — С. 505−508.

4. Бухбергер Б. Базисы Гребнера. Алгоритмический метод в теории полиномиальных идеалов / Б. Бухбергер // Компьютерная алгебра. Символьные и алгебраические вычисления / Под ред. Бухбергсра Б., Коллинза Дж., Лооса Р. М.: Мир, — 1986. — С. 331−372.

5. Быков В. И. Компьютерная алгебра многочленов. Модифицированный метод исключения / В. И. Быков, А. М. Кытманов, Т. А. Осетрова // Докл. РАН. 1996. — Т. 350. — № 4. — С. 443−445.

6. Быков В. И. Методы исключения в компьютерной алгебре многочленов / В. И. Быков, А. М. Кытманов, М. З. Лазман. Новосибирск: Наука, — 1991. — 234 с.

7. Быков В. И. Компьютерная алгебра многочленов. Методы и приложения / В. И. Быков, А. М. Кытманов, Т. А. Осетрова // Вычислительные технологии. Сб. научных трудов. Новосибирск. — 1995. — Т. 4. № 10. С. 79−88.

8. Быков В. И. Компьютерная алгебра многочленов. Методы и приложения / В. И. Быков, А. М. Кытманов, Т. А. Осетрова // Доклады РАН. 1996. — Т. 350. — № 4. — С. 443−446.

9. Быков В. И. Применение систем компьютерной алгебры в модифицированном методе исключения неизвестных / В. И. Быков, А. М. Кытманов, Т. А. Осетрова, З. Е. Потапова // Докл. РАН. 2000. Т. 370. № 4. — С. 439−442.

10. Ван дер Варден Б. Л. Современная алгебра / Б. Л. Ван дер Варден. -М.-Л.: ОГИЗ, 1947.

11. Ван дер Варден Б. Л. Алгебра / Б. Л. Ван дер Варден. М.: Наука, -1976. — 649 с.

12. Гамелин Т. Равномерные алгебры / Т.Гамелин. М.: Мир, — 1973. -334 с.

13. Гриффите Ф. Принципы алгебраической геометрии. / Ф. Гриффите, Дж.Харрис. М.: Мир, — 1982. — 860 с.

14. Дольбо Д. Общая теория многомерных вычетов / Д. Дольбо // Итоги науки и техники. Современные проблемы математики (фундаментальные направления). М.: ВИНИТИ. — 1985. — Т. 7. — С. 227−251.

15. Дэвенпорт Дж. Компьютерная алгебра / Дж. Дэвенпорт, И. Сирэ, Э.Турнье. М.: Мир, — 1991.

16. Ермилов И. В. Вычисление сумм и улучшение сходимости числовых рядов / И. В. Ермилов // Исследования по комплексному анализу. -Красноярск: КрасГУ. 1989. — С. 42−52.

17. Ефимов Г. Б. Компьютерная алгебра в ИПМ им. М. В. Келдыша / Г. Б. Ефимов, Е. Ю. Зуева, И. Б. Щенков // Матем. моделирование. -2001. Т. 13. — № 6. — С. 11−18.

18. Качаева Т. И. О нахождении сумм некоторых кратных рядов / Т. И. Качаева // Вестник КрасГУ Сер. физ.-мат. науки. Красноярск, — 2004. Вып. 1. — С. 105−109.

19. Клименко В. П. Особенности структуры данных и их преобразования в системе компьютерной алгебры АНАЛИТИК / В. П. Клименко, Ю. С. Фишман, Т. Н. Швалюк // Математические машины и системы.- 2004. № 2. — С. 42−48.

20. Куприков A.B. О логарифмическом вычете / А. В. Куприков, А. П. Южаков //В кн.: «Некоторые свойства голоморфных функций многих комплексных переменных». Красноярск, ИФ СО АН СССР.- 1973. С. 181−191.

21. Курош А. Г. Курс высшей алгебры / А. Г. Курош. М.: Наука, — 1971.

22. Кытманов A.M. Интеграл Бохнера-Мартинелли и его применения / А. М. Кытманов. Новосибирск: Наука, — 1992. — 240 с.

23. Кытманов A.M. Формулы для нахождения степенных сумм корней систем мероморфных функций / А. М. Кытманов, З. Е. Потапова // Изв. вузов. 2005. — № 8 (519). — С. 39−48.

24. Осетрова Т. А. MAPLE-процедуры для нахождения результантов систем нелинейных алгебраических уравнений / Т. А. Осетрова // Комплексный анализ и дифференциальные уравнения. Межвузовский сб. — Красноярск: КрасГУ. — 1996. — С. 164−175.

25. Прудников А. П. Интегралы и ряды. Элементарные функции / А. П. Прудников, Ю. А. Брычков, О. И. Маричев. М.: Наука, — 1981. — 800 с.

26. Хенкин Г. М. Метод интегральных представлений в комплексном анализе / Г. М. Хенкин // Современные проблемы математики. Фундаментальные направления. (Итоги науки и техники). М.: ВИНИТИ. 1985. — Т. 7. — С. 23−124.

27. Цих А. К. Интегральные реализации вычета Гротендика и его преобразование при композициях / А. К. Цих, Б. А. Шаимкулов // Вестник КрасГУ. Серия физ.-мат. науки. Красноярск. — 2005 — № 1. — С. 151−155.

28. Цих А. К. Многомерные вычеты и их применения / А. К. Цих. Новосибирск: Наука, — 1988. — 241 с.

29. Шабат Б. В.

Введение

в комплексный анализ. 4.2. Функции нескольких переменных / Б. В. Шабат. М.: Наука, — 1985. — 400 с.

30. Шабат Б. В. Распределение значений голоморфных отображений / Б. В. Шабат. М.: Наука, — 1982. — 288 с.

31. Шафаревич И. Р. Основы алгебраической геометрии / И. Р. Шафаревич. М: Наука, — 1979.

32. Adams W.W. An introduction to Grocbncr Bases / W.W.Adams, P.Loustraunau. American Mathematical Society. — 1994. — 289 p.

33. Atiyah M.F. Convexity and commuting Hamiltonians / M.F.Atiyah // Bull. Lond. Math. Soc. 1982. — V. 14. — P. 1−15.

34. Atiyah M.F. Angular momentum, convex polyhedra and algebraic geometry / M.F.Atiyah // Proc. of the Edinburgh Math. Soc. 1983. -V. 26. — P. 121−138.

35. Audin M. The Topology of Torus Actions on Symplectic Manifolds / M.Audin. Progress in Math. 93. Birkhauser: Boston-Basel-Berlin. -1991. — 181 p.

36. Bajaj C. On the application of multi-equational resultants / C. Bajaj, T. Garrity, J. Warren // Tecnical Report CSD-TR-826, Departament of Computer Science. Purdue University. — 1988.

37. Batyrev V. Quantum cohomology rings of toric manifolds / V. Batyrev // Journees de Geometrie Algebrique d’Orsay (Juillet 1992), Asterisque 218, Societe Mathematique de France, Paris. 1993. — P. 9−34.

38. Batyrev V. Toric residues and mirror symmetry / V. Batyrev, E. Materov // Moscow math, journal. 2002. — V. 2. — № 3. — P. 435−475.

39. Bochner S. Analytic and meromorphic continuation by means of Green’s formula / S. Bochner // Ann. Math. 1943. — V. 44. — P. 652−673.

40. Bykov V.I. Elimination methods in polynomial computer algebra / V.I.Bykov, A. M Kytmanov, M.Z.Lazman. Dodrecht-Boston-Basel: Kluwer Academic Publishers, — 1998.

41. Cattani E. Computing Multidimensional Residues / E. Cattani, A. Dickenstein, B. Sturmfels // Basel: Birkhauser. Prog. Math. 1996. -V. 143. — P. 135−164.

42. Char B. MapleV Library Reference Manual / B. Char, K. Geddes et allSpringer Verlag: Berlin, New York. 1991.

43. Char B. MapleV Language Reference Manual / B. Char, K. Geddes et all. Springer Verlag: Berlin, New York. — 1991.

44. Char B. MapleV First Leaves: A Tutorial Introduction / B. Char, K.Geddes. Springer Verlag: Berlin, New York. — 1991.

45. Cox D. The homogeneous coordinate ring of a toric variety / D. Cox // J. Algebraic Geom. 1995. — V. 4. — P. 17−50.

46. Cox D. Toric residues / D. Cox // Ark. Mat. 1996. V. 34. P. 73−96.

47. Cox D. Recent Developments in Toric geometry / D. Cox // Providence, RI: American Mathematical Society. Proc. Symp. Pure Math. 1997. -V. 62 — P. 389−436.

48. Dwilewicz R. Additive Riemann-Hilbert problem in line bundles over CP1 / R. Dwilewicz // Can. Math. Bull. 2006. — V. 49. — No. 1. — P. 72−81.

49. Fulton W. Introduction to Toric Varieties / W.Fulton. Princeton U. Press. Princeton, NJ. — 1993. — 157 p.

50. Gelfand I.M. Discriminants, resultants and multidimensional determinants / I.M.Gelfand, M.M.Kapranov, A.V.Zelevinsky. -Mathematics: Theory & Applications. Birkhauser Boston Inc., Boston, MA. 1994. — 523 p.

51. Guillemin V. Moment Maps and Combinatorial Invariants of Hamiltonian Tn-spaces / V.Guillemin. Progress in Math. V. 122. Birkhauser: Boston Basel Berlin. 1994. — 150 p.

52. Guillemin V. Convexity properties of the moment mapping / V. Guillemin, S. Sternberg // Invent. Math. 1982. -V. 67. — P. 491−513.

53. Lazard D. Groebner bases, Gaussian elimination and resolution of systems of algebraic equations / D. Lazard // Lect. Notes Comput. Sci. 1983. — V. 162. — P. 146−156.

54. Macauley F.S. Algebraic theory of modular systems / F.S.Macauley. -Cambridge. 1916.

55. Manocha D. MultiPolynomial Resultant Algorithms / D. Manocha, J.F.Canny // J. Symbolic Computation. 1993. — № 15. — P. 99−122.

56. Manocha D. Multipolynomial resultant algorithms and linear algebra / D. Manocha, J.F.Canny // In Proceedings of International Symposium on Symbolic and Algebraic Computation. 1992. — P. 232−241.

57. Martinelli E. Alcuni teoremi integral! per le funzioni analitiche di piu variabili complesse / E. Martinelli // Mem. R. Accad. Ital. 1938. — V. 9. — P. 269−283.

58. Moller H.M. The construction of multivariate polynomials with preassiqued zeros / H.M.Moller, B. Buchbcrger // Lect. Notes Comput. Sei. 1983. — V. 162. — P. 24−31.

59. Moses J. Solution of Systems of Polynomial Equation by Elimination / J. Moses // Commun. of the ACM. 1966. — V. 9. — № 8. — P. 634−637.

60. Oda T. Convex Bodies and Algebraic Geometry / T.Oda. SpringerVerlag. Berlin Heidelberg New York. — 1988. — 212 p.

61. Passare M. Residue currents of the Bochner-Martinelli type / M. Passare, A. Tsikh, A. Yger // Publicacions Matematiques. 2000. — V. 44. — P. 85−117.

62. Poincare H. Sur les residues des integrales doubles / H. Poincare // Acta Math. 1887. — V. 9. — P. 312−380.

63. Shchuplev A.V. Residual kernels with singularities on coordinate planes / A.V.Shchuplev, A.K.Tsikh, A. Yger // Proc. of the Steklov Inst, of Math. 2006. — V. 253. — P. 256—274.

64. Shchuplev A.V. Toric varieties and residues / A.V.Shchuplev. Doctoral thesis. — Stockholm Univ., Department of Math. — 2007. — 70 p.

65. Tong T.L. Integral representation formulae and Grothendieck residue symbol / T.L.Tong // Amer. J. Math. 1973. — V. 4. — P. 904−917.

66. Winkler F. An algorithm for constructing canonical bases of polynomial ideals / F. Winkler, B. Buchberger, F. Lichtenberger, H. Rolleeetschk // ACM Trans. Math. Software. 1985. — V. 11. — № 1. — P. 66−78.

67. Кытманов A.A. Формы объема для некоторых торических многообразий / А. А. Кытманов // Тр. межд. конф. «Математические модели и методы их исследования». Красноярск: ИВМ СО РАН. — 2001. -Т. 2. — С. 52−55.

68. Кытманов A.A. Об аналоге ядра Бохнера-Мартинелли для одного торического многообразия / А. А. Кытманов // Сб. научн. тр. «Вопросы математического анализа». Красноярск: КрасГТУ, — 2002. — Вып. 5. — С. 48−53.

69. Кытманов A.A. Об одном интегральном представлении в С5 / A.A.Кытманов // Сб. научн. тр. «Многомерный комплексный анализ». Красноярск: КрасГУ. — 2002. — С. 79−89.

70. Кытманов A.A. Об одном классе интегральных представлений в областях пространства Cd / А. А. Кытманов // Материалы XL международной научной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ. — 2002. -С. 74−75.

71. Кытманов A.A. Об интегральном представлении, связанном с тори-ческим многообразием, которое определяется невыпуклым веером / A.A.Кытманов // Тез. межд. конф. «Многомерный комплексный анализ». Красноярск: КрасГУ. — 2002. — С. 22−23.

72. Кытманов A.A. Об одном классе интегральных представлений в полиэдрах пространства Cd / A.A.Кытманов // Тез. межд. конф,-школы по геометрии и анализу. Новосибирск: Институт математики СО РАН. — 2002. — С. 54.

73. Кытманов A.A. Об одном интегральном представлении, ассоциированном с торическим многообразием, заданным с помощью невыпуклого веера / А. А. Кытманов // Сб. научн. тр. «Вопросы математического анализа». Красноярск: КрасГТУ. — 2003. — Вып. б. — С. 124−133.

74. Кытманов A.A. Об аналоге формы Фубини-Штуди для двумерных торических многообразий / A.A.Кытманов // Сиб. матем. журн. -2003. Т. 44. — № 2. — С. 358−371.

75. Кытманов A.A. О ядрах интегральных представлений как усреднениях формул Коши / А. А. Кытманов // Вестник КрасГУ. Сер. физ.-мат. науки. Красноярск, — 2003. — Вып. 2. — С. 3−9.

76. Кытманов A.A. О построении формы объема для торических многообразий / А. А. Кытманов // Материалы XLI международной научной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ. — 2003. — С. 46−47.

77. Кытманов A.A. Конструирование ядер интегральных представлений с помощью торических многообразий / А. А. Кытманов // Тезисы межд. школы-конф. «Геометрический анализ и его прил.» -Волгоград: ВолГУ 2004. — С. 107−109.

78. Кытманов A.A. Об одном аналоге формы Фубини-Штуди для торических многообразий / А. А. Кытманов // Сб. научн. тр. «Вопросы математического анализа». Красноярск: КрасГТУ. — 2004. — Вып. 8. — С. 72−84.

79. Кытманов A.A. Об аналоге представления Бохнера-Мартинелли в d-круговых полиэдрах пространства С1/ А. А. Кытманов // Изв. вузов. Математика. 2005. — № 3. (514). — С. 52−58.

80. Кытманов A.A. Вычисление групп когомологий гладких некомпактных двумерных торических многообразий / A.A.Кытманов // Вестник КрасГУ. Сер. физ.-мат. науки. Красноярск, — 2005. — Вып. 1. — С. 103−105.

81. Кытманов A.A. О некоторых обобщениях рекуррентных формул Ньютона / А. А. Кытманов // Вестник КрасГУ. Сер. физ.-мат. науки. Красноярск, — 2006. — Вып. 9. — С. 85−91.

82. Кытманов A.A. Об аналогах рекуррентных формул Ньютона для систем нелинейных уравнений / А. А. Кытманов // Уфимская межд. матем. конф. Уфа: Институт математики с выч. центром УНЦ РАН. — 2007. — Т. 2. — С. 30−31.

83. Kytmanov A.A. Integral representations and volume forms on Hirzebruch surfaces / A.A.Kytmanov // Журнал СФУ. Сер. мат. и физ. Красноярск. — 2008. — Вып. 2. — С. 125−132.

84. Кытманов A.A. Об аналогах рекуррентных формул Ныотоиа / А. А. Кытманов // Изв. вузов. Математика. 2009. — № 10. — С. 40−50.

85. Kytmanov A.A. Toric Varieties in Several Complex Variables / A.A.Kytmanov. LAP Lambert Academic Publishing. 2009. — 100 p.

86. Kytmanov A.A. Averaging of the Cauchy kernels and integral realization of the local residue / A. A. Kytmanov, A.Y. Semusheva // Mathematische Zeitschrift. 2010. — V. 264. — № 1. — P. 87−98.

87. Кытманов A.A. Алгоритм вычисления степенных сумм корней для класса систем нелинейных уравнений / А. А. Кытманов // Программирование. 2010. — № 2.'- С. 55−63.