Участник:Elijah/Нахождение собственных чисел квадратной матрицы методом QR разложения
| Нахождение собственных чисел квадратной матрицы методом QR разложения | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ N * O(n^3) }[/math] |
| Объём входных данных | [math]\displaystyle{ n^2 }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ N * (12n - 15) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(n^2) }[/math] |
Основные авторы описания: И.В.Афанасьев, В.А.Шишватов
Свойства и структура алгоритма
Общее описание алгоритма
//TODO
Математическое описание алгоритма
//TODO
Вычислительное ядро алгоритма
У базового QR алгоритма есть два вычислительных ядра:
- операция поиска QR разложения с использованием метода Гивенса
- матричное умножения полученных матриц
Макроструктура алгоритма
Как уже описано в описании ядра алгоритма, базовая версия QR-алгоритма на каждой итерации использует следующие алгоритмы:
Схема реализации последовательного алгоритма
Последовательная реализация простейшего алгоритма сострит из некоторого числа итераций.
На итерации [math]\displaystyle{ n }[/math]:
- Для матрицы [math]\displaystyle{ A_{n} }[/math] строится QR разложение любым доступным последовательным алгоритмом на матрицы [math]\displaystyle{ Q_{n} }[/math] и [math]\displaystyle{ R_{n} }[/math]
- Матрицы [math]\displaystyle{ R_{n} }[/math] и [math]\displaystyle{ Q_{n} }[/math] перемножаются, таким образом получается матрица [math]\displaystyle{ A_{n+1} = R_{n} * Q_{n} }[/math] для следующей итерации [math]\displaystyle{ n + 1 }[/math]
По окончании каждой итерации проверятся, приведена ли матрица к диагональной форме.
// TODO about heisenberg form and algorithm with shift
Последовательная сложность алгоритма
Рассчитаем последовательную сложность базового алгоритма. Пусть [math]\displaystyle{ A \in \mathbb{R}^{n \times n} }[/math], и для приведения матрицы к диагональной форме необходимо произвести N итераций алгоритма.
На каждой итерации алгоритма производится QR разложение (сложностью [math]\displaystyle{ 2 * n^3 }[/math]) и матричное умножение (сложностью [math]\displaystyle{ n^3 }[/math]). Проверка того, имеет ли матрица диагональную форму, может быть проведена за [math]\displaystyle{ n^2 }[/math] операций.
Таким образом итоговая сложность одной итерации составляет: [math]\displaystyle{ 3*n^3 + n^2 = O(n^3) }[/math]
Общая сложность алгоритма при [math]\displaystyle{ N }[/math] итерациях составляет [math]\displaystyle{ N * O(n^3) }[/math]
// TODO about heisenberg complexity
Информационный граф
//TODO
Ресурс параллелизма алгоритма
Все итерации базового QR-алгоритма производятся последовательно, поэтому на верхнем уровне алгоритм чисто последователен.
Основной ресурс параллелизма представлен на нижнем уровне, при реализации различных операций, используемых в алгоритме, таких как QR разложение методом вращений и матричное умножение.
Параллельная сложность базового QR-алгоритма
Посчитаем параллельную сложность каждой операции по отдельности, а затем, по полученным данным, и всего алгоритма целиком:
- Параллельная сложность QR разложения методом вращений составляет [math]\displaystyle{ 11n - 16 }[/math] [1]
- Параллельная сложность матричного умножения составляет [math]\displaystyle{ n }[/math][2].
- Параллельная сложность проверки, является ли матрица диагональной, равна 1.
Таким образом параллельная сложность каждой итерации составляет [math]\displaystyle{ 12n - 15 }[/math]. При N итерациях, которые необходимо производить последовательно, итоговая сложность базового алгоритма составляет [math]\displaystyle{ N * (12n - 15) }[/math]
// TODO for Heisenberg
Входные и выходные данные алгоритма
Входные данные: плотная квадратная матрица [math]\displaystyle{ A }[/math] (элементы [math]\displaystyle{ a_{ij} }[/math]).
Объём входных данных: [math]\displaystyle{ n^2 }[/math].
Выходные данные: n вещественных собственных чисел [math]\displaystyle{ | l_{i} | }[/math] матрицы [math]\displaystyle{ A }[/math]
Объём выходных данных: [math]\displaystyle{ n }[/math].
Свойства алгоритма
Соотношение последовательной и параллельной сложности как для базового, так и для оптимизированного алгоритма, является квадратичным, что даёт хороший стимул для распараллеливания.
Вычислительная мощность, равная отношению числа операций [math]\displaystyle{ N * O(n^3) }[/math] к суммарному объему входных и выходных данных [math]\displaystyle{ n^2 + n }[/math], для каждой итерации линейна, а для всего алгоритма в целом равна [math]\displaystyle{ N*n }[/math], что позволяет сделать вывод о том, что перемещение данных для обработки не играет важной роли в данном алгоритме.
Данный алгоритм недетерминирован, так как число итераций зависит от значений матрицы.
Вычислительная погрешность растет линейно, из-за использования метода вращений для QR разложения.
// TODO Сбалансированность и другие свойства из общего описания