Stability analysis and fast algorithms for triangulation of Toeplitz matrices

DOI10.1007/S002110050268MaRDI QIDQ1358161zbMATH OpenOpenAlexFDO

Authors Haesun Park, Lars Eldén

Publication date 30 June 1997

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002110050268

zbMATH Keywords

algorithmerror analysisfast algorithmsill-conditioned problemsnumerical examplesQR decompositionSchur algorithmstability analysisToeplitz matricestriangulation

Mathematics Subject Classification ID

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

Review text

An algorithm for triangularizing an \(m \times n\) Toeplitz matrix is presented. This algorithm is a generalization of the classical algorithm due to Schur. In the QR decomposition of a Toeplitz matrix the new algorithm produces a more accurate R factor (upper triangular) than other existing fast methods, especially for ill-conditioned problems. In this generalized Schur algorithm, each row of the triangular factor is computed recursively via updating and downdating steps. A forward error analysis shows that the relative accuracy of the computed upper triangular factor is bounded essentially by the square condition number square of the given Toeplitz matrix, like in Cholesky decomposition. Five numerical tests are performed in order to verify the performance of the algorithm.

Recommendations

• A fast but unstable orthogonal triangularization technique for Toeplitz matrices
• scientific article; zbMATH DE number 4030822
• Fast Parallel Algorithms for QR and Triangular Factorization
• Modified Schur algorithm for positive definite Toeplitz matrices
• Stability analysis of a general Toeplitz system solver

Cited in

(11)

• A total least squares method for Toeplitz systems of equations
• Symbiosis between linear algebra and optimization
• A fast but unstable orthogonal triangularization technique for Toeplitz matrices
• Stability analysis of a general Toeplitz system solver
• Modified Schur algorithm for positive definite Toeplitz matrices
• Stability Issues in the Factorization of Structured Matrices
• scientific article; zbMATH DE number 4030822 (Why is no real title available?)
• Condition and Accuracy of Algorithms for Computing Schur Coefficients of Toeplitz Matrices
• On the Stability of the Bareiss and Related Toeplitz Factorization Algorithms
• Characterizations and accurate computations for tridiagonal Toeplitz matrices
• Structured condition numbers of structured Tikhonov regularization problem and their estimations

This page was built for publication: Stability analysis and fast algorithms for triangulation of Toeplitz matrices

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