Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный точечный вариант): различия между версиями
Перейти к навигации
Перейти к поиску
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
Строка 20: | Строка 20: | ||
− | [[file: | + | [[file:QRGivens2.png|thumb|center|600px|Граф алгоритма без отображения входных и выходных данных. n=4]] |
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === |
Версия 17:55, 17 октября 2014
Содержание
- 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.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.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.