|
|
| Строка 17: |
Строка 17: |
| В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. | | В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений. |
|
| |
|
| === Математическое описание алгоритма ===
| |
|
| |
| В методе Хаусхолдера для выполнения разложения матрицы в произведение хессенберговой и двух ортогональных используются попеременные умножения слева и справа её текущих модификаций на матрицы Хаусхолдера (отражений).
| |
|
| |
| {{Шаблон:Матрица отражений}}
| |
|
| |
| На <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>.
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| Вычислительная погрешность в методе отражений (Хаусхолдера) растет ''линейно'', как и в методе Гивенса (вращений).
| |
|
| |
| == Программная реализация алгоритма ==
| |
| === Особенности реализации последовательного алгоритма ===
| |
| === Локальность данных и вычислений ===
| |
| ==== Локальность реализации алгоритма ====
| |
| ===== Структура обращений в память и качественная оценка локальности =====
| |
| ===== Количественная оценка локальности =====
| |
| === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| === Масштабируемость алгоритма и его реализации ===
| |
| ==== Масштабируемость алгоритма ====
| |
| ==== Масштабируемость реализации алгоритма ====
| |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
| === Выводы для классов архитектур ===
| |
| === Существующие реализации алгоритма ===
| |
|
| |
|
| == Литература == | | == Литература == |
| Разложение в произведение хессенберговой и двух ортогональных матриц методом Хаусхолдера (отражений)
|
| Последовательный алгоритм
|
| Последовательная сложность
|
[math]\displaystyle{ O(n^3) }[/math]
|
| Объём входных данных
|
[math]\displaystyle{ n^2 }[/math]
|
| Объём выходных данных
|
[math]\displaystyle{ n(n + 2) }[/math]
|
| Параллельный алгоритм
|
| Высота ярусно-параллельной формы
|
[math]\displaystyle{ O(n^2) }[/math]
|
| Ширина ярусно-параллельной формы
|
[math]\displaystyle{ O(n^2) }[/math]
|
Основные авторы описания: А.В.Фролов
Свойства и структура алгоритма
Общее описание алгоритма
Метод Хаусхолдера (в советской математической литературе чаще называется методом отражений) используется для разложения матриц в виде [math]\displaystyle{ A=QDV }[/math] ([math]\displaystyle{ Q, V }[/math] - унитарные, [math]\displaystyle{ D }[/math] — правая двухдиагональная матрица)[1]. При этом матрицы [math]\displaystyle{ Q, V }[/math] хранятся и используются не в своём явном виде, а в виде произведения матриц отражения[2]. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием двух одномерных дополнительных массивов.
В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений.
Литература
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
- ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
