Fast and stable solution of banded-plus-semiseparable linear systems (Q2569768)

The authors propose a new stable algorithm for solving systems of linear equations \({(A+B)x = y}\) with a nonsingular semiseparable \((n \times n)\) matrix \(A\) and a banded matrix \(B\). It is supposed that \(\max\{p,q\} \ll n\), where \(p\) is the lower bandwidth and \(q\) the upper bandwidth. At first, a stable numerical algorithm for computing a triangular factorization of a nonsingular semiseparable matrix \(A\) is developed. The algorithm is based on the Gaussian elimination with partial pivoting and makes use of the structural properties of the inverse matrix \(A^{-1}\). The algorithm requires \(O(n)\) arithmetical operations. Based on this algorithm and the representation \(A+B = A(I + A^{-1}B)\) a procedure for solving systems of equations with a banded-plus-semiseparable matrix is derived. This algorithm has also linear complexity. Finally, the numerical behaviour of the algorithm is illustrated by numerical examples.