Optimized look-ahead recurrences for adjacent rows in the Padé table
type: Item
instance of: scholarly article
title: Optimized look-ahead recurrences for adjacent rows in the Padé table
zbMATH Open document ID: 0852.65025
DOI: 10.1007/BF01731983
author: Marlis Hochbruck
author: Martin H. Gutknecht
published in: BIT
publication date: 1996-12-04T00:00:00Z
review text: The recursive solution of a nested set of Toeplitz systems is done by the Levinson or Schur algorithm in the Hermitian positive definite case; by nonsymmetric versions of these when the matrices are non-Hermitian but strongly regular; by look-ahead versions in exact arithmetic and by stable look-ahead versions when numerical rounding occurs. These algorithms compute recursively the solutions on two adjacent rows in a Padé table, that is when the denominator of the rational approximant is increased, keeping the numerator degree constant. Padé approximant should be considered in broad sense, i.e. Padé approximant of a Laurent series or Padé approximant in two points. In the case of a matrix which is not strongly regular, submatrices become singular when a so-called singular block is reached in the Padé table. Jumping over such a block (i.e., finding the solution for the next nonsingular submatrix) with the minimal amount of work can be complicated. Moreover, if the submatrix is nonsingular, but very ill-conditioned, it should be avoided as well because computing a solution there could introduce large rounding errors. Thus recurrences are used which allow to jump over several blocks simultaneously. Algorithms of this type were published before by \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)] by \textit{R. W. Freund} [Numer. Math. 68, No. 1, 35-69 (1994; Zbl 0811.65023)]\ and by the authors [ibid. 70, No. 2, 181-227 (1995; Zbl 0823.65023)]. The optimization mentioned in the title refers to the fact that the present algorithm always takes the smallest possible look-ahead steps. Therefore, it alternates between the Levinson/Schur type algorithm and a sawtooth algorithm. The updating links well-conditioned pairs which are either regular (different neighbouring solutions on a diagonal) or column…
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F05
zbMATH DE Number: 885553
zbMATH Keywords: Padé approximation
zbMATH Keywords: fast algorithm
zbMATH Keywords: Levinson algorithm
zbMATH Keywords: Toeplitz systems
zbMATH Keywords: Schur algorithm
zbMATH Keywords: ill-conditioned
zbMATH Keywords: sawtooth algorithm
zbMATH Keywords: \(LDU\) decompositions
zbMATH Keywords: Toeplitz matrix
MaRDI profile type: Publication
cites work: A look-ahead Levinson algorithm for general Toeplitz systems
cites work: On the non-normal two-point Padé table
cites work: Polynômes orthogonaux formels - applications
cites work: Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems
cites work: A look-ahead Bareiss algorithm for general Toeplitz matrices
cites work: The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
cites work: Stable row recurrences for the Padé table and generically superfast lookahead solvers for non-Hermitian Toeplitz systems
cites work: Look-ahead Levinson- and Schur-type recurrences in the Padé table
cites work: Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems
cites work: Q4261047
full work available at URL: https://doi.org/10.1007/bf01731983
OpenAlex ID: W2005537210
Recommended article: Q4261046
Recommended article: A fast approach to stabilize two Toeplitz solvers of the Levinson type
Recommended article: Q5498431
Recommended article: Q3481150
Recommended article: A look-ahead Levinson algorithm for general Toeplitz systems
Recommended article: A new algorithm for solving Toeplitz systems of equations
Recommended article: On reduced polynomial-based split algorithms
Recommended article: Q4306797
Recommended article: Q3730927
Recommended article: Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems
description: scientific article; zbMATH DE number 885553