Система программ для исследования комбинаторно-алгебраических инвариантов топологических объектов малой размерности тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Каишев, Андрей Игоревич

• Каишев, Андрей Игоревич
• кандидат физико-математических наук
• 2000

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

1 Комбинаторные объекты, связанные с инвариантами Васильева

1.1 Особые узлы и фильтрация Васильева.

1.2 Инварианты узлов

1.3 Алгебра хордовых диаграмм.

1.4 Алгебра диаграмм Фейнмана.

1.5 Алгебра 3-графов.

1.5.1 Умножение

1.5.2 Некоторые тождества.

1.5.3 Связные диаграммы Фейнмана и 3-графы.

2 Весовые системы со значениями в центре универсальной обертывающей алгебры

2.1 Универсальные обертывающие алгебры.

2.2 Алгоритм построения образующих центра.

2.3 Каноническое представление простых алгебр Ли.

2.3.1 Представление алгебр серии А.

2.3.2 Представление алгебр серии В.

2.3.3 Представление алгебр серии С.

2.3.4 Представление алгебр серии Б.

2.3.5 Представление алгебры С2.

2.4 Система программ для вычисления значений весовых систем

2.4.1 Реализация алгоритма построения образующих центра.

2.4.2 Структура РСЖМ-программ.

2.4.3 Вычисление значений весовой системы на хордовых диаграммах

2.5 Результат.

2.6 Выводы.

3 Структура алгебры 3-графов

3.1 Составление списка графов.

3.2 Выражение графов через образующие.

3.3 Вычисления.

3.4 Результаты.;

3.5 Выводы.

Алгебра 3-графов и алгебры Ли

4.1 Конструкция инварианта Кд.

4.2 Алгоритм вычисления и йо^-полиномов.

4.3 Переход к рекурсивному (параллельному) алгоритму.

4.4 Т-программа вычисления я/- и 5 о-полиномов.

4.5 Показатели эффективности распараллеливания Т-программы

4.6 Результат.

4.7 Выводы.

Алгебра графов Ландо

5.1 Конструкция алгебры Ландо.

5.2 Программа для вычислений в алгебре

Ландо.

5.3 Выражение графов через образующие.

5.4 Гомоморфизм алгебр 7 :£>—>■£.

5.5 Выводы.

Введение диссертации (часть автореферата) на тему «Система программ для исследования комбинаторно-алгебраических инвариантов топологических объектов малой размерности»

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

Инварианты конечного типа, введенные московским математиком В.Васильевым в 1990 году, быстро завоевали широкое признание среди специалистов по теории узлов, и в течение 10 лет в мире вышло около 500 работ, посвященных исследованию инвариантов Васильева. Оказалось, что это понятие позволяет понять с единой точки зрения многие конструкции, введенные в топологии за последние 50 лет. В принципе, существует алгоритм, который дает явное описание всех инвариантов Васильева, но его суперэкспоненциальная сложность не позволяет продвинуться дальше степени 7. По этой причине особое значение имеют разного рода опосредованные алгоритмы, которые позволяют находить те или иные характеристики изучаемых объектов с помощью вспомогательных структур (хордовых диаграмм, алгебр Ли, графов и т.п.). Настоящая диссертация относится как раз к этому подходу. В ней описан разработанный автором пакет программ для исследования комбинаторно-алгебраических структур, возникающих в теории инвариантов Васильева.

Краткое содержание диссертации таково.

В первой главе мы излагаем основные определения и конструкции теории инвариантов Васильева, необходимые для понимания последующего материала. Это, в частности, введенное М. Концевичем понятие весовой системы как функции на алгебре хордовых диаграмм (см. [К], [ВШ]) и введенная С. К. Ландо ([Ьа]) конструкция алгебры графов с 4-членными соотношениями. Несколько подробнее изложена конструкция алгебры 3-графов Г, введенная в статье [сок].

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

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

• составление списка графов,

• нахождение полиномов, выражающих 3-графов через образующие,

• вычисление sl^- и волг-полиномов 3-графов.

Четвертая глава посвящена вычислению полиномиальных инвариантов 3-графов, связанных с алгебрами Ли sijv и son- В первом параграфе описана восходящая к Р. Пенроузу и М. Концевичу конструкцию, позволяющую по алгебре Ли 0 с заданной невырожденной ad-инвариантной билинейной формой В построить функцию Kg на множестве 3-графов, порождающую гомоморфизм алгебр Г —> R

Параграф 4.2 посвящен реализация алгоритма вычисления si- и so-полиномов. В тексте приведена соответствующая программа 1 на псевдокоде.

В параграфе 4.3 изложена параллельная версия алгоритма и ее реализация на языке t2cp в рамках системы автоматического динамического распараллеливания программ (Т-системы, [АА]).

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

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

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

• Алгоритм нахождения образующих центра универсальных обертывающих алгебр для алгебр Ли серий А, В, С, D и особой алгебры G2 (см. 2.4).

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

• Усовершенствованный алгоритм генерации полного списка трехвалентных графов с данным числом вершин (параграф 3.1).

• Разработка и реализация алгоритма выражения 3-графов через образующие (см. параграф 3.2). Существенной его частью является алгоритм точного решения систем линейных уравнений специального вида (3.6), который позволил обрабатывать системы из десятков тысяч уравнений.

• В результате работы описанного программного комплекса найден линейный базис алгебры 3-графов и система мультипликативных образующих до градуировки 10. Эти значения приведены в таблицах 3.1 и 3.2. Имеющиеся в этих таблицах значения градуировки 11 получены в результате работы программ, рассматриваемых в следующей главе.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Каишев, Андрей Игоревич

5 Выводы

Основными результатами настоящей главы являются:

• Разработка и реализация алгоритма нахождения образующих алгебры Ландо и выражения элементов этой алгебры через образующие.

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

• Установлено, что естественный гомоморфизм из алгебры хордовых диаграмм в алгебру Ландо является изоморфизмом до градуировки б, а в градуировке 7 представляет собой эпиморфизм с одномерным ядром.

Список литературы диссертационного исследования кандидат физико-математических наук Каишев, Андрей Игоревич, 2000 год

1. Al. J. W. Alexander, Topological invariants of knots and links. Trans. Amer. Math. Soc. 30, (1928), 275-306.

2. A. V. I. Arnold, Vassiliev's theory of discriminants and knots, Plenary lecture at the first European Congress of Mathematicians, Paris, July 1992.

3. BN1. D. Bar-Natan, On the Vassiliev knot invariants, Topology, 34 (1995) 423472.

4. BN2. D. Bar-Natan, Lie algebras and the four color theorem, Arhus University preprint, August 1995, and q-alg/9606016 preprint, June 1996. To appear in Combinatorica.

5. BN3. D. Bar-Natan, Some computations related to Vassiliev invariants. http://www.ma.huj i.ac.il/ drorbn/papers/table.dvi.

6. BN4. D. Bar-Natan, Bibliography of Vassiliev Invariants. Web publication http://www.ma.huj i.ac.il/ drorbn/VasBib/VasBib.html.

7. BG. D. Bar-Natan, S. Garoufalidis, On the Melvin-Morton-Rozansky conjecture Invent. Math. 125 (1996) 103-133.

8. B. J. Birman, New points of view in knot theory, Bull. Amer. Math. Soc. 28, (1993), 253-287.

9. BL. J. Birman and X.-S.Lin, Knot polynomials and Vassiliev invariants, Invent. Math. Ill, (1993), 225-270.

10. BDM. B. McKay, Nauty: a program for computing automorphism groups of graphs, http://cs.anu.edu.au/people/bdm/nauty/.

11. Bou. H. Бурбаки, Группы и алгебры Ли. Главы 1-3. М.: Мир, 1976. Главы 4-6. М.: Мир, 1972. Главы 7-8. М.: Мир, 1978.

12. CD1. S. V. Chmutov, S. V. Duzhin, An upper bound for the number of Vassiliev knot invariants, Journal of Knot Theory and its Ramifications, 3 (1994) 141-151.

13. CD2. S. V. Chmutov, S. V. Duzhin, A lower bound for the number of Fas-siliev knot invariants, Preprint, 21 pp., available as PostScript file at ftp://pier.botik.ru:/pub/local/zmr/lb.ps.gz.

14. CD3. S. Chmutov, S. Duzhin, The Kontsevich integral. Preprint of MaxPlanck-Institut für Mathematik (Bonn, August 1997); 27 pp., available as PostScript file at ftp://pier.botik.ru:/pub/local/zmr/ki.ps.gz.

15. CDK. С. В. Дужин, А. И. Каишев, С. В. Чмутов, Алгебра 3-графов. Труды Математического Института им. Стеклова РАН, т. 221, 1998 г. 168-196

16. CDU. S. V. Chmutov, S. V. Duzhin, S. К. Lando, Vassiliev knot invariants I. Introduction, Advances in Soviet Math., 21 (1994) 117-126.

17. CDL2. S. V. Chmutov, S. V. Duzhin, S. K. Lando, Vassiliev knot invariants II. Intersection Graph Conjecture for Trees, Advances in Soviet Math., 21 (1994) 127-134.

18. CDL3. S. V. Chmutov, S. V. Duzhin, S. K. Lando, Vassiliev knot invariants III. Forest Algebra and Weighted Graphs, Advances in Soviet Math., 21 (1994) 135-145.

19. CV. S. Chmutov, A. Varchenko, Remarks on the Vassiliev knot invariants coming from sl2i Topology 36 (1997) 153-178.

20. C. J. H. Conway, An enumeration of knots and links and some of their algebraic properties. Computational Problems in Abstract Algebra (J.Leech, ed.), Pergamon Press, New York, 1970, 329-358.

21. Das. O. Dasbach, Private communication, July 1997.

22. DK1. С. В. Дужин, А. И. Каишев, Реализация в Т-системе программы вычисления si- и so-полиномов для 3-графов. В сб. 'Программные системы". М.: Наука 1999, стр. 214-223.

23. Ftp. А. И. Каишев, Программы и данные, расположенные на анонимном ftp-cepeepe. ftp: //math. botik. ru/pub/a3g.

24. Kal. А. И. Каишев, Координатные асимптотики решений одномерного уравнения Дирака с осциллирующим потенциалом. Математические заметки, т. 37, вып. 3, 1985 г. 345-354.

25. Ка2. А. И. Каишев, Уточненная схема построения апостериорного интервального расширения элементарной функции. Вопросы кибернетики, ВК-149. Москва, 1989 г. 14-17.

26. Kn. J. Kneissler, The number of primitive Vassiliev invariants up to degree twelve. Preprint q-alg 9706022, also available at http://rhein.iam.uni-bonn.de/ jk/, June 1996.

27. К. M. Kontsevich, Vassiliev's knot invariants, Adv. in Soviet Math., vol. 16, Part 2, pp. 137-150, 1993.

28. Коп. M. Kontsevich, Feynman diagrams and low-dimensional topology, First European Congress of Mathematics II 97-121, Birkhauser, Basel 1994.

29. MM. J. Milnor, J. Moore, On the structure of Hopf algebras, Ann. Math. 81 (1965), 211-264.

30. Pen. R. Penrose, Applications of negative dimensional tensors, In: Combinatorial mathematics and its applications (ed. D. J. A. Welsh), New York, London: Academic Press, 1971.

31. Pont. JI. С. Понтрягин, Непрерывные группы. M.: Наука. 1984

32. PS. В. В. Прасолов, А. Б. Сосинский, Узлы и маломерная топология, специальный семинар, изд-во МК НМУ, 1993.

33. Ro. D. Rolfsen, Knots and Links. Publish or Perish, 1976.

34. Cub. G. Royle. WWW-page containing tables of S-graphs, October 1996. http://www.cs.uwa.edu.au/~gordon/remote/cubics/.

35. S. A. B. Sossinsky, Feynman diagrams and Vassiliev invariants. IHES preprint, Paris, February 1992.

36. W. T. Tutte, A ring in graph theory, Proc. Cambridge Phil. Soc. 43 (1947), 26-40. Reprinted in Selected Papers of W. T. Tutte, Vol. 1, The Charles Babbage Research Center, Manitoba, Canada, 1979.

37. V. A. Vassiliev, Cohomology of knot spaces, Theory of Singularities and Its Applications (ed. V. I. Arnold), Advances in Soviet Math., 1 (1990) 23-69.

38. В.А.Васильев, Топология дополнений к дискриминантам, M., Фазис, 1997, 536 стр.

39. J. A. M. Vermaseren. Computer algebraic system FORM. User's manual. ftp.nikhef.nl:/pub/form/manual/form.dvi.

40. P. Vogel, Algebraic structures on modules of diagrams, Institut de Mathématiques de Jussieu, Prépublication 32, August 1995, 45 pages.