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

Разложение в произведение хессенберговой и двух ортогональных матриц методом Хаусхолдера (отражений)
Последовательный алгоритм
Последовательная сложность	$O(n^3)$
Объём входных данных	$n^2$
Объём выходных данных	$n(n + 2)$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(n^2)$
Ширина ярусно-параллельной формы	$O(n^2)$

Основные авторы описания: А.В.Фролов

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

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