Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement

In this thesis we propose a new algorithm for solving PDEs on massively parallel computers. The Nested Iteration Adaptive Mesh Refinement Range Decomposition (NI-AMRRD) algorithm uses nested iteration and adaptive mesh refinement locally before performing a global communication step. Only a few such steps are observed to be necessary before reaching a solution that is on the order of discretization error. The target application is peta- and exa-scale machines, where traditional parallel numerical PDE communication patterns stifle scalability. The RD algorithm uses a partition of unity to equally distribute the error and thus the work. The computational advantages of this approach are that the decomposed problems can be solved using nested iteration and any multigrid cycle type, with communication needed only a few times when the partitioned solutions are summed. This offers potential advantages in the paradigm of expensive communication but very cheap computation. This thesis introduces the method and explains the details of the communication step. Two performance models are developed, showing that the communication cost associated with a traditional parallel implementation of nested iteration is proportional to log(P)2, whereas the NI-AMR-RD method reduces the communication time to log(P). Numerical results for the Laplace problem with dirichlet boundary conditions demonstrate this enhanced performance