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

Тамбовский государственный университет имени Г.Р.Державина

005049316

На правах рукописи

Переславцева Оксана Николаевна

Вычисление характеристических полиномов плотных матриц: последовательные и параллельные алгоритмы

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

7 ФЕВ 2013

Тамбов 2013

005049316

Работа выполнена на кафедре математического анализа Тамбовского государственного университета имени Г. Р. Держави на.

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

профессор

Малашонок Геннадий Иванович

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

старший научный сотрудник Корняк Владимир Васильевич

кандидат физико-математических наук, доцент

Зобнин Алексей Игоревич

Ведущая организация: Саратовский государственный

университет имени Н.Г. Чернышевского

Защита диссертации состоится 1 марта 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при факультете вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В.Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан 21 января 2013 г.

Председатель диссертационного совета, член-корр. РАН, профессор / /Z / Л.Н.Королев

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

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

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

Характеристические полиномы матриц впервые появляются в трудах Лапласа, Якоби и Леверье. За прошедшие полтора столетия они нашли приложения в самых разных теоретических и прикладных областях - в теории матриц, в терии представлений групп, в механике, в астрономии, в физике, химии, биологин, во многих технических задачах, в теории управления.

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

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

1 Le Verrier U.J.J. Sur les variations séculaires des éléments elliptiques des sept planètes principales: Mercure, Venus, La Terre, Mars, Jupiter, Saturne et Uranus // Journal de Mathématiques Pures et Appliquées. 1840. N4. 220-254.

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

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

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

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

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

В работе Икрамова Х.Д.7 как наиболее эффективный способ точного вычисления характеристического многочлена матриц над копеечными полями рекомендуется метод Данилевского8 (1937), который требует выполнения ~ 2п3 операций. Асимптотически лучшими последовательными алгоритмами для вычисления характеристического полинома в конечном поле являются алгоритм Келлер-Гехрига9 (1985) н вероятностный алгоритм Пернета-Сторьоханна10 (2007), которые требуют выполнения 0(n" log2 п) и 0(пш) операций соответственно. Здесь ©(71") обозначает сложность матричного умножения.

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

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

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

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

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

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

"Kumura K., Anai H. 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.

12Philippe 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.

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

Даль работы.

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

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

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

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

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

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

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

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

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

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

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

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

Практическая значимость. .

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

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

Результаты исследований докладывались на Международных научных конференциях Parallel Computer Algebra (РагСА'2010) (Тамбов, 29 июня - 3 июля 2010), 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), "Современное математическое образование и проблемы истории и методологии математики" (Тамбов, 2006, 2008), Державин-ские чтения (Тамбов, 2005—2012), научном семинаре «Компьютерная алгебра» факультета ВМК МГУ и ВЦ РАН, научных семинарах в Тамбовском государственном университете.

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, библиографии и трех приложений. Общий объем диссертации составляет 117 страниц, включая 23 рисунка, 7 таблиц. Библиография включает 56 наименований.

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

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

В 1-й главе исследуются известные точные алгоритмы вычисления характеристических полиномов матриц в коммутативной области: методы Леверье, Леверье-Винограда, метод Леверье-Фаддеева, алгоритм Чистова, алгоритм Берковича, алгоритм Сейфуллина, алгоритм Мала-шонка. Вычисляется количество кольцевых операций в каждом алгоритме. Разрабатывается новый алгоритм вычисления характеристических полиномов матриц в коммутативной области, который имеет наименьшее число кольцевых операций среди известных алгоритмов.

В основе алгоритма лежит разложение данной матрицы А порядка п х п в произведение квазитреугольной В и диагональной D ~' матриц: А = ВD~1. Вычисление характеристического полинома данной матрицы выполняется по формуле: det(xD — В)/det D.

Обозначим В111 = А, (В1'1)) — элемент матрицы стоящий на пересечении г-ой строки и j-го столбца.

Вычисление квазитреугольной матрицы В выполняется за п-2 шага, На шаге I (I = 1,..., п - 2) вычисляется матрица, у которой обнуляются элементы ¿-го столбца под "второй" диагональю:

В[1+1] = иВ^Ьи ГДС (Ее 0 0 \ / Еь 0 0 \

I, = 0 1 0 , и = 0 а4 О

\ О -V1 а1Еп^~ 1 ) \ О V4 /

а4 = Для I = 1, 2 и а' = (В141)^/^")'^ для * = 3,..., т» - 2;

= для ( = 1,2„ „' = (В141)Г2,7(5"1)!12 Для I = . ,п-2.

Последней вычисляется квазитреугольная матрица В = 11.

Диагональная матрица О вычисляется по формуле Б = с11ад(1, а1, а1«2,..., ^а2 • • • ап~2, а1«2 • • ■ а""2).

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

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

Алгоритм Леверье Леверье-Фаддеева Чистова Берковича

Количество операций ~ 2п4 ~ 2п4 ~ 2/Зтг4 ~ 1/2 п4

Алгоритм Сейфуллина Леверье-Винограда Малашонка новый

Количество операций ~ 1/2п4 ~ 2п3-5 ~ 8/3п3 ~ 7/3?г3

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

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

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

Показано, что в классе прямых алгоритмов для целочисленных матриц асимптотически лучшими являются методы Леверье, Леверье-Вино-града и Леверье-Фаддеева, если в них используется алгоритм Штрассе-

на14 для умножения матриц. Для матриц, порядок которых менее 4700, лучшим является алгоритм Сейфуллина.

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

В 1-м параграфе для кольца целых чисел вычисляются выражения для сложности алгоритмов в числе мультипликативных операций над машинными словами. Для метода Леверье, метода Леверье-Винограда, метода Леверье-Фадцеева, алгоритма Чистова, алгоритма Берковича и алгоритма Сейфуллина выражения для сложности являются полиномиальной функцией, а для алгоритма Малашонка и нового алгоритма — экспоненциальной функцией. Эти выражения позволяют сравнивать полученные прямые алгоритмы вычисления характеристических полиномов в кольце целых чисел.

Пусть п — порядок матрицы, элементы матрицы содержат Ь слов и для умножения матриц используется алгоритм Штрассена. Обозначим |\рп = Г'°ви> — количество машинных слов, необходимых для записи числа п, где ги = Iй, й — число двоичных разрядов в машинном слове.

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

Метод Число машинных операций умножения

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

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

Метод Леверье-Фадцеева ~f(b + ¥>n)n4-B1

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

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

Алгоритм Чистова ~ i(19b + 3v>„)n°

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

Как видно из таблицы 2, среди рассмотренных алгоритмов асимптотически лучшими являются методы Леверье, Леверье-Винограда и Леверье-Фадцеева. Ближайший к ним по времени алгоритм — алгоритм Сейфуллина. Методы Леверье будут быстрее алгоритма Сейфуллина, если |(Ь + <рп)п4'81 < -^(Ь + <рп)п5. Поэтому для матриц небольших размеров лучшим среди прямых алгоритмов будет алгоритм Сейфуллина, а при п > 4700 лучшими будут алгоритмы Леверье, если в них использовать умножение по алгоритму Штрассена.

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

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

Во 2-м параграфе исследуется алгоритм Данилевского. В этом алгоритме требуется выполнить 2?г3 - 5г? + 6?г - 3 операций в поле К.

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

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

Эксперименты подтвердили, что лучшее время вычислений показывает метод гомоморфных образов, в котором используется метод Данилевского для конечных полей. Однако для матриц небольших размеров (не более, чем 35 х 35) прямой метод Сейфуллина является лучшим (см. рис. 1).

Ь (bits)

Рис. 1. Граничная линия, разделяющая плоскость на две области S и D. В области S выигрывает алгоритм Сейфуллина, а в области D выигрывает метод гомоморфных образов, Ь — разрядность коэффициентов матрицы, п — порядок матрицы.

Эксперименты показали, что алгоритм, основанный на методе гомоморфных образов, в котором в конечном поле используется алгоритм Данилевского, вычисляет характеристический полином существенно быстрее, чем Maple 9.5 и Mathematica 7.0. Например, для Ь = 7 и п — 50 Mathematica проигрывает в 5,9 раза, a Maple проигрывает в 11,5 раза. Для п = 100 алгоритм, основанный на методе гомоморфных образов, быстрее, чем Mathematica в 13,1 раз и быстрее, чем Maple в 13,8 раз, а для п — 200 — в 26 и 16 раз соответственно.

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

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

Обозначим для полинома д через ||з|| — наибольший по абсолютной величине числовой коэффициент и s{g) — количество мономов в полиноме д.

Пусть А = (dij(x)), 1 < г < га, 1 < j < п — исходная матрица полиномов, d = 77iaz{deg a,j(x)}, а = maa:{||aij||} для 1 ^ i п, 1 ^ j ^ п; с = max{s(a,ij(x))} — максимальное число мономов у элементов матрицы.

Теорема 2.1. Пусть F(x, у) = уп + fi {х)у11~г + ... + /„(ж) - характеристический полином матрицы А(х) £ Znxn[x¡. Тогда max{degfi(x),...,degfn(x)} sí n-d 4-1 и для наибольшего по модулю числового коэффициента полинома F(x, у) выполняется неравенство

log2 \\F(x, у) 11 ^ ti (logo п + log2 a + log2 с) - log2 с.

Экспериментальное сравнение алгоритмов вычисления характеристических полиномов для полиномиальных матриц показало, что алгоритм, основанный на методе гомоморфных образов, в котором для вычисления характеристического полинома в конечном поле используется алгоритм Данилевского, выигрывает у остальных рассматриваемых алгоритмов. Кроме того, он быстрее алгоритма, реализованного в системе компьютерной алгебры Mathematica. Например, если порядок матрицы п ~ 20 и степень входных полиномов d ~ 15, он вычисляет характеристический полином быстрее в 23 раза, чем алгоритм, который реализован в системе Mathematica 7.0.

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

В 1-м параграфе описывается параллельный алгоритм вычисления характеристических полиномов матриц для кольца целых чисел. Раздача простых модулей происходит по бинарному дереву. Для этого при переходе на следующий уровень дерева процессор делит отрезок номеров числовых модулей [¿i; ¿2] на два отрезка [i'i; j¡ и {j + 1;«2¡, где j =

(¿j+i2)/2. Один отрезок он оставляет себе, а второй передает свободному процессору. Процесс бинарного деления останавливается, когда исчерпываются или процессоры или модули. На листовых вершинах вычисляются характеристические полиномы по простым модулям. Восстановление полинома происходит при подъеме от листовых вершин к корневой вершине на каждом узле бинарного дерева.

Графики зависимости времени вычисления от количества процессоров носят ступенчатый характер. Скачкообразное уменьшение времени вычисления наблюдается, когда количество процессоров кратно 2Р, где р — натуральное число. Наилучшее ускорение достигается, если количество процессоров является степенью числа 2.

Во 2-м параграфе описывается алгоритм вычисления характеристических полиномов полиномиальных матриц, граф которого пред--ставляет собой бинарное дерево. Этот алгоритм аналогичен алгоритму, рассмотренному в 1-м параграфе. Отличие состоит в том, что здесь вместо списка номеров числовых модулей [¿i;i2] рассматривается список, включающий как числовые, так и полиномиальные модули. Один отрезок задает номера модулей одной переменной или номера числовых модулей.

Вначале вычислений создается список отрезков intervals = {[1, тщ],..., [1, mt), [1, h\} полиномиальных и числовых модулей. Начиная с отрезка номеров числовых модулей [1,Л] и спускаясь по бинарному дереву, перемещаемся влево по списку отрезков intervals и делим эти отрезки до тех пор, пока в них останется один номер модуля или не останется свободных процессоров.

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

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

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

Пусть к — количество процессоров кластера с номерами 0, 1, 2,. .., (к—

1) и на нулевом процессоре имеется исходная матрица А над полиномами из кольца Z[ xi,..., xt]. Пусть множество М, которое содержит необходимый список простых чисел, имеется на каждом процессоре.

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

Этап 1. Вычисление количества модулей.

Каждый процессор вычисляет необходимые для данной задачи модули. Количество модулей определяется теоремой 2.1.

Этап 2. Решение задачи в гомоморфных образах в конечном поле.

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

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

Нулевой процессор разбивает один из полиномов на к частей, посылает полученный шаблон разбиения полинома на все процессоры.

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

г-й процессор, i = 0,1,..., к — 1, посылает j-e части всех своих полиномов j-му процессору, j = 0,..., к - 1, j -ф г. Таким образом на каждом процессоре будут получены остатки по всем модулям для всех коэффициентов соответствующей части характеристического полинома.

Каждый процессор восстанавливает соответствующую часть характеристического полинома.

Этап 4■ Сбор результата на нулевом процессоре.

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

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

Доказываются теоремы о временной сложности параллельного алгоритма.

Теорема 3.1. Пусть А €. ZnXn[x¡,...,xt] — полиномиальная матрица, у элементов которой а — наибольший по абсолютной величине числовой коэффициент, s — наибольшее количество мономов, degi — наибольшая степень по переменной Xi , г = 1,..., t. Пусть к — количество процессоров.

Тогда время, необходимое для вычисления характеристического полинома матрицы А с использованием параллельного алгоритма с восстановлением на листьях, без учета времени пересылки данных между процессорами равно Tn,k = 0( j;nt+4(log2 п + log2 а + log2 s) Пг'=1 degi).

Теорема 3.2. Пусть А £ Z"Xn[xi,... ,Xt\ — полиномиальная матрица, у элементов которой а — наибольший по абсолютной величине

числовой коэффициент, а - наибольшее количество мономов, (1ецг наибольшая степень по переменной ач, г = 1,..., Пусть к — количество процессоров.

Тогда время, необходимое для пересылки данных между процессорами при вычислении характеристического полипома с использованием параллельного алгоритма с восстановлением на листьях, равно ТБп,к = ©(¿тг'+2(1об2 п + 1оЙ2 а + 1о&2 в) ГП=1 ¿ед*).

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

ТОмиИе)

Т (ттШе)

Рис. 2. Время вычисления характеристического полинома для числовой матрицы, элементами которой являются 7-ми разрядные двоичные числа, используя к процессоров.

T (minute)

400

800

600

200

п

200

400

600

800

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

В заключении приведены основные результаты работы.

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

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

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

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

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

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

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

Основные публикации по теме диссертации:

Публикации в изданиях из списка ВАК:

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

2. Переславцева О.Н. О вычислении коэффициентов характеристического полинома. Вычислительные методы и программирование: новые вычислительные технологии. 2008. Т. 9. № 2. С. 180-184.

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

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

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

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

7. Переславцева О.Н. Эксперименты с параллельным алгоритмом вычисления характеристических полиномов матриц в кольце полиномов. Вестник Тамбовского университета. Сер. Естественные и технические науки. Том 15, вып. 1, 2010. С. 346-349.

8. Переславцева О.Н. Параллельный алгоритм вычисления характеристических полиномов матриц, основанный на методе гомоморфных образов. Вестник Тамбовского университета. Сер. Естественные и технические пауки. Том 15, вып. 4, 2010. С. 1413-1425.

9. Переславцева О.Н. О вычислении характеристического полинома матрицы И Дискретная математика. Т. 23, вып. 1, 2011, с. 28-45. (eng. tansl.: Pereslavtseva O.N. Calculation of the characteristic polynomial of a matrix // Discrete Mathematics and Applications. Volume 21, Issue 1, 2011. P. 109129.)

10. Переславцева О.Н. Параллельный модулярный алгоритм вычисления характеристического полинома матрицы в кольце полиномов многих переменных // Вестник Тамбовского университета. Сер. Естественные и

технические науки. Том 17, вып. 2, 2012. Прочие публикации:

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

12. Переславцева О.Н. История и современное состояние теории алгоритмов вычисления характеристического полинома матрицы // Международная научная конференция «Современное математическое образование и проблемы истории и методологии математики». Тамбов: Изд-во Першина Р.В. 2006. С.130-134.

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

14. Малашонок Г.И., Переславцева О.Н., Сажнева O.A., Старов М.В. Алгоритмы компьютерной алгебры. Часть 1. Учебное пособие. Тамбов: Издательский дом ТГУ им. Г.Р. Державина, 2008.

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

16. Переславцева О.Н. Параллельное вычисление характеристического полинома матрицы // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Новгород, 30 марта - 3 апреля 2009 г.). - Челябинск: Изд. ЮУрГУ, 2009. -С. 817-821.

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

18. Переславцева О.Н. Вычисление характеристических полиномов матриц: последовательные и параллельные алгоритмы // Mathematical Modeling and Computational Physics (MMCP'2009): Book of Abstracts of the International Conference (Dubna, July 7-11, 2009). - Dubna: JINR, 2009. P. 130-131.

19. Малашонок Г.И., Старов M.B., Бетин A.A., Переславцева O.H., Позд-никин А.Г. Параллельная компьютерная алгебра. Часть 1. Учебное пособие. Тамбов: Издательский дом ТГУ им. Г.Р. Державина, 2010.

20. Pereslavtseva O.N. Parallel algorithm for computing the characteristic polynomials of polynomial matrices // International Conference Polynomial Computer Algebra. St. Peterburg 2012. C. 67-69.

Подписано в печать 18.01.2013 г. Формат 60x84/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 1021. Бесплатно.

392008, Тамбов, ул. Советская, 190г. Издательский дом ТГУ имени Г.Р. Державина. Отпечатано в типографии Издательского дома ТГУ имени Г.Р. Державина

Введение.

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. Выигрыш во времени растет с ростом размеров матриц.

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

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

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.