Вычисление характеристических полиномов плотных матриц: последовательные и параллельные алгоритмы тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Переславцева, Оксана Николаевна

• Переславцева, Оксана Николаевна
• кандидат физико-математических наук
• 2012

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

Введение.

1 Методы вычисления характеристических полиномов в коммутативных областях

1.1. Метод Леверье.

1.2. Метод Леверье-Фаддеева

1.3. Метод Чистова.

1.4. Алгоритм Берковича.

1.5. Алгоритм Ссйфуллина.

1.6. Алгоритм Малашонка.

1.7. Новый алгоритм.

1.8. Выводы.

2 Алгоритмы вычисления характеристических полиномов матриц в кольце целых чисел и в кольце полиномов с целыми коэффициентами

2.1. Сложность алгоритмов, выраженная в числе машинных операций

2.1.1. Метод Леверье.

2.1.2. Метод Леверье-Винограда

2.1.3. Алгоритм Леверье-Фаддеева.

2.1.4. Алгоритм Чистова.

2.1.5. Алгоритм Берковича.

2.1.6. Алгоритм Сейфуллина.

2.1.7. Алгоритм Малашонка и новый алгоритм.

2.2. Метод Данилевского.

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

2.4. Экспериментальное сравнение алгоритмов в кольце целых чисел

2.5. Вычисление характеристических полиномов полиномиальных матриц.

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

2.5.2. Оценка коэффициентов характеристического полинома полиномиальной матрицы.

2.5.3. Алгоритм, основанный на методе гомоморфных образов, который в конечном поле использует алгоритм Данилевского

2.5.4. Вычислительные эксперименты.

2.6. Выводы.

3 Параллельные алгоритмы вычисления характеристических полиномов

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

3.1.1. Алгоритм.

3.1.2. Результаты экспериментов.

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

3.2.1. Схема передачи данных.

3.2.2. Алгоритм вычисления характеристического полинома полиномиальной матрицы.

3.2.3. Пример в кольце полиномов от двух переменных.

3.2.4. Эксперименты

3.3. Параллельный алгоритм вычисления характеристического полинома с восстановлением на листовых вершинах.

3.3.1. Алгоритм.

3.3.2. Время вычисления характеристического полинома

3.3.3. Эксперименты

3.4. Выводы.

Введение диссертации (часть автореферата) на тему «Вычисление характеристических полиномов плотных матриц: последовательные и параллельные алгоритмы»

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

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

Характеристические полиномы матриц впервые появляются в трудах Лапласа, Якоби и Леверье. За прошедшие полтора столетия они нашли приложения в самых разных теоретических и прикладных областях — в теории матриц [1], в тер и и представлений групп [2], в механике [3|, в астрономии [4|, в физике, химии, биологии, во многих технических задачах, в теории управления [5].

Один из первых методов вычисления характеристических полипомов матриц в коммутативном кольце предложил в 1881 г. Леверье. Видоизменение этого метода, предложенное в 1943 г. Фаддсевым Д.К. [6], позволило вычислять одновременно еще и присоединенную матрицу. Алгоритм Леверье (с улучшением Винограда [7]) требует выполнения ~ 4п35 кольцевых операций, алгоритм Фаддеева - ~ 2тг4 кольцевых операций при вычислении характеристического полинома матрицы размера п х п. В основе алгоритмов лежит вычисление произведения матриц. Это позволяет для распараллеливания этих алгоритмов использовать параллельное умножение матриц.

Отметим недавно полученные алгоритмы для коммутативных областей. Алгоритм Сейфуллина [8] (2002) требует кольцевых операций ~ 1/2п1. Алгоритм Малашоика [10] (1999) и новый алгоритм [11] (2008), который предложен автором, требуют, соответственно, ~ 8/3п3 и ~ 7/3?г3 кольцевых операций.

В работе Икрамова Х.Д. [12] как наиболее эффективный способ точного вычисления характеристического многочлена матриц над конечными полями рекомендуется метод Данилевского [13] (1937), который требует выполнения ~ 2п3 операций. Асимптотически лучшими последовательными алгоритмами для вычисления характеристического полинома в конечном поле являются алгоритм Келлер-Гехрига [14] (1985) и вероятностный алгоритм Пернета-Сторьоханпа [15] (2007), которые требуют выполнения 0(пш \0g2n) и 0(пш) операций соответственно. Здесь ©(п^) обозначает сложность матричного умножения.

После публикации [16, 17, 18, 19] в российских научных изданиях работ автора, в которых предлагаются новые алгоритмы и методы расспараллели-вания алгоритмов вычисления характеристических полипимов, появился ряд статей по этой же теме других авторов. Так японские математики К. Kumura и H. Anai [20j предлагают алгоритм вычисления определителя с использованием модулярной арифметики. Они приводят результаты экспериментов на 2-х процессорном компьютере и демонстрируют ускорение по сравнению с системами Maple 13 и Mathematica 6.

Французские математики Ф. Обри и А. Валибуз [21j предложили параллельный алгоритм вычисления резольвенты Лагранжа для полинома одной переменной с использованием техники модулярных вычислений. Они получили формулу для разложения резольвент, которая позволяет строить параллельные алгоритмы с двумя уровнями распараллеливания. В работе других французских авторов J.-G. Dumas, Th. Gautier и J.-L. Roch [22j описывается схема распараллеливания алгоритмов вычисления определителя и характеристического полинома матриц с применением модулярных вычислений.

Цель работы.

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

Задачи работы.

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

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

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

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

• Требуется провести экспериментальное исследование эффективности полученных алгоритмов и программ.

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

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

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

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

Разработаны и исследованы новые параллельные алгоритмы и программы для вычисления характеристических полиномов матриц в кольце целых чисел и в кольце полиномов с целыми коэффициентами. Практическая ценность.

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

Результаты исследований докладывались на 18 конференциях и многих научных семинарах:

- Международная научная конференция Parallel Computer Algebra (РагСА'2010) (Тамбов, 29 июня - 3 июля 2010),

- Международная научная конференция "Современное математическое образование и проблемы истории и методологии математики" (Тамбов, 2006, 2008),

- International Conference Polynomial Computer Algebra (Санкт-Петербург, 4-7 апреля 2008, 8-12 апреля 2009, 2-7 апреля 2010, 17-22 апреля 2011, 23-28 апреля 2012),

- Международная научная конференция ПаВТ'2009 (Нижний Новгород, 30 марта - 3 апреля 2009),

- Международная научная конференция Mathematical Modeling and Computational Physics (MMCP'2009) (Dubna, July 7-11, 2009),

- Международная научная конференция Колмогоровские чтения. Общие проблемы управления и их приложения (ОПУ-2009) (Тамбов 5-9 октября 2009),

- Дсржавинские чтения (Тамбов, 2005-2012),

- семинар «Компьютерная алгебра» факультета ВМК МГУ и ВЦ РАН,

- научные семинары в Тамбовском государственном университете.

Публикации автора. Основные результаты диссертации опубликованы в 20 научных работах автора (все работы без соавторов, из них 10 работ опубликованы в журналах, которые входят в список журналов, рекомендованных ВАК РФ) и двух учебных пособиях, в которых автором написаны отдельные главы.

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

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

3.4. Выводы

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

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

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

Даны рекомендации по использованию вычислительного кластера для вычисления характеристических полиномов в зависимости от размера матрицы и характера ее коэффициентов.

Заключение данной работе получены следующие результаты:

Проведено уточненное исследование сложности известных последовательных алгоритмов вычисления характеристических полипомов плотных матриц в коммутативном кольце. Найдены выражения для количества кольцевых операций. Для кольца целых чисел получены оценки сложности в количестве операций над машинными словами. Исследованные алгоритмы программно реализованы. Результаты экспериментов хорошо согласуются с полученными теоретическими оценками сложности алгоритмов.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Переславцева, Оксана Николаевна, 2012 год

1. Гантмахер Ф.Р. Теория матриц. — М.: Наука, 1988.

2. Виленкин Н.Я. Специальные функции и теория представлений групп. М.: Наука, 1991.

3. Крылов А.Н. О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем. Собрание сочинений, т.5. 1937.

4. Le Verrier U.J.J. Sur les variations séculaires des elements elliptiques des sept planétes principales: Mercure, Venus, La Terre, Mars, Jupiter, Saturne et, Uranus // Journal de Mathématiques Purés et Appliquees. 1840. N4. 220254.

5. Воронов B.C. Показатели устойчивости и качества робастных систем управления. Изв. РАН. Теория и системы управления. 1995. N6. 49-54.

6. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М., JL: Гос. изд. физ. мат. литературы, 1963.

7. Кнут Д. Искусство программирования для ЭВМ. Т.2. М.: Мир, 1977.

8. Сейфуллин Т.Р. Вычисление определителя, присоединённой матрицы и характеристического полинома без деления // Кибернетика и системный анализ.2002. N.5. С.18-42.

9. Seifullin T.R. Acceleration of computation of determinants and characteristic polynomials without divisions // Cybernetics and Systems Analysis. 2003. Vol. 39, N. 6. P. 805-815.

10. Малашонок Г.И. A computation of the characteristic polynomial of an endomorphism of a free module // Записки научных семинаров ПО-МИ.1999. Т. 258. С. 101-114.

11. Переславцева О.Н. Метод вычисления характеристического полинома матрицы // Вестник Тамбовского Университета. Серия: Естественные и технические науки. 2008 Т. 13. Вып.1. С.131-133.

12. Икрамов Х.Д. О конечных спектральных процедурах в линейной алгебре // Программирование. 1994. № 1. 56-69

13. Данилевский A.M. О численном решении векового уравнения // Ма-тем. сб. 1937. Т.2(44). N1. 169-172.

14. Keller-Gehrig W. Fast algorithms for the characteristic polynomial//Theoretical computer science. 1985. V. 36. P. 309-317.

15. Pernet C., Storjohann A. Faster algorithms for the characteristic polynomial // ISSAC. 2007. P. 307-314.

16. Переславцева О.Н. О вычислении коэффициентов характеристического полинома // Вычислительные методы и программирование. 2008. Т.9. С. 366-370 (http://num-meth.srcc.msu.ru/).

17. Переславцева О.Н. Вычисление характеристических полиномов матриц в кольце полиномов // International Conference Polynomial Computer Algebra. С.-Петербург. 2009. 35-39.

18. Переславцева О.Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках // Вестник Тамбовского Университета. Серия: Естественные и технические науки. 2009 - Т. 14. - Вып.4. -С.779-781.

19. Kumura К., Anai Н. Parallel computation of determinants of matrices with polynomial entries for robust control design // PASCO 2010 : Parallel Symbolic Computation'10. P 173-174. 21-23 July, Grenoble, France.

20. Philippe Aubry, Annick Valibouze Parallel computation of Lagrange resolvents by multi-resolvents // Tambov University Reports. Series: Natural and Technical Sciences. V. 15. Issue 4, 2010. P. 1328-1341.

21. J.-G. Dumas, Th. Gautier, J.-L. Roch Gcneric design of Chinese remaindering schemes // PASCO 2010 : Parallel Symbolic Computation'10. P. 26-34. 21-23 July, Grenoble, France.

22. Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic Proc. FCT '85, Springer Lecture Notes in Computer Science 199.-1985,- P. 147-150.

23. Berkowitz S.J. On computing the determinant in small parallel time using a small number of processors // Information Processing Letters. 1984. 18. 147-150.

24. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, V.13, p. 354-356.

25. Сейфуллин T.P. Ускорение вычисления определителя и характеристического полипома без деления // Кибернетика и системный аиализ,-2003.- N.6.- С.32-45.

26. Малашонок Г.И. Матричные методы вычислений в коммутативных кольцах Тамбов: Изд-во ТГУ, 2002.

27. Компьютерная алгебра: Символьные и алгебраические вычисления: Пер. с англ./ Под ред. Б. Бухбергера, Дж. Коллинза, P. Jlooca. М.: Мир, 1986.

28. Переславцева О.Н. Вычислительные эксперименты с алгоритмами вычисления характеристических полиномов матриц // Вестник Тамбовского Университета. Серия: Естественные и технические науки. 2007 -Т. 12. - Вып.1. - С.126-128.

29. Переславцева О.Н. Вычисление характеристического полипома в кольце целых чисел // International Conference Polynomial Computer Algebra. С.-Петербург. 2008. 57-61.

30. Dumas J.-G., Pernet C., Wan Z. Efficient Computation of the Characteristic Polynomial // ISSAC'05, July 24-27, 2005, Beijing, China.

31. MPI: A Message-Passing Interface Standard. Version 2.2. Message Passing Interface Forum. September 4, 2009. http://www.mpi-forum.org/docs/docs.html

32. G.I. Malaschonok ParCA2: Arcitecture and Experiments. Mathematical Modeling and Computation Physics (MMCP'2009): Book of Abstracts of the International Conference (Dubna, July 7-11, 2009). Dubna: JINR, 2009. P. 175.

33. Переславцева О.H. Оценка числа бит-умножений в алгоритмах вычисления определителя, характеристического полинома и присоединённой матрицы //XI Державинские чтения. Тамбов.- 2006,- С. 79-83.

34. Kaitofen Е. On Computing Determinants of Matrices Without Divisions / Proc. Internat. Symp. Symbolic Algebraic Comput. ISSAC'92. ACM Press, 1992. P. 342-349.38. www.parallel.ru39. www.open-mpi.org

35. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

36. Антонов А.С., Воеводин Вл.В. Эффективная адаптация последовательных программ для современных векторно-кон веерных и массивно-параллельных супер-ЭВМ. // Программирование. 1996, № 4, с. 37-51.

37. Jounaïdi Abdeljaoued THÈSE «Algorithmes rapides pour le Calcul du Polynôme Caractéristique». Grade de docteur de l'Université de Franche-Comté, 22 mars 1997

38. Ноутон П., Шилдт Г. Java 2. СПб: БХВ-Петербург, 2001. 1072с.

39. Фаддеев Д. К. Лекции по алгебре. М.: Наука, 1984.

40. Переславцева О.H. Об оценке коэффициентов характеристического полинома // Вестник Тамбовского Университета. Серия: Естественные и технические пауки. 2008 - Т. 13. - Вып.1. - С.124-125.

41. Крылов А.Н. Собрание трудов, Т.5 «Математика и механика». M.-JL: Изд-во АН СССР, 1937.

42. Чаплыгин С.А. Научная деятельность Алексея Николаевича Крылова // Труды физико-математического института им. В.А. Стеклова. Отдел математический. Л.: Изд-во АН СССР, 1934, Т. 5.

43. Kaltofen Е., Villard G. On the complexity of computing determinants // Proc. Fifth Asian Symposium on Computer Mathematics (ASCM 2001). P. 13-27

44. Малашонок Г.И., Аветисян А.И., Валеев Ю.Д., Зуев M.С. Параллельные алгоритмы компьютерной алгебры // Труды института системного программирования. Под. ред. В.П. Ивапникова, М.: ИСП РАН 2004 -с. 169-180.

45. Малашонок Г.И., Валеев Ю.Д. Рекурсивное распараллеливание символьно-численных алгоритмов. // Вестник Тамбовского университета, 2006, том 11, вып. 4. с. 536-549

46. Малашонок Г.И., Валеев Ю.Д., Зуев М.С. Параллельная компьютерная алгебра. Введение // Тамбов: Изд-во ТГУ им. Г.Р. Державина, 2006. 102 с.

47. Малашонок Г.И., Валеев Ю.Д., Зуев М.С. Параллельные вычисления на бинарных деревьях в задачах компьютерной алгебры. // Тамбов: Изд-во ТГУ им. Г.Р. Державина, 2006. 122 с.

48. Переславцева О.H. Об алгоритмах вычисления характеристического полинома матрицы в кольце целых чисел// Международная научная конференция «Современное математическое образование и проблемы истории и методологии математики». Тамбов. 2008. С.196-198.

49. Малашонок Г.И., Переславцева О.Н., Сажнева O.A., Старов

50. М.В. Алгоритмы компьютерной алгебры. Часть 1. Учебное пособие. Тамбов: Издательский дом ТГУ им. Г.Р. Державина, 2008.

51. Переславцева О.Н. Вычисление характеристического полинома для полиномиальных матриц // Вестник Тамбовского Университета. Серия: Естественные и технические пауки. 2009. Т. 14. Выи.1. С.274-277.