Уровень алгоритма

Классический точечный метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме: различия между версиями

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

Версия 10:22, 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 Общее описание алгоритма

Метод Хаусхолдера (в советской математической литературе чаще называется методом отражений) используется для разложения матриц в виде [math]A=QDV[/math] ([math]Q, V[/math] - унитарные, [math]D[/math] — правая двухдиагональная матрица)[1]. При этом матрицы [math]Q, V[/math] хранятся и используются не в своём явном виде, а в виде произведения матриц отражения[2]. Каждая из матриц отражения может быть определена одним вектором. Это позволяет в классическом исполнении метода отражений хранить результаты разложения на месте матрицы A с использованием двух одномерных дополнительных массивов.

В данной статье рассматривается именно классическое исполнение, в котором не используются приёмы типа сдваивания при вычислениях скалярных произведений.


2 Литература

  1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
  2. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.