Linear complexity parallel algorithms for linear systems of equations with recursive structure

DOI10.1016/0024-3795(87)90113-3zbMath0624.65020MaRDI QIDQ578844

Israel Gohberg, Peter Lancaster, Thomas Kailath, Israel Koltracht

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0024-3795(87)90113-3

zbMATH Keywords

stability; numerical examples; fast algorithms; Hankel matrix; Vandermonde matrix; matrix inversion; Hilbert matrix; recursive structure; triangular factorization; Levinson's algorithm; linear complexity parallel algorithms; strongly regular symmetric Toeplitz matrices; UDL factorization

Mathematics Subject Classification ID

15A09: Theory of matrix inversion and generalized inverses

65Y05: Parallel numerical computation

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

Paired Cauchy matrices, Fast computation of divided differences and parallel Hermite interpolation, Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I: Transformations, On the numerical solution of integral equations with piecewise continuous displacement kernels, A new approach to the rational interpolation problem: The vector case, Parallel and superfast algorithms for Hankel systems of equations, A definiteness test for Hankel matrices and their lower submatrices, Second order parallel algorithms for Fredholm integral equations with continuous displacement kernels, Generalized Schur parameters and the effects of perturbations, Classical foundations of algorithms for solving positive definite Toeplitz equations, Solving Toeplitz systems after extension and transformation, Second order parallel algorithms for piecewise smooth displacement kernels, A Chebychev-Vandermonde solver, Fast QR factorization of Vandermonde matrices, Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms, Convergence analysis for a parallel Jacobi algorithm, Displacement structure of generalized inverse matrices, Newton's iteration for inversion of Cauchy-like and other structured matrices, Displacement-structure approach to polynomial Vandermonde and related matrices, The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices, Generalized Cauchy-Vandermonde matrices, Look-ahead methods for block Hankel systems, Recursive solution of Cauchy-Vandermonde systems of equations, A fast Hankel solver based on an inversion formula for Loewner matrices, Matrix decompositions using displacement rank and classes of commutative matrix algebras, Triangular factors of Cauchy and Vandermonde matrices, Superfast algorithms for Cauchy-like matrix computations and extensions, Efficient algorithm for finding the inverse and the group inverse of FLS \(r\)-circulant matrix, On Computations with Dense Structured Matrices

Cites Work

• New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices
• Numerical solution of integral equations, fast algorithms and Krein- Sobolev equation
• Efficient solution of linear systems of equations with recursive structure
• Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices
• The \(QR\) algorithm for band symmetric matrices
• Displacement ranks of a matrix
• A highly concurrent algorithm and pipeleined architecture for solving Toeplitz systems
• The Numerical Stability of the Levinson-Durbin Algorithm for Toeplitz Systems of Equations
• Simplified Treatment of Integrals of Cauchy Type, the Hilbert Problem and Singular Integral Equations. Appendix: Poincaré-Bertrand Formula
• Solution of Vandermonde systems of equations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item