Ballard, Grey; Demmel, James; Holtz, Olga; Schwartz, Oded Minimizing communication in numerical linear algebra. (English) Zbl 1246.68128 SIAM J. Matrix Anal. Appl. 32, No. 3, 866-901 (2011). The costs of an algorithm consist of computation costs of arithmetic operations and of communication costs which occur either by moving data between different levels of the memory hierarchy or over the network connecting processors of a parallel platform. The article concentrates on the communication costs and assumes that these costs are given by the amount of data moved in a specific algorithm. More precisely, the numbers of load and store operations are considered and lower bounds for this number are derived. As mentioned in the article, the result is an extension of the works by Hong and Kung in 1981, which proved lower bounds for a dense \(n\)-by-\(n\) matrix multiplication, and by Irony, Toledo, and Tiskin in 2004, which has treated the parallel case. These results are generalized in this article and applied to a wider range of linear algebra algorithms, including LU factorization, Cholesky factorization, QR factorization, or Gram-Schmidt algorithm. Also, lower bounds of the costs for the composition of linear algebra algorithms are considered and it is shown how, in case that several versions exist, the better one can be chosen for optimization purposes. Reviewer: Gudula Rünger (Chemnitz) Cited in 30 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68W10 Parallel algorithms in computer science 68W15 Distributed algorithms 68W40 Analysis of algorithms 65Y05 Parallel numerical computation 65Y10 Numerical algorithms for specific classes of architectures 65Y20 Complexity and performance of numerical algorithms 65F30 Other matrix algorithms (MSC2010) Keywords:linear algebra algorithms; communication cost; lower bound; load and store operations; matrix multiplication; LU factorization; sparse Cholesky factorization; QR factorization Software:BLAS; ScaLAPACK; POOCLAPACK; SBR Toolbox; LAPACK; OSKI PDFBibTeX XMLCite \textit{G. Ballard} et al., SIAM J. Matrix Anal. Appl. 32, No. 3, 866--901 (2011; Zbl 1246.68128) Full Text: DOI arXiv