Участник: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
Вычислительное ядро алгоритма
Для базового алгоритма вычислительное ядро состоит из операций двух типов:
1) поиска QR разложения с использованием метода Гивенса
2) матричного умножения полученных матриц
Макроструктура алгоритма
//TODO
Схема реализации последовательного алгоритма
Последовательная реализация простейшего алгоритма сострит из некоторого числа итераций.
На итерации [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 }[/math] имеет размер [math]\displaystyle{ n x 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
Ресурс параллелизма алгоритма
// 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