swMATH ID: 6433
Software Authors: Grigori, Laura; Demmel, James W.; Xiang, Hua
Description: CALU: A communication optimal LU factorization algorithm The authors discussed CALU, a communication avoiding LU factorization algorithm. The main part of the paper focuses on showing that CALU is stable in practice. It is also shown that CALU minimizes communications.
The paper is organized as follows. Section 1 is an introduction. In Section 2 presents the algebra of CALU and the new tournament pivoting scheme. Section 3 is devoted to the stability of CALU. It describes similarities between GEPP and CALU and upper bounds of the growth factor of CALU. Experimental results for random matrices and several special matrices showing that CALU is stable in practice are also presented. In Section 4 two alternative approaches for solving linear systems of LU-like factorization are discussed. In Section 5 parallel and sequential CALU algorithms and their performance models are presented. Section 6 recalls lower bounds on communications and shows that CALU attains them. Finally, Section 7 concludes the paper.
Homepage: http://www.netlib.org/lapack/lawnspdf/lawn226.pdf
Keywords: LU factorization; communication optimal algorithm; numerical stability; parallel computation; numerical examples; tournament pivoting scheme; random matrices
Related Software: SparseMatrix; LAPACK; ScaLAPACK; SUMMA; POOCLAPACK; LINPACK; BLAS; CSparse; SuiteSparseQR; CHOLMOD; SuperLU; PARDISO; HSL; Regularization tools; SuperLU-DIST; METIS; mctoolbox; Algorithm 97; Pochoir; CTF
Referenced in: 11 Publications

Referencing Publications by Year