next up previous
Next: About this document ...

David Appelhans
Multi-level Range Decomposition for Massively Parallel Machines

1355 Agape Way
Lafayette
CO 80026
dappelha@gmail.com

Multi-level Range Decomposition eliminates the 1-to-1 communications necessary at ever level of traditional parallel multigrid implementations, substituting a single all-to-all communication and a small amount of extra local computation. Range decomposition uses a partition of unity to assign each processor a forcing function that is zero outside of the processor's region of interest. Decomposing the range instead of the domain allows the functional, and thus the work, to be equally distributed among processors a priori. Leveraging FOSLS and adaptive mesh refinement, each processor independently solves the decomposed system on an optimal sub-mesh which is global but has relatively few elements outside of a processors region of interest. The sum of such solutions from each processor represents the solution to the global problem. The computational advantages of this approach are that complicated cycle types such as w-cycles can be used with no communication penalty, and the decomposed problems can be solved in parallel without any communication until the solutions need to be summed. This offers potential advantages in the paradigm of expensive communication but very cheap computation. Convergence to within a small multiple of discretization error within one to two iterations is demonstrated for several elliptic first order system (FOSLS) test problems.




next up previous
Next: About this document ...
Copper Mountain 2014-02-23