QR и LQ разложения

QR-разложение является наиболее известным представителем семейства ортогональных факторизаций, включающего в себя QR, LQ, RQ и QL разложения. Здесь Q обозначает ортогональную матрицу, а R и L - верхне и нижнетреугольные матрицы соответственно. В пакете ALGLIB реализованы наиболее часто использующиеся разложения: QR и LQ. Эти разложения могут использоваться для решения полной по рангу переопределенной системы линейных уравнений, как промежуточный этап в SVD-разложении матрицы, либо для других задач. QL и RQ разложения имеют меньше применений и в пакете ALGLIB не реализованы.

Содержание

    1 Алгоритм
    2 Быстродействие
    3 Подпрограммы
    4 Manual entries

Алгоритм

Для вычисления QR(LQ)-разложения в пакете ALGLIB используется алгоритм, схожий с реализованным в LAPACK:

матрица A делится на вертикальные блоки, обрабатываемые слева направо
осуществляется QR(LQ) разложение очередного блока. Каждый блок разлагается с использованием Level 2 алгоритма.
блоки, следующие за текущим, обновляются (умножаются на матрицу Qi, полученную в ходе факторизации текущего блока)

Быстродействие

В отличие от алгоритмов треугольной факторизации, входящих в состав ALGLIB, реализация QR(LQ) разложения не является cache oblivious. Тем не менее, даже такой алгоритм может эффективно использовать кэш процессора без специальной настройки (хотя и несколько менее эффективно, чем алгоритмы треугольной факторизации). Алгоритм активно использует ALGLIB BLAS, главным образом - rank-k updates.

С точки зрения быстродействия, решаемые задачи относятся к одному из двух классов:

задачи с квадратными матрицами или прямоугольными матрицами, обе размерности которых велики. Такие задачи решаются наиболее эффективно, т.к. в них наиболее активно используется ALGLIB BLAS, главным образом - оптимизированные операции третьего уровня.
задачи с длинными и узкими прямоугольными матрицами (количество строк много больше количества столбцов). В таких задачах level 3 updates занимают незначительную часть времени (либо вообще отсутствуют), а алгоритм бОльшую часть времени использует BLAS второго уровня. При этом профиль матрицы препятствует разделению задачи на подзадачи меньшего размера, помещающиеся в кэш. Эффективность решения таких задач ниже, чем в первом случае.

Подпрограммы

Пакет ALGLIB содержит подпрограммы для QR(LQ)-разложения как вещественных, так и комплексных матриц. Ниже приведен список вещественных версий подпрограмм:

rmatrixqr и rmatrixlq служат для построения разложения в компактной форме (матрицы Q, R и L перезаписывают матрицу A)
rmatrixqrunpackq и rmatrixlqunpackq служат для извлечения матрицы Q (всей, либо только части)
rmatrixqrunpackr и rmatrixlqunpackl служат для извлечения треугольной матрицы R/L

Комплексные версии подпрограмм имеют аналогичные имена: