Title: A Levinson-like algorithm for symmetric strongly nonsingular higher order semiseparable plus band matrices
Authors: Vandebril, Raf
Mastronardi, Nicola
Van Barel, Marc
Issue Date: Apr-2005
Publisher: Department of Computer Science, K.U.Leuven, Leuven, Belgium
Series Title: TW Reports vol:TW427
Abstract: In this paper we will derive a solver for a symmetric strongly nonsingular higher order generator representable semiseparable plus band matrix. The solver we will derive is based on the Levinson algorithm, which is used for solving strongly nonsingular Toeplitz systems. In a first part an O(p2n) solver for a semiseparable matrix of
semiseparability rank p is derived, and in a second part we derive an O(ln) solver for a band matrix with bandwidth 2l + 1. Both solvers are constructed in a similar way: 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.
Finally a combination of the above methods is presented to solve linear systems with semiseparable plus band coefficient matrices. The overall complexity of this solver is 6(l + p)n^2 plus lower order
terms. In a final section numerical experiments are performed. Attention is paid to the timing and the accuracy of the described methods.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Electrical Engineering - miscellaneous
NUMA, Numerical Analysis and Applied Mathematics Section

Files in This Item:
File Status SizeFormat
TW427.pdf Submitted 223KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.