Участник:Elijah/Нахождение собственных чисел квадратной матрицы методом QR разложения

Нахождение собственных чисел квадратной матрицы методом QR разложения
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ N * O(n^3) }[/math]
Объём входных данных	[math]\displaystyle{ n^2 }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ Unknown }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ Unknown }[/math]

Основные авторы описания: И.В.Афанасьев, В.А.Шишватов

Свойства и структура алгоритма

//TODO

Общее описание алгоритма

//TODO

Математическое описание алгоритма

//TODO

Вычислительное ядро алгоритма

У базового QR алгоритма есть два вычислительных ядра:

1. операция поиска QR разложения с использованием метода Гивенса
   
2. матричное умножения полученных матриц

Макроструктура алгоритма

Базовая версия QR алгоритма на каждой итерации использует следующие алгоритмы:

1. Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный вариант)
2. Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)

Схема реализации последовательного алгоритма

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

На итерации [math]\displaystyle{ n }[/math]:

1. Для матрицы [math]\displaystyle{ A_{n} }[/math] строится QR разложение любым доступным последовательным алгоритмом на матрицы [math]\displaystyle{ Q_{n} }[/math] и [math]\displaystyle{ R_{n} }[/math]
   
2. Матрицы [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 разложение методом вращений и матричное умножение.

Оценим потенциально возможное ускорение каждой операции по отдельности, а затем, по полученным данным, и всего алгоритма целиком:

// TODO

Входные и выходные данные алгоритма

Входные данные: плотная квадратная матрица [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].

Свойства алгоритма

// TODO