EUVIMEDEUVIMED entdecken
Crossref

Avoiding Communication in Successive Band Reduction

Grey Ballard, James Demmel, Nicholas Knight

ACM Transactions on Parallel Computing · 2015

DOI: 10.1145/2686877 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, 2015. Verfasst von Grey Ballard und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 59 Literaturangaben. Gefördert von: Center for Future Architecture Research, Lockheed Martin Corporation, Sandia National Laboratories.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The running time of an algorithm depends on both arithmetic and communication (i.e., data movement) costs, and the relative costs of communication are growing over time. In this work, we present sequential and distributed-memory parallel algorithms for tridiagonalizing full symmetric and symmetric band matrices that asymptotically reduce communication compared to previous approaches. The tridiagonalization of a symmetric band matrix is a key kernel in solving the symmetric eigenvalue problem for both full and band matrices. In order to preserve structure, tridiagonalization routines use annihilate-and-chase procedures that previously have suffered from poor data locality and high parallel latency cost. We improve both by reorganizing the computation and obtain asymptotic improvements. We also propose new algorithms for reducing a full symmetric matrix to band form in a communication-efficient manner. In this article, we consider the cases of computing eigenvalues only and of computing eigenvalues and all eigenvectors.

Förderung

  • Center for Future Architecture Research
  • Lockheed Martin Corporation
  • Sandia National Laboratories
  • US DOE
  • U.S. Department of Energy Contract
  • Microsoft
  • ParLab
  • DARPA

Zitieren

APA

Ballard, G., Demmel, J., & Knight, N. (2015). Avoiding Communication in Successive Band Reduction. ACM Transactions on Parallel Computing. https://doi.org/10.1145/2686877

Vancouver

Ballard G, Demmel J, Knight N. Avoiding Communication in Successive Band Reduction. ACM Transactions on Parallel Computing. 2015. doi:10.1145/2686877

BibTeX
@article{Ballard2015,
  author = {Ballard, Grey and Demmel, James and Knight, Nicholas},
  title = {Avoiding Communication in Successive Band Reduction},
  journal = {ACM Transactions on Parallel Computing},
  year = {2015},
  doi = {10.1145/2686877}
}
Kostenlos starten →