Разложение Шура квадратной матрицы

Разложением Шура называется представление матрицы A в виде A = S^T T S, где S - ортогональная матрица (матрица векторов Шура), а T - квази-верхнетреугольная матрица, т.е. треугольная матрица с блоками размером 1x1 и 2x2 на главной диагонали.

Данный алгоритм осуществляет разложение Шура произвольной квадратной матрицы с использованием QR-алгоритма с множественными сдвигами. Разложение осуществляется путем приведения матрицы к верхней форме Хессенберга, после чего вызывается алгоритм разложения Шура верхней матрицы Хессенберга. Этот алгоритм является блочно-матричным аналогом обычного QR-алгоритма с двойным сдвигом. Следует отметить, что как и все блочно-матричные алгоритмы, он требует настройки для достижения оптимального быстродействия.

Настройке подвергается величина NS - внутренний параметр подпрограммы InternalSchurDecomposition, определяющий число сдвигов за одну итерацию алгоритма. С ростом числа сдвигов быстродействие алгоритма растет, достигая максимума при NS находящемся между 4 и 16, после чего быстродействие заметно падает. На разных системах границы этого интервала могут различаться, однако в целом тенденция одна и та же. По умолчанию NS установлено в значение, которое достаточно хорошо на большинстве систем, однако если важен даже небольшой прирост быстродействия, имеет смысл провести ручную калибровку этого параметра. Следует отметить, что оптимальное значение параметра зависит как от характеристик системы, так и от свойств обрабатываемых алгоритмом матриц.

Построение разложения Шура осуществляет подпрограмма RMatrixSchur, возвращающая матрицы T и S. Обычно предметом интереса является структура блоков матрицы T, которая может быть легко определена путем изучения поддиагонали главной диагонали матрицы - поскольку все элементы, лежащие ниже блоков, равны 0, то элементы a[i+1,i], равные 0, могут служить индикаторами границы блока.

Алгоритм реализован на основе подпрограммы DHSEQR (библиотека LAPACK 3.0).