Parallel solution of symmetric positive definite systems with hyperbolic rotations

DOI10.1016/0024-3795(86)90163-1MaRDI QIDQ1072335zbMATH OpenOpenAlexFDO

Authors Jean-Marc Delosme, Ilse C. F. Ipsen

Publication date 1986

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0024-3795(86)90163-1

zbMATH Keywords

backsubstitutionForward eliminationhyperbolic rotationsparallel solutionToeplitz system

Mathematics Subject Classification ID

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

Review text

An algorithm based on hyperbolic rotations is presented for the solution of linear systems of equations \(Ax=b\), with symmetric positive definite coefficient matrix A. Forward elimination and backsubstitution are replaced by matrix-vector multiplications, rendering the method amenable to implementation on a variety of parallel and vector machines. This method can be simplified and formulated without square roots if A is also Toeplitz; a systolic architecture implementing the resulting recurrence equations is more efficient than previously proposed pipelined Toeplitz system solvers. The hardware count becomes independent of the matrix size if its inverse is banded.

Recommendations

• scientific article; zbMATH DE number 4151711
• A parallel Cholesky algorithm for the solution of symmetric linear systems
• scientific article; zbMATH DE number 49276
• A practical parallel algorithm for solving band symmetric positive definite systems of linear equations
• A parallel algorithm for solving Toeplitz linear systems

Cites work

• A highly concurrent algorithm and pipeleined architecture for solving Toeplitz systems
• A method of matrix inverse triangular decomposition based on contiguous principal submatrices
• scientific article; zbMATH DE number 3845052 (Why is no real title available?)
• scientific article; zbMATH DE number 3744414 (Why is no real title available?)
• scientific article; zbMATH DE number 3628373 (Why is no real title available?)
• scientific article; zbMATH DE number 3892457 (Why is no real title available?)
• Schur Parametrization of Positive Definite Block-Toeplitz Systems
• The Numerical Stability of the Levinson-Durbin Algorithm for Toeplitz Systems of Equations
• Toeplitz matrices with banded inverses

Cited in

(6)

• Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing
• Least squares modifications with inverse factorizations: Parallel implications
• Computing A^ T A-B^ T B=L^ T DL using generalized hyperbolic transformations
• Parallel solution of symmetric positive definite systems based on decomposition into overlapping blocks
• From Bareiss' algorithm to the stable computation of partial correlations
• Computationally efficient cholesky factorization of a covariance matrix with block toeplitz structure

This page was built for publication: Parallel solution of symmetric positive definite systems with hyperbolic rotations

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