Department of Computer Science, K.U.Leuven, Leuven, Belgium
TW Reports vol:TW423
In this paper a Levinson-like algorithm is derived for solving symmetric positive deﬁnite semiseparable plus diagonal systems of equations. In a ﬁrst part we solve a Yule-Walker-like system of equations. Based on this O(n) solver an algorithm for a general right-hand side is derived. The new method has a linear complexity and takes 19n − 13 operations. The relation between the algorithm and an upper triangular decomposition of the inverse of the semiseparable plus diagonal matrices is investigated. Numerical experiments are included.