Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems
type: Item
instance of: scholarly article
title: Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems
zbMATH Open document ID: 0823.65023
author: Marlis Hochbruck
author: Martin H. Gutknecht
published in: Numerische Mathematik
publication date: 1995-10-24T00:00:00Z
review text: The classical Schur and Levinson algorithms compute the columns of the \(U\) factor in an LDU factorization of a Hermitian Toeplitz matrix \(T\) or its inverse, respectively. They break down when \(T\) is not strongly regular, i.e., when not all the leading principal submatrices are nonsingular. Several variants were proposed to deal with the non- Hermitian and the non strongly regular case when exact arithmetic is used. Some of the steps may be ill-conditioned though, leading to unstable algorithms. In this paper, look-ahead steps, searching for only stable operations are proposed. A step is only executed when two successive leading principal submatrices are sufficiently well-conditioned. When the lengths of these steps are bounded, the algorithms require \(O(N^ 2)\) operations for a Toeplitz matrix of size \(N\). Another variant using divide and conquer and fast polynomial arithmetic needs only \(O(N \log^ 2 N)\) operations. In comparison with other look-ahead methods for Toeplitz matrices [cf. e.g. \textit{T. F. Chan} and \textit{P. C. Hansen} [IEEE Trans. Signal Processing 40, No. 5, 1079-1090 (1992; Zbl 0756.65044); \textit{R. W. Freund} and \textit{H. Zha}, Linear Algebra Appl. 188-189, 255-303 (1993; Zbl 0777.65011); \textit{M. H. Gutknecht}, Linear Algebra Appl. 188-189, 351-421 (1993; Zbl 0777.65014)], the stepping condition requiring two successive submatrices to be nonsingular is stronger, resulting in generally larger look-ahead steps.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F05
zbMATH DE Number: 770156
zbMATH Keywords: look-ahead algorithm
zbMATH Keywords: Levinson algorithm
zbMATH Keywords: Schur algorithm
zbMATH Keywords: fast algorithm
zbMATH Keywords: LDU factorization
zbMATH Keywords: Hermitian Toeplitz matrix
zbMATH Keywords: divide and conquer
zbMATH Keywords: fast polynomial arithmetic
MaRDI profile type: Publication
full work available at URL: s002110050116
OpenAlex ID: W1996557319
DOI: 10.1007/S002110050116
Recommended article: Q4261046
Recommended article: An Implementation of the Look-Ahead Lanczos Algorithm for Non-Hermitian Matrices
Recommended article: A Look-Ahead Levinson Algorithm for Indefinite Toeplitz Systems
Recommended article: Q4306797
Recommended article: A look-ahead Levinson algorithm for general Toeplitz systems
Recommended article: Q4327532
Recommended article: Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems
Recommended article: Preconditioners for non-Hermitian Toeplitz systems
Recommended article: Inverse product Toeplitz preconditioners for non-Hermitian Toeplitz systems
Recommended article: Erratum: A Look-Ahead Levinson Algorithm for Indefinite Toeplitz Systems
description: scientific article; zbMATH DE number 770156