Avoiding Communication in Two-Sided Krylov Subspace Methods

: 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.