A QR-Based Solver for Rank Structured Matrices

Abstract

In this paper we show how to compute the QR-factorization of a rank structured matrix in an efficient way by means of the Givens-weight representation. We also show how the QR-factorization can be used as a preprocessing step for the solution of linear systems. Provided the representation is chosen in an appropriate manner, the complexity of the QR-factorization is $O((ar^2+brs+cs^2)n)$ operations, where n is the matrix size, r is some measure for the average rank of the rank structure, s is some measure for the bandwidth of the unstructured matrix part around the main diagonal, and $a,b,c\in \mathbb{R}$ are certain weighting parameters. The complexity of the solution of the linear system with given QR-factorization is then only $O((dr+es)n)$ operations for suitable $d,e\in \mathbb{R}$. The performance of this scheme will be demonstrated by some numerical experiments.