Title: Solving linear systems with a Levinson-like solver
Authors: Vandebril, Raf ×
Mastronardi, Nicola
Van Barel, Marc #
Issue Date: 2007
Publisher: Kent State Univ. Lib, Kent, OH
Series Title: Electronic Transactions on Numerical Analysis vol:26 pages:243-269
Abstract: In this paper we will present a general framework for solving linear systems of equations. The solver is based on the Levinson-idea for solving Toeplitz systems of equations. We will consider a general class of matrices, defined as the class of simple (p1,p2)-Levinson conform matrices. This class incorporates, for instance, semiseparable, band, companion, arrowhead and many other matrices. For this class, we will derive a solver of complexity O(p1p2n). The system solver is written inductively, and uses in every step k, the solution of a so-called kth order Yule-Walker-like equation. The algorithm obtained first has complexity O(p1p2n2). Based, however on the specific structure of the simple (p1,p2)-Levinson conform matrices, we will be able to further reduce the complexity of the presented method, and get an order O(p1p2n) algorithm. Different examples of matrices are given for this algorithm. Examples are presented for: general dense matrices, upper triangular matrices, higher order generator semiseparable matrices, quasiseparable matrices, Givens-vector representable semiseparable matrices, band matrices, companion matrices, confederate matrices, arrowhead matrices, fellow matrices and many more. Finally, the relation between this method and an upper triangular factorization of the original matrix is given and also details concerning possible look ahead methods are presented.
Description: Full article freely available at the homepage of Electronic Transactions on Numerical Analysis. See enclosed link.
ISSN: 1068-9613
Publication status: published
KU Leuven publication type: IT
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


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

© Web of science