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

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

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

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

//TODO

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

//TODO

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

//TODO

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

Для базового алгоритма вычислительное ядро состоит из операций двух типов:
1) поиска QR разложения с использованием метода Гивенса
2) матричного умножения полученных матриц

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

//TODO

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

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

На итерации $n$:

1. Для матрицы $A_{n}$ строится QR разложение любым доступным последовательным алгоритмом на матрицы $Q_{n}$ и $R_{n}$
   
2. Матрицы $R_{n}$ и $Q_{n}$ перемножаются, таким образом получается матрица $A_{n+1} = R_{n} * Q_{n}$ для следующей итерации $n + 1$

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

// TODO about heisenberg form and algorithm with shift

1.6 Последовательная сложность алгоритма

Рассчитаем последовательную сложность базового алгоритма. Пусть матрица $A$ имеет размер $n x n$, и для приведение матрицы к диагональной форме необходимо произвести N итераций алгоритма.
На каждой итерации алгоритма производится QR разложение (сложностью $2 * n^3$) и матричное умножение (сложностью $n^3$). Проверка того, имеет ли матрица диагональную форму, может быть проведена за $n^2$ операции.
Таким образом итоговая сложность итерации составляет: $3*n^3 + n^2 = O(n^3)$
Общая сложность алгоритма при $N$ итерациях составляет $N * O(n^3)$

1.7 Информационный граф

//TODO

1.8 Ресурс параллелизма алгоритма

// TODO

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

Входные данные: плотная квадратная матрица $A$ (элементы $a_{ij}$).

Объём входных данных: $n^2$.

Выходные данные: n вещественных собственных чисел $| l_{i} |$ матрицы $A$

Объём выходных данных: $n$.

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

// TODO