Communication-Avoiding Algorithms are reformulations of classical numerical and data-intensive algorithms that minimize data movement (between memory hierarchy levels or between processors) at the cost of additional computation, based on the principle that communication costs (latency + bandwidth) grow faster than computation costs and increasingly dominate execution time on modern hardware.

The energy cost of moving a double-precision number from DRAM to a CPU register (~100 pJ) is 100x the cost of a floating-point multiply (~1 pJ). Between nodes across a network, the ratio is 10,000x. Communication-avoiding algorithms reduce data movement by the maximum amount information-theoretically possible.

Communication Lower Bounds: For matrix-matrix multiplication of n x n matrices, the I/O lower bound (minimum data movement between fast memory of size M and slow memory) is Omega(n^3 / sqrt(M)). Classical algorithms perform O(n^3) communication — sqrt(M) times more than necessary. Communication-optimal algorithms match the lower bound.

Key Communication-Avoiding Algorithms:

s-Step Krylov Methods: Classical Krylov solvers (CG, GMRES) perform one matrix-vector multiply and one or two global reductions (dot products, norms) per iteration — the global reductions synchronize all processes and become the bottleneck at scale. s-step variants compute s iterations' worth of basis vectors before orthogonalizing, reducing global synchronizations by a factor of s. The trade-off: numerical stability decreases with larger s, requiring careful implementation with Newton or Chebyshev polynomials for basis generation.

2.5D Algorithms: Classical 2D parallel algorithms distribute an n x n matrix across P processors in a P^(1/2) x P^(1/2) grid. 2.5D algorithms use c redundant copies of the data, organized in a P^(1/2) x P^(1/2) x c processor grid, reducing communication bandwidth by a factor of c^(1/2) at the cost of c-fold memory overhead. For c = P^(1/3), this achieves the communication lower bound — optimal data movement at the cost of extra memory and redundant computation.

Cache-Oblivious Algorithms: Achieve near-optimal cache behavior without knowing cache sizes, using recursive divide-and-conquer that naturally fits data into any level of the memory hierarchy. Cache-oblivious matrix multiplication recursively divides matrices into quadrants until they fit in L1 cache, achieving O(n^3 / sqrt(M)) cache misses at every cache level simultaneously — communication-optimal without cache-size tuning parameters.

Communication-avoiding algorithms represent a fundamental shift in algorithm design priorities — from minimizing arithmetic operations (the classical optimization metric) to minimizing data movement (the actual performance limiter on modern hardware), yielding speedups that increase as the computation-to-communication gap continues to widen with each hardware generation.