A parallel Cholesky algorithm for the solution of symmetric linear systems
Let \(A\) be a symmetric positive definite matrix with Cholesky factorization \(A=\tilde{L}\tilde{L}^T\). If \(L=\tilde{L}^{-1}\), then \(LAL^T=I\). Building up the \(L\) matrix column by column can be done by building up the unit matrix in \(LAL^T=I\) from the top left to the bottom right, i.e., by eliminating all elements in the successive columns of \(A\) below the diagonal and making the diagonal element 1. By symmetry this is then also obtained for the successive rows of \(A\). In combination with a right hand side, this allows to compute the solution vector \(x\) in \(Ax=b\), element by element from top to bottom. In the case of a Toeplitz matrix \(A\), the usual Cholesky method would correspond to the Schur algorithm, and the present one to the Levinson algorithm. This Levinson-like algorithm is then adapted to a block version. If \(N=rn\) is the size of \(A\), then it is considered to be an \(n\times n\) block matrix with blocks of size \(r\). The matrix operations in the algorithm are then executed in parallel by \(r\) processors. An operation count shows that the efficiency of the parallel algorithm is close to 1.
- scientific article; zbMATH DE number 29780
- The choleski Q.I.F. algorithm for solving symmetric linear systems
- Efficient and optimal parallel algorithms for Cholesky decomposition
- A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices
- scientific article; zbMATH DE number 1150503
- The symmetric-Toeplitz linear system problem in parallel
- A New Class of Parallel Algorithms for Solving Systems of Linear Equations
- A multilevel parallel algorithm to solve symmetric Toeplitz linear systems
- A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor
- Parallel methods for solving the linear algebraic systems
- Avoiding the square-root bottleneck in the Choleski factorization of a matrix on a parallel computer
- Parallel Cholesky factorization on a shared-memory multiprocessor
- Parallel solution of symmetric positive definite systems with hyperbolic rotations
- Block-Cholesky for parallel processing
- Explicit parallel block Cholesky algorithms on the CRAY APP
- A parallel-vector algorithm for rapid structural analysis on high-performance computers
- Existence and Stability of Choleski Q.I.F. for Symmetric Linear Systems
- scientific article; zbMATH DE number 4076453 (Why is no real title available?)
- scientific article; zbMATH DE number 29780 (Why is no real title available?)
- A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices
- scientific article; zbMATH DE number 1131773 (Why is no real title available?)
- Parallel solution of hierarchical symmetric positive definite linear systems
- A Cholesky Up- and Downdating Algorithm for Systolic and SIMD Architectures
- The choleski Q.I.F. algorithm for solving symmetric linear systems
- scientific article; zbMATH DE number 6746173 (Why is no real title available?)
- Divide-and-conquer strategy with Cholesky's factorization for inverting symmetric positive definite matrices
- Parallel Cholesky-based reduction for the weighted integer least squares problem
This page was built for publication: A parallel Cholesky algorithm for the solution of symmetric linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1774750)
