Avoiding Communication in Iterative Linear Algebra k-steps of iterative solver for sparse Ax=b or Ax=λx – Does k SpMVs with A and starting vector – Many such Krylov Subspace Methods Conjugate Gradients (CG), GMRES, Lanczos, Arnoldi, … Goal: minimize communication – Assume matrix well-partitioned – Serial implementation Conventional: O(k) moves of data from slow to fast memory New: O(1) moves of data – optimal – Parallel implementation on p processors Conventional: O(k log p) messages (k SpMV calls, dot prods) New: O(log p) messages - optimal Lots of speed up possible (modeled and measured) – Price: some redundant computation – Challenges: Poor partitioning, Preconditioning, Stability 38
{}