A parallel Cholesky algorithm for the solution of symmetric linear systems
type: Item
instance of: scholarly article
title: A parallel Cholesky algorithm for the solution of symmetric linear systems
zbMATH Open document ID: 1074.65030
DOI: 10.1155/S0161171204202265
author: Niranjan Chakravarthy
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2005-05-18T00:00:00Z
full work available at URL: https://eudml.org/doc/51767
review text: 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.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 2168684
zbMATH Keywords: Cholesky factorization
zbMATH Keywords: symmetric system
zbMATH Keywords: parallel computation
zbMATH Keywords: Schur algorithm
zbMATH Keywords: Levinson algorithm
zbMATH Keywords: algorithm
MaRDI profile type: Publication
OpenAlex ID: W2028467041
Recommended article: Q3984931
Recommended article: The choleski Q.I.F. algorithm for solving symmetric linear systems
Recommended article: Efficient and optimal parallel algorithms for Cholesky decomposition
Recommended article: A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices
Recommended article: Q4388755
Recommended article: Computational Science – ICCS 2005
Recommended article: A New Class of Parallel Algorithms for Solving Systems of Linear Equations
Recommended article: A multilevel parallel algorithm to solve symmetric Toeplitz linear systems
Recommended article: A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor
Recommended article: Q5201002
description: scientific article; zbMATH DE number 2168684