TY - GEN

T1 - A communication-avoiding parallel algorithm for the symmetric eigenvalue problem

AU - Solomonik, Edgar

AU - Ballard, Grey

AU - Demmel, James

AU - Hoefler, Torsten

N1 - Funding Information:
Grey Ballard was supported by an appointment to the Sandia National Laboratories Truman Fellowship in National Security Science and Engineering, sponsored by Sandia Corporation (a wholly owned subsidiary of Lockheed Martin Corporation) as Operator of Sandia National Laboratories under its U.S. Department of Energy Contract No. DE-AC04-94AL85000. James Demmel was supported by US Dept. of Energy, Office of Science, Office of Advanced Scientific Computing Research, Grant DOE DE-SC0010200, and ASPIRE Lab industrial sponsors and affiliationliates Intel, Google, Hewlett-Packard, Huawei, LGE, NVIDIA, Oracle, and Samsung. Edgar Solomonik was supported by a US. Dept. of Energy Computational Science Graduate Fellowship and an ETH Zurich Postdoctoral Fellowship. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. SPAA ’17, July 24-26, 2017, Washington DC, USA © 2017 Copyright held by the owner/author(s). Publication rights licensed to Association for Computing Machinery. ACM ISBN 978-1-4503-4593-4/17/07...$15.00 https://doi.org/10.1145/3087556.3087561
Publisher Copyright:
© 2017 Copyright held by the owner/author(s).

PY - 2017/7/24

Y1 - 2017/7/24

N2 - Many large-scale scientific computations require eigenvalue solvers in a scaling regime where efficiency is limited by data movement. We introduce a parallel algorithm for computing the eigenvalues of a dense symmetric matrix, which performs asymptotically less communication than previously known approaches. We provide analysis in the Bulk Synchronous Parallel (BSP) model with additional consideration for communication between a local memory and cache. Given sufficient memory to store c copies of the symmetric matrix, our algorithm requires Θ( √c) less interprocessor communication than previously known algorithms, for any c ≤ p1/3 when using p processors. The algorithm first reduces the dense symmetric matrix to a banded matrix with the same eigenvalues. Subsequently, the algorithm employs successive reduction to O(log p) thinner banded matrices.We employ two newparallel algorithms that achieve lower communication costs for the full-to-band and band-to-band reductions. Both of these algorithms leverage a novel QR factorization algorithm for rectangular matrices.

AB - Many large-scale scientific computations require eigenvalue solvers in a scaling regime where efficiency is limited by data movement. We introduce a parallel algorithm for computing the eigenvalues of a dense symmetric matrix, which performs asymptotically less communication than previously known approaches. We provide analysis in the Bulk Synchronous Parallel (BSP) model with additional consideration for communication between a local memory and cache. Given sufficient memory to store c copies of the symmetric matrix, our algorithm requires Θ( √c) less interprocessor communication than previously known algorithms, for any c ≤ p1/3 when using p processors. The algorithm first reduces the dense symmetric matrix to a banded matrix with the same eigenvalues. Subsequently, the algorithm employs successive reduction to O(log p) thinner banded matrices.We employ two newparallel algorithms that achieve lower communication costs for the full-to-band and band-to-band reductions. Both of these algorithms leverage a novel QR factorization algorithm for rectangular matrices.

UR - http://www.scopus.com/inward/record.url?scp=85027876294&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027876294&partnerID=8YFLogxK

U2 - 10.1145/3087556.3087561

DO - 10.1145/3087556.3087561

M3 - Conference contribution

AN - SCOPUS:85027876294

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 111

EP - 121

BT - SPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017

Y2 - 24 July 2017 through 26 July 2017

ER -