A note on the parallel Cholesky factorization of wide banded matrices

DOI10.1016/0167-8191(89)90021-5MaRDI QIDQ1124266zbMATH OpenOpenAlexFDO

Authors John M. Conroy

Publication date 1989

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(89)90021-5

zbMATH Keywords

band matricesCholesky factorizationoptimal efficiencysymmetric positive definite matrixsystolic algorithmsystolic array

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05)

Review text

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.

Recommendations

• Concurrent Cholesky factorization of positive definite banded Hermitian-matrices
• Parallel algorithms for the solution of narrow banded systems
• scientific article; zbMATH DE number 833700
• An Algorithm-by-Blocks for SuperMatrix Band Cholesky Factorization
• scientific article; zbMATH DE number 29780

Cited in

(5)

• scientific article; zbMATH DE number 3850363 (Why is no real title available?)
• The retraction algorithm for factoring banded symmetric matrices
• An Algorithm-by-Blocks for SuperMatrix Band Cholesky Factorization
• Concurrent Cholesky factorization of positive definite banded Hermitian-matrices
• The design, implementation, and evaluation of a symmetric banded linear solver for distributed-memory parallel computers

This page was built for publication: A note on the parallel Cholesky factorization of wide banded matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124266)