The QR factorization of a banded-plus-semiseparable matrix is computable in linear complexity with Householder reflections

Abstract

We show that the QR factorization of a banded-plus-semiseparable (BPS) matrix is computable in optimal linear complexity with respect to the discretization size by showing that the intermediate stages of a QR factorization as computed using Householder reflection maintain a specific structure which has optimal storage. While optimal complexity QR factorizations of BPS matrices are known via Given's rotations, our Householder-based framework enables adaptive, partial QR factorizations whose computational cost depends solely on the number of upper-triangularized columns rather than the global matrix size and represents the factors in a format consistent with LAPACK. This allows users to switch to highly optimized dense matrix operations for the final solve, creating a fast hybrid approach. We further deduce that the Compact WY format also has BPS structure and can be computed in optimal complexity. Finally, for symmetric BPS matrices, we show that the reverse $RQ$ product preserves the BPS structure, establishing the algebraic closure of this matrix class under orthogonal similarity transformations and facilitating efficient chain-structured matrix decompositions. Numerical experiments validate the optimal linear complexity, confirm high numerical accuracy, demonstrate excellent computational efficiency via LAPACK integration, and show substantial speedups compared with existing hierarchical approaches. The algorithms have been implemented in an open-source Julia package, providing an efficient and accessible platform for practical use.