A note on the parallel Cholesky factorization of wide banded matrices (Q1124266)

Let A be an \(n\times n\) symmetric positive definite matrix with semibandwidth m. Computing the Cholesky factorization of A \((A=LL^ T)\) by a systolic algorithm, a hexagonal array of \(1/2m(m+1)\) processors, is required. This paper shows that the above algorithm can be mapped onto \(p\times p\) array of processors such that the computation can be performed with near optimal efficiency. Two algorithms for factoring symmetric positive definite band matrices are presented. Both are designed for \(p\times p\) array of processors with local memory with \(p\leq 0(m)\), where m is the semibandwidth of the matrix. The first algorithm is achieved by reflecting or folding a systolic array of \textit{R.P. Brent} and \textit{F. T. Luk} [Computing the Cholesky factorization using a systolic algorithm, in: Proc. 6th Australian Computer Science Conference, Australian Comp. Sci. Comm. 5 (1983)]. In the other one, a torus wrap of the band matrix is used to give an efficient method which allows the matrix to stay in place during the curse of the algorithm. Both algorithms achieve nearly optimal efficiency for matrices whose bandwidth is large relative to the size of processor array. Namely, their efficiency is asymptotically 1.