Введение
1 Методы вычисления характеристических полиномов в коммутативных областях 15
1.1. Метод Леверье 16
1.2. Метод Леверье-Фаддеева 19
1.3. Метод Чистова 21
1.4. Алгоритм Берковича 22
1.5. Алгоритм Сейфуллина 24
1.6. Алгоритм Малашонка 29
1.7. Новый алгоритм 32
1.8. Выводы 34
2 Алгоритмы вычисления характеристических полино мов матриц в кольце целых чисел и в кольце полиномов с целыми коэффициентами 36
2.1. Сложность алгоритмов, выраженная в числе машинных операций 37
2.1.1. Метод Леверье 37
2.1.2. Метод Леверье-Винограда 38
2.1.3. Алгоритм Леверье-Фаддеева 39
2.1.4. Алгоритм Чистова 40
2.1.5. Алгоритм Берковича 41
2.1.6. Алгоритм Сейфуллина 42
2.1.7. Алгоритм Малашонка и новый алгоритм
2.2. Метод Данилевского 47
2.3. Применение метода гомоморфных образов для вычисления характеристических полиномов матриц в кольце целых чисел 50
2.4. Экспериментальное сравнение алгоритмов в кольце целых чисел 51
2.5. Вычисление характеристических полиномов полиномиальных матриц
2.5.1. Применение метода гомоморфных образов для вычисления характеристических полипомов полиномиальных матриц 56
2.5.2. Оценка коэффициентов характеристического полинома полиномиальной матрицы 57
2.5.3. Алгоритм, основанный на методе гомоморфных образов, который в конечном поле использует алгоритм Данилевского 59
2.5.4. Вычислительные эксперименты 60
2.6. Выводы 61
3 Параллельные алгоритмы вычисления характеристических полиномов 64
3.1. Параллельный алгоритм вычисления характеристических полиномов для целочисленных матриц с восстановлением по бинарному дереву 65
3.1.1. Алгоритм 65
3.1.2. Результаты экспериментов 66
3.2. Параллельный алгоритм вычисления характеристического полинома для полиномиальных матриц с восстановлением по бинарному дереву 69
3.2.1. Схема передачи данных 69
3.2.2. Алгоритм вычисления характеристического полинома полиномиальной матрицы 72
3.2.3. Пример в кольце полиномов от двух переменных 74
3.2.4. Эксперименты 79
3.3. Параллельный алгоритм вычисления характеристического по линома с восстановлением на листовых вершинах 81
3.3.1. Алгоритм 81
3.3.2. Время вычисления характеристического полинома 83
3.3.3. Эксперименты 86
3.4. Выводы 93
Заключение 94
Приложение 95
Приложение 1. Алгоритмы, описанные в главе 1 95
Приложение 2. Алгоритм, описанный в параграфе 2 главы 3 101
Приложение 3. Алгоритм, описанный в параграфе 3 главы 3 107
Литература
