QR factorization of Toeplitz matrices

DOI10.1007/BF01389431MaRDI QIDQ1063382zbMATH OpenOpenAlexFDO

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

Publication date 1986

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/133100

zbMATH Keywords

Cholesky factorizationcomputational complexityleast squaresnumerical stabilityorthogonal factorizationQR factorizationrank-1 modificationSweet's algorithmToeplitz matrix

Mathematics Subject Classification ID

Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

This paper presents a new algorithm for computing the QR factorization of an \(m\times n\) Toeplitz matrix in O(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m-1)\(\times (n-1)\) submatrices of the Toeplitz matrix are identical.

Recommendations

• Fast block Toeplitz orthogonalization
• scientific article; zbMATH DE number 857679
• scientific article; zbMATH DE number 1180525
• Fast Parallel Algorithms for QR and Triangular Factorization
• Fast algorithm for R of QR decomposition of block-Toeplitz matrices

Cites work

• Fast Toeplitz orthogonalization
• scientific article; zbMATH DE number 883145 (Why is no real title available?)
• Methods for Modifying Matrix Factorizations
• Stability of Methods for Solving Toeplitz Systems of Equations
• The Effects of Rounding Error on an Algorithm for Downdating a Cholesky Factorization

Cited in

(25)

• Hybrid algorithm for fast Toeplitz orthogonalization
• An inverse factorization algorithm for linear prediction
• Fast orthogonal decomposition of rank deficient Toeplitz matrices
• The prolate matrix
• A total least squares method for Toeplitz systems of equations
• Toeplitz approximate inverse preconditioner for banded Toeplitz matrices
• A least squares approach to reduce stable discrete linear systems preserving their stability.
• From Bareiss' algorithm to the stable computation of partial correlations
• A superfast method for solving Toeplitz linear least squares problems.
• Stability analysis of a general Toeplitz system solver
• On the sensitivity of generators for the QR factorization of quasiseparable matrices with total nonpositivity
• A limit result concerning the \(QR\) factorization of banded Toeplitz matrices
• Indefinite QR factorization
• A modification to the LINPACK downdating algorithm
• Fast Toeplitz Orthogonalization Using Inner Products
• Asymptotic properties of the QR factorization of banded Hessenberg–Toeplitz matrices
• Fast algorithms for computing QR and Cholesky factors of Toeplitz operators
• Fast inverse Cholesky decomposition for rectangular Toeplitz-block matrix
• Derivation and analysis of fast bilinear algorithms for convolution
• scientific article; zbMATH DE number 5494062 (Why is no real title available?)
• System identification by operatorial cancellation of nonlinear terms and application to a class of Volterra models
• A fast algorithm for \({\mathcal Q}{\mathcal R}^{-1}\) factorization of Toeplitz matrices
• Toeplitz Infinite GMRES for Parameterized Linear Systems
• Fast block Toeplitz orthogonalization
• Some complexity results in parallel matrix-based signal processing

This page was built for publication: QR factorization of Toeplitz matrices

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