Accession Number:

ADA555879

Title:

Avoiding Communication in Two-Sided Krylov Subspace Methods

Descriptive Note:

Technical rept.

Corporate Author:

CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Report Date:

2011-08-16

Pagination or Media Count:

55.0

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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE