Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы, вещественный точечный вариант: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
(Добавление категории.) |
ASA (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]] | Основные авторы описания: [[Участник:Frolov|А.В.Фролов]] | ||
| − | == | + | == Свойства и структура алгоритма == |
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Метод Хаусхолдера''' (в советской математической литературе называется также '''методом отражений''') используется для разложения матриц в виде <math>A = QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица). При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц отражения. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы <math>A</math> с использованием минимального одномерного дополнительного массива. | + | '''Метод Хаусхолдера''' (в советской математической литературе называется также '''методом отражений''') используется для разложения матриц в виде <math>A = QR</math> (<math>Q</math> - унитарная, <math>R</math> — правая треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц отражения. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы <math>A</math> с использованием минимального одномерного дополнительного массива. |
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| Строка 13: | Строка 13: | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
| − | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| Строка 22: | Строка 21: | ||
[[file:HausholderQR-1.png|thumb|center|600px|Граф алгоритма без отображения входных и выходных данных. n=4.]] | [[file:HausholderQR-1.png|thumb|center|600px|Граф алгоритма без отображения входных и выходных данных. n=4.]] | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
| − | == Программная реализация == | + | == Программная реализация алгоритма == |
| − | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Локальность данных и вычислений === | |
| − | === | + | ==== Локальность реализации алгоритма ==== |
| − | + | ===== Структура обращений в память и качественная оценка локальности ===== | |
| − | ==== | ||
| − | |||
| − | ===== | ||
| − | |||
===== Количественная оценка локальности ===== | ===== Количественная оценка локальности ===== | ||
| − | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | === Возможные способы и особенности реализации | ||
| − | |||
| − | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
| − | + | ==== Масштабируемость алгоритма ==== | |
| − | ==== | + | ==== Масштабируемость реализации алгоритма ==== |
| − | |||
| − | ==== | ||
| − | |||
| − | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
| − | |||
| − | |||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
== Литература == | == Литература == | ||
| − | + | <references /> | |
| − | |||
| − | |||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
Версия 11:41, 29 июля 2015
Основные авторы описания: А.В.Фролов
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод Хаусхолдера (в советской математической литературе называется также методом отражений) используется для разложения матриц в виде [math]A = QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица)[1]. При этом матрица [math]Q[/math] хранится и используется не в своём явном виде, а в виде произведения матриц отражения. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы [math]A[/math] с использованием минимального одномерного дополнительного массива.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
3 Литература
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
