On the Stability of the Bareiss and Related Toeplitz Factorization Algorithms

DOI10.1137/S0895479891221563MaRDI QIDQ4325677zbMATH OpenDBLPWikidataFDO

Authors Richard P. Brent, D. R. Sweet, Adam W. Bojanczyk, F. R. De Hoog

Publication date 5 September 1995

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.5510

zbMATH Keywords

Bareiss algorithmCholesky decompositiondisplacement rank 2elementary downdating stepsfactorization algorithmsLevinson algorithmnumerical experimentsnumerical stabilitysymmetric positive definite matricesToeplitz matrix

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05)

Abstract: This report contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can be expressed as sequences of elementary downdating steps. The stability of the factorization algorithms follows directly from the numerical properties of algorithms for realizing elementary downdating operations. It is shown that the Bareiss algorithm for factorizing a symmetric positive definite Toeplitz matrix is in the class and hence the Bareiss algorithm is stable. Some numerical experiments that compare behavior of the Bareiss algorithm and the Levinson algorithm are presented. These experiments indicate that in general (when the reflection coefficients are not all positive) the Levinson algorithm is not stable; certainly it can give much larger residuals than the Bareiss algorithm.

Recommendations

• Stability of approximate factorization with \(\theta\)-methods
• Stability analysis and fast algorithms for triangulation of Toeplitz matrices
• A look-ahead Bareiss algorithm for general Toeplitz matrices
• A BSP Bareiss algorithm for Toeplitz systems
• Stability Issues in the Factorization of Structured Matrices
• Stability of Methods for Solving Toeplitz Systems of Equations
• A Toeplitz algorithm for polynomial J-spectral factorization
• The weak and strong stability of algorithms in numerical linear algebra
• On the Stability of Relaxed Incomplete Lu Factorizations
• On the stability of splitting schemes and approximate factorization for solving systems of multivariate equations

Cited in

(18)

• Classical foundations of algorithms for solving positive definite Toeplitz equations
• Solving Toeplitz systems after extension and transformation
• A fast approach to stabilize two Toeplitz solvers of the Levinson type
• Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms
• Stability analysis of a general Toeplitz system solver
• Stability and inertia
• Improved bounds for the eigenvalues of prolate spheroidal wave functions and discrete prolate spheroidal sequences
• Finding linearly generated subsequences
• High-performance processing of covariance matrices using GPU computations
• A structured rank-revealing method for Sylvester matrix
• Monotone convex sequences and Cholesky decomposition of symmetric Toeplitz matrices
• Stability Issues in the Factorization of Structured Matrices
• On the acceleration of an algorithm for polynomial factorization
• scientific article; zbMATH DE number 17436 (Why is no real title available?)
• Stable factorization for Hankel and Hankel‐like matrices
• Diagonal pivoting for partially reconstructible Cauchy-like matrices, with applications to Toeplitz-like linear equations and to boundary rational matrix interpolation problems
• Cholesky factorization of semidefinite Toeplitz matrices
• Fast error analysis of continuous GPS observations

This page was built for publication: On the Stability of the Bareiss and Related Toeplitz Factorization Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4325677)