×

CALU: A communication optimal LU factorization algorithm. (English) Zbl 1242.65089

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.

MSC:

65F50 Computational methods for sparse matrices
65F05 Direct numerical methods for linear systems and matrix inversion
65Y05 Parallel numerical computation

Software:

mctoolbox; LINPACK; CALU
PDFBibTeX XMLCite
Full Text: DOI