×

Minimizing communication in numerical linear algebra. (English) Zbl 1246.68128

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.

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)
PDFBibTeX XMLCite
Full Text: DOI arXiv