Stanford University location:Stanford, CA, USA date:May 25, 2006
In this talk we will derive a Levinson-type solver for systems of equations. The class of matrices admitting this solver will be named simple (p_1,p_2)-Levinson conform and they admit an order O(p_1p_2n) solver. The derived solver is based on the Levinson algorithm, which is used for solving strongly nonsingular Toeplitz systems. The solver is constructed in a similar way as the solver for Toeplitz systems: firstly a Yule-Walker-like equation needs to be solved, and secondly this solution is used for solving a linear equation with an arbitrary right-hand side. Various examples will be presented, including different types of matrices. For example, semiseparable, quasiseparable, higher order semiseparable, band matrices, arrowhead matrices, companion matrices, summations of any of the previous matrices,etc.