Stability Issues in the Factorization of Structured Matrices
Authors:
- Michael StewartMSMichael Stewart
- Paul Van DoorenPDPaul Van Dooren
- 1 January 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 18 (1) , 104-118
Abstract
This paper provides an error analysis of the generalized Schur algorithm of Kailath and Chun [SIAM J. Matrix Anal. Appl., 15 (1994), pp. 114--128]---a class of algorithms which can be used to factorize Toeplitz-like matrices, including block-Toeplitz matrices, and matrices of the form $T^{T}T$, where T is Toeplitz. The conclusion drawn is that if this algorithm is implemented with hyperbolic transformations in the factored form which is well known to provide numerical stability in the context of Cholesky downdating, then the generalized Schur algorithm will be stable. If a more direct implementation of the hyperbolic transformations is used, then it will be unstable. In this respect, the algorithm is analogous to Cholesky downdating; the details of implementation of the hyperbolic transformations are essential for stability. An example which illustrates this instability is given. This result is in contrast to the ordinary Schur algorithm for which an analysis by Bojanczyk, Brent, De Hoog, and Sweet [SIAM J. Matrix Anal. Appl., 16 (1995), pp. 40--57] shows that the sta- bility of the algorithm is not dependent on the implementation of the hyperbolic transformations.
Keywords
This publication has 8 references indexed in Scilit:
- Stability of the Diagonal Pivoting Method with Partial PivotingSIAM Journal on Matrix Analysis and Applications, 1997
- High performance algorithms for Toeplitz and block Toeplitz matricesLinear Algebra and its Applications, 1996
- On the Stability of the Bareiss and Related Toeplitz Factorization AlgorithmsSIAM Journal on Matrix Analysis and Applications, 1995
- Generalized Displacement Structure for Block-Toeplitz, Toeplitz-Block, and Toeplitz-Derived MatricesSIAM Journal on Matrix Analysis and Applications, 1994
- Analysis of the Cholesky decomposition of a semi-definite matrix1990
- A Note on Downdating the Cholesky FactorizationSIAM Journal on Scientific and Statistical Computing, 1987
- QR factorization of Toeplitz matricesNumerische Mathematik, 1986
- The Numerical Stability of the Levinson-Durbin Algorithm for Toeplitz Systems of EquationsSIAM Journal on Scientific and Statistical Computing, 1980