A note on the parallel Cholesky factorization of wide banded matrices (Q1124266)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the parallel Cholesky factorization of wide banded matrices |
scientific article |
Statements
A note on the parallel Cholesky factorization of wide banded matrices (English)
0 references
1989
0 references
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.
0 references
symmetric positive definite matrix
0 references
Cholesky factorization
0 references
systolic algorithm
0 references
optimal efficiency
0 references
band matrices
0 references
systolic array
0 references