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

• Автор: Переславцева, Оксана Николаевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Тамбов
• Количество страниц: 117 с. : ил.

ОГЛАВЛЕНИЕ
Введение

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

коммутативных областях

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

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

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

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

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

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

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

1.8. Выводы
2 Алгоритмы вычисления характеристических полиномов матриц в кольце целых чисел и в кольце полиномов
с целыми коэффициентами
2.1. Сложность алгоритмов, выраженная в числе машинных операций
2.1.1. Метод Леверье.
2.1.2. Метод ЛеверьеВи но града
2.1.3. Алгоритм ЛеверьеФаддесва.
2.1.4. Алгоритм Чистова
2.1.5. Алгоритм Берковича
2.1.0. Алгоритм Ссйфуллина.
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. Алгоритмы, описанные в главе 1.
Приложение 2. Алгоритм, описанный в параграфе 2 главы 3.
Приложение 3. Алгоритм, описанный в параграфе 3 главы 3.
Литература


В параграфе 1 исследуются методы Леверье и Леверье-Винограда |4, 7|. В основе метода Леверье лежит вычисление для данной матрицы /1 ее степеней А2,. Ап. Для этих матриц вычисляются следы /ц, я«, которые связаны с коэффициентами Д,. М_1 - . Метод Лсверье-Винограда отличается тем, что вычисляются матричные степени 'только до Ат, где т = у/п~— 1"), а для остальных матриц вычисляются диагональные элементы. Если алгоритм матричного умножения имеет сложность то алгоритм Леверье требует выполнения ~ пш+1 операций умножения в кольце, а алгоритм Леверье-Вшюграда — ~ ли;+0‘5 операций умножения 1} кольце. В параграфе 2 исследуется метод Ле вер ьс-Фаддее на [в], который также как и метод Левсрье требует выполнения ~ nW r 1 операций умножения в кольце. В параграфах 3 и 4 исследуются алгоритмы Чистова [] и Берковича _|. Показано, что алгоритм Берковича имеет меньшую сложность, чем алгоритм Чистова. Алгоритм Чистова требует выполнения ~ 1/3пл операций умножения и столько же операций сложения в кольце R. Алгоритм Берковича требует выполнения ~ 1/4п4 операций умножения и столько же операций сложения в кольце R. В 5-м параграфе исследуется алгоритм Сейфуллина [8], основой которого стал метод Леверье-Фаддеева. Т.Р. Сейфуллин заметил, что деление в алгоритме Лсверье-Фадцссва па целые числа связано с многократным сложением одних и тех же слагаемых, и исключил это многократное сложение путем частичного умножения матриц. Алгоритм требует выполнения ^ 1/4п'1 операций умножения и столько же операций сложения в кольце R. В 6-м параграфе приводится алгоритм Малашоика [], который требует выполнения ~ 4/Згс3 операций умножения, ~ 1/Згг3 операций сокращения и ~ п3 операций сложения в коммутативной области. В основе алгоритма лежит вычисление эквивалентной квазитреуголыши матрицы и последующее непосредственное вычисление определителя такой матрицы. В 7-м параграфе разрабатывается новый алгоритм [], который имеет наименьшее число кольцевых операций среди известных алгоритмов. В основе алгоритма лежит разложение данной матрицы А в произведение квазитрсугольной В и диагональной D~l матриц: А = BD"1. Вычисление характеристического полинома данной матрицы выполняется по формуле: det(xD - В)/ dot D. Обозначим ВМ = А, (ВЩ1^ — элемент матрицы стоящий на пересечении 2-ой строки и j-ro столбца. Вычисление квазитреугольной матрицы В выполняется за п — 2 шага. Для і = 1,2 и а* = {ВЩ[+1/(В^):1 Для і = 3,. Vі = (вЩ[+2'п для * = 1,2 и Vі = (ВЩ? ВЩ1Г_ для < = 3,. Диагональная матрица Г) вычислялся по формуле й — сИад(1,а1,а1а2,. Необходимо обратить внимание на то, что все вычисления в алгоритме происходят в исходном кольце коэффициентов, и все деления являются точными. Предложенный алгоритм требует выполнения ~ 4/3и? В 8-м параграфе проводится сравнительный анализ всех 8 алгоритмов по количеству кольцевых операций. Результаты сведены в таблицу 1. В этой главе разрабатываются два класса алгоритмов — прямые алгоритмы и алгоритмы, основанные на методе гомоморфных образов. Показано, что в классе прямых алгоритмов для целочисленных матриц асимптотически лучшими являются методы Леверьс, Леверьс-Винограда и Лсвсрье-Фаддеева, если в них используется алгоритм Штрасссна (] для умножения матриц. Для матриц, порядок которых менее , лучшим является алгоритм Сейфуллина. Экспериментальное сравнение алгоритмов показало, что алгоритм, основанный па методе гомоморфных образов, который в конечном поле использует алгоритм Данилевского, быстрее остальных семи рассматриваемых алгоритмов в кольце целых чисел и в кольце полиномов. В 1-м параграфе для кольца целых чисел вычисляются выражения для сложности алгоритмов в числе мультипликативных операций над машинными словами. Для метода Лсвсрье, метода Леверьс-Винограда, метода Леверье-Фаддеева, алгоритма Чистова, алгоритма Берковича и алгоритма Сейфуллина выражения для сложности являются полиномиальной функцией, а для алгоритма Малашопка и нового алгоритма — экспоненциальной функцией. Эти выражения позволяют сравнивать полученные прямые алгоритмы вычисления характеристических полиномов в кольце целых чисел.