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
Y1 - 2003
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
SN - 1570-1166
VL - 2
SP - 217
EP - 234
JO - Journal of Mathematical Modelling and Algorithms
JF - Journal of Mathematical Modelling and Algorithms
IS - 3
ER -