Date of Award
Doctor of Philosophy (PhD)
Thomas A. Manteuffel
Stephen F. McCormick
When solving elliptic partial differential equations (PDE's) multigrid algorithms often provide optimal solvers and preconditioners capable of providing solutions with O(N) computational cost, where N is the number of unknowns. As parallelism of modern super computers continues to grow towards exascale, however, the cost of communication has overshadowed the cost of computation as the next major bottleneck for multigrid algorithms. Typically, multigrid algorithms require O((log P)^2) communication steps in order to solve a PDE problem to the level of discretization accuracy, where P is the number of processors. This has inspired the development of new algorithms that employ novel paradigms for parallelizing PDE problems, and this thesis studies and further develops two such algorithms.
The nested iteration with range decomposition (NIRD) algorithm is known to achieve accuracy similar to that of traditional methods in only a single iteration with log P communication steps for simple elliptic problems. This thesis makes several improvements to the NIRD algorithm and extends its application to a much wider variety of problems, while also examining and updating previously proposed convergence theory and performance models.
The second method studied is the algebraic multigrid with domain decomposition (AMG-DD) algorithm. Though previous work showed only marginal benefits when comparing convergence factors for AMG-DD against standard AMG V-cycles, this thesis studies the potential of AMG-DD as a discretization-accuracy solver. In addition to detailing the first parallel implementation of this algorithm, this thesis also shows new results that study the effect of different AMG coarsening and interpolation strategies on AMG-DD convergence and show some evidence to suggest AMG-DD may achieve discretization accuracy in a fixed number of cycles with O(log P) communication cost even as problem size increases.
Mitchell, Wayne, "Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations" (2017). Applied Mathematics Graduate Theses & Dissertations. 80.