|
|
| Строка 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>.
| |
| − |
| |
| − | === Свойства алгоритма ===
| |
| − |
| |
| − | Вычислительная погрешность в методе отражений (Хаусхолдера) растет ''линейно'', как и в методе Гивенса (вращений).
| |
| − |
| |
| − | == Программная реализация алгоритма ==
| |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − | === Локальность данных и вычислений ===
| |
| − | ==== Локальность реализации алгоритма ====
| |
| − | ===== Структура обращений в память и качественная оценка локальности =====
| |
| − | ===== Количественная оценка локальности =====
| |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | ==== Масштабируемость алгоритма ====
| |
| − | ==== Масштабируемость реализации алгоритма ====
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
| | | | |
| | == Литература == | | == Литература == |
