  FFT, FMM, and multigrid methods are widely used fast and highly scalable
solvers for elliptic PDEs. However, emerging large-scale computing systems are
introducing challenges in comparison to current petascale computers. Recent
efforts (Dongarra et al. 2011) have identified several constraints in the
design of exascale software that includes massive concurrency, resilience
management, exploiting the high performance of heterogeneous systems, energy
efficiency, and utilizing the deeper and more complex memory hierarchy expected
at exascale. In this paper, we perform a model-based comparison of the FFT,
FMM, and multigrid methods in the context of these projected constraints. In
addition, we use performance models to offer predictions about the expected
performance on upcoming exascale system configurations based on current
technology trends.
