Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме: различия между версиями
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | ||
| + | |||
| + | === Математическое описание алгоритма === | ||
| + | |||
| + | В методе Хаусхолдера для выполнения разложения матрицы в произведение хессенберговой и двух ортогональных используются попеременные умножения слева и справа её текущих модификаций на матрицы Хаусхолдера (отражений). | ||
| + | |||
| + | {{Шаблон:Матрица отражений}} | ||
| + | |||
| + | На <math>i</math>-м шаге метода с помощью преобразования отражения "убираются" ненулевые поддиагональные элементы в <math>i</math>-м столбце, а потом (кроме шага с номером <math>i=n-1</math>) с помощью преобразования отражения "убираются" ненулевые наддиагональные элементы в <math>i</math>-м столбце, кроме самого левого из них. Таким образом, после <math>n-1</math> шагов преобразований получается хессенбергова <math>D</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<i</math>, <math>v_{j}=u_{j-i+1}</math> при <math>j>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>. | ||
| + | |||
| + | Аналогично для правых матриц отражений <math>U=E-\frac{1}{\gamma}vv^*</math> <math>v</math> находится через координаты текущей <math>i</math>-й строки так: | ||
| + | |||
| + | <math>s</math> - вектор размерности <math>n-i</math>, составленный из элементов <math>i</math>-й строки, начиная с <math>i+1</math>-го элемента. | ||
| + | |||
| + | Если <math>(s,s)=0</math>, то <math>v=e_{i+1}</math>, <math>\gamma = \frac{1}{2}</math>. | ||
| + | |||
| + | В остальных случаях по алгоритму вычисляется <math>u = \frac{1}{\sqrt{(s,s)}}s</math>, и далее <math>v_{j}=0</math> при <math>j<i+1</math>, <math>v_{j}=u_{j-i+2}</math> при <math>j>i+1</math>, а <math>v_{i+1}=1</math>, если <math>u_{1}=0</math> и <math>v_{i+1}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)</math> для остальных значений. При этом <math>\gamma = 1+|u_{1}|</math>. | ||
| + | |||
| + | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Основную часть алгоритма составляют вычисления на каждом шагу скалярных произведений <math>(s,s)</math> и <math>(x,v)</math> для всех подстолбцов <math>x</math>справа от текущего, а также векторные операции <math>x'=x-\frac{(x,v)}{\gamma}v</math>, и затем вычисления на каждом шагу (кроме шага с номером <math>i=n-1</math>) скалярных произведений <math>(s,s)</math> и <math>(x,v)</math> для всех подстрок <math>x</math>снизу от текущей, а также векторные операции <math>x'=x-\frac{(x,v)}{\gamma}v</math>. Это используется при программировании метода во многих библиотеках для его конструирования из стандартных подпрограмм (например, из BLAS). | ||
| + | |||
| + | === Макроструктура алгоритма === | ||
| + | |||
| + | === Схема реализации последовательного алгоритма === | ||
| + | |||
| + | === Последовательная сложность алгоритма === | ||
| + | |||
| + | При классификации по последовательной сложности, таким образом, метод Хаусхолдера относится к алгоритмам ''с кубической сложностью''. | ||
| + | |||
| + | === Информационный граф === | ||
| + | |||
| + | === Ресурс параллелизма алгоритма === | ||
| + | |||
| + | === Входные и выходные данные алгоритма === | ||
| + | |||
| + | '''Входные данные''': плотная квадратная матрица <math>A</math> (элементы <math>a_{ij}</math>). | ||
| + | |||
| + | '''Объём входных данных''': <math>n^2</math>. | ||
| + | |||
| + | '''Объём выходных данных''': <math>n^2+2n</math>. | ||
| + | |||
| + | === Свойства алгоритма === | ||
| + | |||
| + | Вычислительная погрешность в методе отражений (Хаусхолдера) растет ''линейно'', как и в методе Гивенса (вращений). | ||
| + | |||
| + | == Программная реализация алгоритма == | ||
| + | === Особенности реализации последовательного алгоритма === | ||
| + | === Локальность данных и вычислений === | ||
| + | ==== Локальность реализации алгоритма ==== | ||
| + | ===== Структура обращений в память и качественная оценка локальности ===== | ||
| + | ===== Количественная оценка локальности ===== | ||
| + | === Возможные способы и особенности параллельной реализации алгоритма === | ||
| + | === Масштабируемость алгоритма и его реализации === | ||
| + | ==== Масштабируемость алгоритма ==== | ||
| + | ==== Масштабируемость реализации алгоритма ==== | ||
| + | === Динамические характеристики и эффективность реализации алгоритма === | ||
| + | === Выводы для классов архитектур === | ||
| + | === Существующие реализации алгоритма === | ||
Версия 10:23, 20 октября 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=QDV[/math] ([math]Q, V[/math] - унитарные, [math]D[/math] — правая двухдиагональная матрица)[1]. При этом матрицы [math]Q, V[/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]i=n-1[/math]) с помощью преобразования отражения "убираются" ненулевые наддиагональные элементы в [math]i[/math]-м столбце, кроме самого левого из них. Таким образом, после [math]n-1[/math] шагов преобразований получается хессенбергова [math]D[/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].
Аналогично для правых матриц отражений [math]U=E-\frac{1}{\gamma}vv^*[/math] [math]v[/math] находится через координаты текущей [math]i[/math]-й строки так:
[math]s[/math] - вектор размерности [math]n-i[/math], составленный из элементов [math]i[/math]-й строки, начиная с [math]i+1[/math]-го элемента.
Если [math](s,s)=0[/math], то [math]v=e_{i+1}[/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+1[/math], [math]v_{j}=u_{j-i+2}[/math] при [math]j\gt i+1[/math], а [math]v_{i+1}=1[/math], если [math]u_{1}=0[/math] и [math]v_{i+1}=\frac{u_{1}}{|u_{1}|}(1+|u_{1}|)[/math] для остальных значений. При этом [math]\gamma = 1+|u_{1}|[/math].
1.3 Вычислительное ядро алгоритма
Основную часть алгоритма составляют вычисления на каждом шагу скалярных произведений [math](s,s)[/math] и [math](x,v)[/math] для всех подстолбцов [math]x[/math]справа от текущего, а также векторные операции [math]x'=x-\frac{(x,v)}{\gamma}v[/math], и затем вычисления на каждом шагу (кроме шага с номером [math]i=n-1[/math]) скалярных произведений [math](s,s)[/math] и [math](x,v)[/math] для всех подстрок [math]x[/math]снизу от текущей, а также векторные операции [math]x'=x-\frac{(x,v)}{\gamma}v[/math]. Это используется при программировании метода во многих библиотеках для его конструирования из стандартных подпрограмм (например, из BLAS).
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+2n[/math].
1.10 Свойства алгоритма
Вычислительная погрешность в методе отражений (Хаусхолдера) растет линейно, как и в методе Гивенса (вращений).
