TY - JOUR
T1 - Efficient and optimal parallel algorithms for cholesky decomposition
AU - Santos, Eunice E.
AU - Chu, Pei Yue
N1 - Funding Information:
Eunice E. Santos was supported in part by an NSF CAREER Grant.
PY - 2003/12/1
Y1 - 2003/12/1
N2 - In this paper, we consider the problem of developing efficient and optimal parallel algorithms for Cholesky decomposition. We design our algorithms based on different data layouts and methods. We thereotically analyze the run-time of each algorithm. In order to determine the optimality of the algorithms designed, we derive theoretical lower bounds on running time based on initial data layout and compare them against the algorithmic run-times. To address portability, we design our algorithms and perform complexity analysis on the LogP model. Lastly, we implement our algorithms and analyze performance data.
AB - In this paper, we consider the problem of developing efficient and optimal parallel algorithms for Cholesky decomposition. We design our algorithms based on different data layouts and methods. We thereotically analyze the run-time of each algorithm. In order to determine the optimality of the algorithms designed, we derive theoretical lower bounds on running time based on initial data layout and compare them against the algorithmic run-times. To address portability, we design our algorithms and perform complexity analysis on the LogP model. Lastly, we implement our algorithms and analyze performance data.
KW - Algorithms and complexity
KW - Cholesky decomposition
KW - LogP model
KW - Numerical linear algebra
KW - Parallel complexity
UR - http://www.scopus.com/inward/record.url?scp=78049308441&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78049308441&partnerID=8YFLogxK
U2 - 10.1023/B:JMMA.0000015832.41014.ed
DO - 10.1023/B:JMMA.0000015832.41014.ed
M3 - Article
AN - SCOPUS:78049308441
VL - 2
SP - 217
EP - 234
JO - Journal of Mathematical Modelling and Algorithms
JF - Journal of Mathematical Modelling and Algorithms
SN - 1570-1166
IS - 3
ER -