A parallel Cholesky algorithm for the solution of symmetric linear systems (Q1774750)

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.