High performance algorithms for Toeplitz and block Toeplitz matrices

DOI10.1016/0024-3795(95)00649-4MaRDI QIDQ1923158zbMATH OpenOpenAlexFDO

Authors S. Thirumalai, V. Vermaut, K. A. Gallivan, Paul van Dooren

Publication date 7 October 1996

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(95)00649-4

zbMATH Keywords

block Toeplitz matriceshigh performance computingnumerical examplesQR factorization algorithmsSchur algorithms

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Complexity and performance of numerical algorithms (65Y20)

Review text

The authors give several high performance variants of the classical Schur algorithms to factor symmetric block Toeplitz matrices. Specifically, they discuss routines to factor symmetric positive definite, positive semidefinite, and indefinite matrices. QR factorization algorithms for rank deficient matrices are discussed. A variety of numerical examples is also given.

Recommendations

• Fast block Toeplitz orthogonalization
• Fast cholesky factorization algorithm for s. p. d block-Toeplitz matrices
• A fast Cholesky factorization algorithm for symmetric indefinite block-Toeplitz matrices and their inverse matrices
• scientific article; zbMATH DE number 782074
• scientific article; zbMATH DE number 857679

Cites work

• A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms. Part II
• A Look-Ahead Block Schur Algorithm for Toeplitz-Like Matrices
• A Look-Ahead Levinson Algorithm for Indefinite Toeplitz Systems
• A modified direct preconditioner for indefinite symmetric Toeplitz systems
• A Storage-Efficient WY Representation for Products of Householder Transformations
• A Weakly Stable Algorithm for Padé Approximants and the Inversion of Hankel Matrices
• Block Downdating of Least Squares Solutions
• Displacement ranks of matrices and linear equations
• Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
• Fast orthogonal decomposition of rank deficient Toeplitz matrices
• Fast Parallel Algorithms for QR and Triangular Factorization
• Fast Triangular Factorization and Inversion of Hermitian, Toeplitz, and Related Matrices with Arbitrary Rank Profile
• Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems
• FORTRAN subroutines for general Toeplitz systems
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 4215255 (Why is no real title available?)
• scientific article; zbMATH DE number 3981513 (Why is no real title available?)
• scientific article; zbMATH DE number 778080 (Why is no real title available?)
• scientific article; zbMATH DE number 782074 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• Hyperbolic Householder Algorithms for Factoring Structured Matrices
• Hyperbolic householder transformations
• Hyperbolic Householder Transforms
• Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems
• Reduction to Tridiagonal Form and Minimal Realizations
• Stability Issues in the Factorization of Structured Matrices
• The WY Representation for Products of Householder Matrices

Cited in

(27)

• On the computation of the rank of block bidiagonal Toeplitz matrices
• Application of FFT-based algorithms for large-scale universal kriging problems
• A stabilized superfast solver for indefinite Hankel systems
• Kronecker product and SVD approximations in image restoration
• A fast block Hankel solver based on an inversion formula for block Loewner matrices
• A lookahead algorithm for the solution of block Toeplitz systems
• Look-ahead methods for block Hankel systems
• A least squares approach to reduce stable discrete linear systems preserving their stability.
• The ubiquitous Kronecker product
• A fast Hankel solver based on an inversion formula for Loewner matrices
• A superfast method for solving Toeplitz linear least squares problems.
• The generalized Schur algorithm and some applications
• Fast QR factorization of Cauchy-like matrices
• Fast direct solvers for some complex symmetric block Toeplitz linear systems
• A stable parallel algorithm for block tridiagonal Toeplitz-block-Toeplitz linear systems
• A fast Cholesky factorization algorithm for symmetric indefinite block-Toeplitz matrices and their inverse matrices
• Fast cholesky factorization algorithm for s. p. d block-Toeplitz matrices
• A fast algorithm for subspace state-space system identification via exploitation of the displacement structure
• Solving sparse linear systems faster than matrix multiplication
• Randomised subspace system identification: complexities and error bounds
• Fast and scalable FFT-based GPU-accelerated algorithms for block-triangular Toeplitz matrices with application to linear inverse problems governed by autonomous dynamical systems
• Obtaining pseudoinverse solutions with MINRES
• First-order methods for nonnegative trigonometric matrix polynomials
• Acoustic multiple scattering using recursive algorithms
• Sensitivity analysis for Szegő polynomials
• A multilevel parallel algorithm to solve symmetric Toeplitz linear systems
• A unified least squares approach to identify and to reduce continuous asymptotically stable systems

Describes a project that uses

Uses Software

• TOEPLITZ
• toms729gw

This page was built for publication: High performance algorithms for Toeplitz and block Toeplitz matrices

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