The QR Factorization for Banded-Plus-Semiseparable Matrices Is Computable in Linear Complexity
This provides a linear-complexity, stable algorithm for solving linear systems and eigenvalue problems involving BPS matrices, which arise in applications like integral equations and optimal control.
The paper proves that the QR factorization of banded-plus-semiseparable matrices can be computed in optimal linear complexity by preserving structure during Householder reflections, and extends this to the RQ product for eigenvalue computations. Numerical experiments confirm linear complexity and substantial speedups over hierarchical methods.
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. This theoretical result enables the design of stable, linear-complexity algorithms for solving the associated linear systems. For symmetric BPS matrices, we further show that the $RQ$ product -- central to eigenvalue computations via the $QR$ algorithm -- also preserves the BPS structure, leading to a linear-complexity algorithm for each iteration. Numerical experiments validate the optimal linear complexity, confirm high numerical accuracy, and demonstrate 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.