CALU 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: LAPACK; SparseMatrix; ScaLAPACK; MAGMA; PLASMA; MUMPS; SUMMA; POOCLAPACK; LINPACK; BLAS; CHOLMOD; SuperLU; CSparse; SuiteSparseQR; PARDISO; HSL; Regularization tools; SuperLU-DIST; METIS; mctoolbox Cited in: 13 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year CALU: A communication optimal LU factorization algorithm. Zbl 1242.65089Grigori, Laura; Demmel, James W.; Xiang, Hua 2011 all top 5 Cited by 28 Authors 6 Grigori, Laura 4 Demmel, James Weldon 2 Hoemmen, Mark 1 Amestoy, Patrick R. 1 Ballard, Grey M. 1 Beliakov, Gleb 1 Boman, Erik G. 1 Carlebach, Eyal 1 Carson, Erin Claire 1 Cayrols, Sebastien 1 Davis, Timothy Alden 1 Donfack, Simplice 1 Dong, Yijun 1 Druinsky, Alex 1 Higham, Nicholas J. 1 Knight, Nicholas 1 Langou, Julien 1 L’Excellent, Jean-Yves 1 Martinsson, Per-Gunnar 1 Matiyasevich, Yuriĭ Vladimirovich 1 Moufawad, Sophie M. 1 Nakatsukasa, Yuji 1 Rouet, François-Henry 1 Roux, François-Xavier 1 Schwartz, Oded 1 Sid-Lakhdar, Wissam M. 1 Toledo, Sivan 1 Xiang, Hua all top 5 Cited in 7 Serials 5 SIAM Journal on Scientific Computing 1 BIT 1 International Journal for Numerical Methods in Engineering 1 SIAM Journal on Matrix Analysis and Applications 1 Numerical Linear Algebra with Applications 1 Advances in Computational Mathematics 1 Acta Numerica Cited in 5 Fields 13 Numerical analysis (65-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 2 Computer science (68-XX) 1 Combinatorics (05-XX) 1 Number theory (11-XX) Citations by Year