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

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

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

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

//TODO

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

//TODO

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

//TODO

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

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

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

//TODO

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

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

На итерации [math] n [/math]:

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

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

// TODO about heisenberg form and algorithm with shift

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

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

// TODO about heisenberg complexity

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

//TODO

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

// TODO

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

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

Объём входных данных: [math]n^2[/math].

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

Объём выходных данных: [math]n[/math].

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

// TODO