Two fast algorithms for solving diagonal-plus-semiseparable linear systems

In this paper we discuss the structure of the factors of a QR- and a URV-factorization of a diagonal-plus -semiseparable matrix. The Q-factor of a QR-factorization has the diagonal-plus-semiseparable structure. The U- and V-factor of a URV-factorization are semiseparable lower Hessenberg orthogonal matrices. The strictly upper triangular part of the R-factor of a QR- and of a URV-factorization is the strictly upper triangular part of a rank-2 matrix. This latter fact provides a tool to construct a fast QR-solver and a fast URV-solver for linear systems of the form (D + S)x = b. c 2003 Elsevier B.V. All rights reserved.