2010/11/13 by Grey Ballard, Ballard, Grey, James Demmel +3 · 3 citations
Computer Science · Engineering · #65F15 #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Software (cs.MS) #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Parallel #and Cluster Computing (cs.DC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1011.3077
openalex publication_date 2010/11/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Algorithms have two costs: arithmetic and communication. The latter represents the cost of moving data, either between levels of a memory hierarchy, or between processors over a network. Communication often dominates arithmetic and represents a rapidly increasing proportion of the total cost, so we seek algorithms that minimize communication. In \citeBDHS10 lower bounds were presented on the amount of communication required for essentially all O(n3)-like algorithms for linear algebra, including eigenvalue problems and the SVD. Conventional algorithms, including those currently implemented in (Sca)LAPACK, perform asymptotically more communication than these lower bounds require. In this paper we present parallel and sequential eigenvalue algorithms (for pencils, nonsymmetric matrices, and symmetric matrices) and SVD algorithms that do attain these lower bounds, and analyze their convergence and communication costs.