Solving Shifted Systems for Quasiseparable Matrices

Abstract

In this paper we develop fast numerical algorithms for solving shifted linear systems with semidefinite quasiseparable matrices. A combination of Givens and hyperbolic plane rotations is used to update the Cholesky-type factorization of the input quasiseparable matrix by determining a factorization of its shifted version of the form $LD{L}^T$, where $L$ is lower triangular and $D$ is a signature matrix. If the shifted matrix is also definite then the Cholesky factorization of the shifted matrix is computed in a stable way by using orthogonal transformations. Since quasiseparability is maintained under diagonal shifting, a fast variant of the updating procedure using computations with generators is also devised. Numerical experiments show the effectiveness and robustness of the proposed algorithm.