Communication-Avoiding Algorithms are the algorithmic redesigns that minimize data movement between levels of the memory hierarchy or between processors — achieving provably optimal or near-optimal communication costs that can be asymptotically lower than traditional algorithms, because data movement (not arithmetic) is the dominant cost in modern computing where a FLOP costs ~100x less energy than a DRAM access and ~10,000x less than a network transfer.

Why Communication Dominates

• Communication cost growing relative to compute: Memory bandwidth doubles every ~4 years, compute doubles every ~2 years.
• Bandwidth wall: Gap between compute and communication grows → data movement is THE bottleneck.

Communication Lower Bounds

• For matrix multiplication (C = A × B, N × N matrices):
• Arithmetic: O(N³) FLOPs — any algorithm.
• Sequential communication (between cache of size M and main memory): $\Omega(N^3 / \sqrt{M})$ words.
• Parallel communication (on P processors with M memory each): $\Omega(N^3 / (P \sqrt{M}))$ words + $\Omega(\sqrt{P})$ messages.

Communication-Optimal Matrix Multiply

3D Algorithm (Parallel Matrix Multiply)

• Traditional 2D: P processors, each holds ~N²/P of A, B, C.
• Communication: O(N² / √P) per processor.
• 3D Algorithm: Arrange P processors in P^(1/3) × P^(1/3) × P^(1/3) cube.
• Replicate inputs across layers → each processor computes N³/P of work.
• Communication: O(N² / P^(2/3)) — asymptotically less!
• Tradeoff: Uses 3x the memory (replicated inputs).
• 2.5D Algorithm: Interpolate between 2D and 3D — use available extra memory optimally.

CA-GMRES / CA-CG (Iterative Solvers)

• Traditional Krylov methods (GMRES, CG): Compute one vector per iteration → global synchronization per iteration.
• CA-Krylov: Compute s vectors at once (s-step method) → synchronize once per s iterations.
• s-step CG: Replace s iterations of CG with one block computation → reduce messages by factor s.
• Challenge: Numerical stability degrades with large s → requires careful basis selection.

CA-LU Factorization (Tournament Pivoting)

• Standard LU: Panel factorization requires N sequential pivoting steps → N synchronization points.
• CA-LU (CALU): Tournament pivoting selects pivots in parallel → reduces communication.
• Achieves communication lower bound for LU factorization.

Communication-avoiding algorithms represent a fundamental shift in algorithm design philosophy — by recognizing that data movement, not arithmetic, is the dominant cost, these algorithms achieve orders-of-magnitude speedups on modern hardware, proving that algorithmic innovation remains as important as hardware improvement for advancing computational performance.