Avoiding Communication in Two-Sided Krylov Subspace Methods

Abstract

The cost of an algorithm is a function of both computation, the number of arithmetic operations performed, and communication, the amount of data movement. Communication cost encapsulates both data movement between levels of the memory hierarchy and between processors, and the number of messages in which the data is sent. In terms of performance, communication costs are much greater than computation costs on modern computer architectures, and the gap is only expected to widen in future systems. Therefore, in order to increase the performance of an algorithm, we must turn to strategies to minimize communication rather than try to decrease the number of arithmetic operations. We call this a "communication-avoiding" (CA) approach to algorithmic design.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 16, 2011
Accession Number
ADA555879

Entities

People

  • Erin Carson
  • James Demmel
  • Nicholas Knight

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Chebyshev Polynomials
  • Computational Fluid Dynamics
  • Computations
  • Computer Science
  • Eigenvalues
  • Electrical Engineering
  • Engineering
  • Errors
  • Linear Systems
  • National Security
  • Notation
  • Polynomials
  • Precision
  • Sparse Matrix
  • Two Dimensional

Fields of Study

  • Computer science
  • Engineering

Readers

  • Linear Algebra
  • Systems Analysis and Design
  • Tactical Satellite Communications Systems Engineering.