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

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

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

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

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

//TODO

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

//TODO

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

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

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

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

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

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

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 \in \mathbb{R}^{n \times 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 Ресурс параллелизма алгоритма

Все итерации базового QR алгоритма производятся последовательно, поэтому на верхнем уровне алгоритм чисто последователен.

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

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

// 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