Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант): различия между версиями

[непроверенная версия]

Версия 17:18, 22 октября 2014

Содержание

1 Описание свойств и структуры алгоритма
2 Программная реализация
3 Литература

1 Описание свойств и структуры алгоритма

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

Метод Гивенса (в советской математической литературе называется также методом вращений) используется для разложения матриц в виде [math]A = QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица). При этом матрица [math]Q[/math] хранится и используется не в своём явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения может быть определена её индексами и одним параметром. Это позволяет в классическом исполнении метода Гивенса хранить результаты разложения на месте матрицы [math]A[/math] без использования дополнительных массивов.

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

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

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

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

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

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

Граф алгоритма без отображения входных и выходных данных. n=4. F1 - операция вычисления параметров поворота, F2 - выполнение поворота 2-мерного вектора (эквивалентно операции умножения двух комплексных чисел).

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

1.9 Описание входных и выходных данных

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

2 Программная реализация

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.2.1 Описание локальности алгоритма

2.2.2 Описание локальности реализации алгоритма

2.2.2.1 Описание структуры обращений в память и качественная оценка локальности

2.2.2.2 Количественная оценка локальности

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Описание масштабируемости алгоритма

2.4.2 Описание масштабируемости реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.

@@ Строка 4: / Строка 4: @@
 === Общее описание алгоритма ===
-'''Метод Гивенса''' (в советской математической литературе называется также '''методом вращений''') используется для разложения  матриц в виде <math>A = QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица).
+'''Метод Гивенса''' (в советской математической литературе называется также '''методом вращений''') используется для разложения  матриц в виде <math>A = QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица). При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения может быть определена её индексами и одним параметром. Это позволяет в классическом исполнении метода Гивенса хранить результаты разложения на месте матрицы <math>A</math> без использования дополнительных массивов.
 === Математическое описание ===