Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме: различия между версиями
Frolov (обсуждение | вклад) м (Frolov переименовал страницу Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме в [[Метод Хаусхол…) |
Frolov (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения матриц в виде <math>A= | + | '''Метод Хаусхолдера''' (в советской математической литературе чаще называется '''методом отражений''') используется для разложения матриц в виде <math>A=QRQ^T</math> (<math>Q</math> - ортогональная, <math>R</math> — правая почти треугольная матрица)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. При этом матрица <math>Q</math> хранится и используется не в своём явном виде, а в виде произведения матриц отражения<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием одномерного дополнительного массива. |
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | ||
| Строка 23: | Строка 23: | ||
{{Шаблон:Матрица отражений}} | {{Шаблон:Матрица отражений}} | ||
| − | На <math>i</math>-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные элементы в <math>i</math>-м столбце, а потом | + | На <math>i</math>-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные (кроме первой поддиагонали) элементы в <math>i</math>-м столбце, а потом выполняется преобразование того же отражения, но справа. Таким образом, после <math>n-2</math> шагов преобразований получается хессенбергова <math>R</math> из разложения матрицы в произведение хессенберговой и двух ортогональных. |
На каждом из шагов метода матрицы отражений обычно представляют не в стандартном виде, а в виде <math>U=E-\frac{1}{\gamma}vv^*</math>, где <math>v</math> находится для левых матриц отражения через координаты текущего <math>i</math>-го столбца так: | На каждом из шагов метода матрицы отражений обычно представляют не в стандартном виде, а в виде <math>U=E-\frac{1}{\gamma}vv^*</math>, где <math>v</math> находится для левых матриц отражения через координаты текущего <math>i</math>-го столбца так: | ||
| Строка 35: | Строка 35: | ||
После вычисления вектора <math>v</math> подстолбцы справа от ведущего модифицируются по формулам <math>x'=x-\frac{(x,v)}{\gamma}v</math>. | После вычисления вектора <math>v</math> подстолбцы справа от ведущего модифицируются по формулам <math>x'=x-\frac{(x,v)}{\gamma}v</math>. | ||
| − | + | Затем с помощью вычисленных параметров отражения выполняется умножение на матрицу Хаусхолдера справа. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| − | |||
| − | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| Строка 65: | Строка 57: | ||
'''Объём входных данных''': <math>n^2</math>. | '''Объём входных данных''': <math>n^2</math>. | ||
| − | '''Объём выходных данных''': <math>n^2+ | + | '''Объём выходных данных''': <math>n^2+n</math>. |
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 12:44, 8 декабря 2016
| Разложение в произведение хессенберговой и двух ортогональных матриц методом Хаусхолдера (отражений) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(n^3)[/math] |
| Объём входных данных | [math]n^2[/math] |
| Объём выходных данных | [math]n(n + 2)[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(n^2)[/math] |
| Ширина ярусно-параллельной формы | [math]O(n^2)[/math] |
Основные авторы описания: А.В.Фролов
Содержание
- 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=QRQ^T[/math] ([math]Q[/math] - ортогональная, [math]R[/math] — правая почти треугольная матрица)[1]. При этом матрица [math]Q[/math] хранится и используется не в своём явном виде, а в виде произведения матриц отражения[2]. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием одномерного дополнительного массива.
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений.
1.2 Математическое описание алгоритма
В методе Хаусхолдера для выполнения разложения матрицы в произведение хессенберговой и двух ортогональных используются попеременные умножения слева и справа её текущих модификаций на матрицы Хаусхолдера (отражений).
Матрица отражений (Хаусхолдера) - матрица вида [math]U=E-2ww^*[/math], где [math]w[/math] - вектор, удовлетворяющий равенству [math]w^{*}w=1[/math]. Является одновременно унитарной ([math]U^{*}U=E[/math]) и эрмитовой ([math]U^{*}=U[/math]), поэтому обратна самой себе ([math]U^{-1}=U[/math]).
На [math]i[/math]-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные (кроме первой поддиагонали) элементы в [math]i[/math]-м столбце, а потом выполняется преобразование того же отражения, но справа. Таким образом, после [math]n-2[/math] шагов преобразований получается хессенбергова [math]R[/math] из разложения матрицы в произведение хессенберговой и двух ортогональных.
На каждом из шагов метода матрицы отражений обычно представляют не в стандартном виде, а в виде [math]U=E-\frac{1}{\gamma}vv^*[/math], где [math]v[/math] находится для левых матриц отражения через координаты текущего [math]i[/math]-го столбца так:
[math]s[/math] - вектор размерности [math]n+1-i[/math], составленный из элементов [math]i[/math]-го столбца, начиная с [math]i[/math]-го.
Если [math](s,s)=0[/math], то [math]v=e_{i}[/math], [math]\gamma = \frac{1}{2}[/math].
В остальных случаях по алгоритму вычисляется [math]u = \frac{1}{\sqrt{(s,s)}}s[/math], и далее [math]v_{j}=0[/math] при [math]j\lt i[/math], [math]v_{j}=u_{j-i+1}[/math] при [math]j\gt i[/math], а [math]v_{i}=1[/math], если [math]u_{1}=0[/math] и [math]v_{i}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)[/math] для остальных значений. При этом [math]\gamma = 1+|u_{1}|[/math].
После вычисления вектора [math]v[/math] подстолбцы справа от ведущего модифицируются по формулам [math]x'=x-\frac{(x,v)}{\gamma}v[/math].
Затем с помощью вычисленных параметров отражения выполняется умножение на матрицу Хаусхолдера справа.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
При классификации по последовательной сложности, таким образом, метод Хаусхолдера относится к алгоритмам с кубической сложностью.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные: плотная квадратная матрица [math]A[/math] (элементы [math]a_{ij}[/math]).
Объём входных данных: [math]n^2[/math].
Объём выходных данных: [math]n^2+n[/math].
1.10 Свойства алгоритма
Вычислительная погрешность в методе отражений (Хаусхолдера) растет линейно, как и в методе Гивенса (вращений).
