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.

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Druinsky, Alex; Carlebach, Eyal; Toledo, Sivan: Wilkinson’s inertia-revealing factorization and its application to sparse matrices. (2018)
  2. Grigori, Laura; Cayrols, Sebastien; Demmel, James W.: Low rank approximation of a sparse matrix based on LU factorization with column and row tournament pivoting (2018)
  3. Grigori, Laura: Introduction to communication avoiding algorithms for direct methods of factorization in linear algebra (2017)
  4. Beliakov, Gleb; Matiyasevich, Yuri: A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic (2016)
  5. Grigori, Laura; Moufawad, Sophie: Communication avoiding ILU0 preconditioner (2015)
  6. Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O.: Communication lower bounds and optimal algorithms for numerical linear algebra (2014)
  7. Suzuki, A.; Roux, F.-X.: A dissection solver with kernel detection for symmetric finite element matrices on shared memory computers (2014)
  8. Nakatsukasa, Yuji; Higham, Nicholas J.: Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD (2013)
  9. Demmel, James; Grigori, Laura; Hoemmen, Mark; Langou, Julien: Communication-optimal parallel and sequential QR and LU factorizations (2012)
  10. Grigori, Laura; Demmel, James W.; Xiang, Hua: CALU: A communication optimal LU factorization algorithm (2011)
  11. Grigori, Laura; Boman, Erik G.; Donfack, Simplice; Davis, Timothy A.: Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization (2010)