Givens (rotations) method for the QR decomposition of a (real) Hessenberg matrix

Метод Гивенса (в отечественной математической литературе называется также методом вращений) используется для разложения матриц в виде [math]A = QR[/math] ([math]Q[/math] - унитарная, [math]R[/math] — правая треугольная матрица). При этом матрица [math]Q[/math] хранится и используется не в явном виде, а в виде произведения матриц вращения. Каждая из матриц вращения (Гивенса)

может быть определена парой индексов и одним параметром. Поскольку для QR-разложения хессенберговой матрицы нужно "обнулить" только элементы одной диагонали, то, в отличие от стандартной реализации метода Гивенса для плотной квадратной матрицы, для него нужно выполнить всего [math]n-1[/math] операций вращения, то есть этот алгоритм квадратичен по порядку выполняемых операций. Критический путь алгоритма, как и в случае плотных матриц, линеен.

Алгоритм, однако, в своём чистом виде практически не используется. Дело в том, что в QR-алгоритме, где QR-разложения хессенберговых матриц формально используются, для экономии ресурсов они давно применяются в неявном виде, а именно в составе QR-итераций с неявным одинарным сдвигом.