University of Colorado
Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.
Degree: PhD, Applied Mathematics, 2017, University of Colorado
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.
Advisors/Committee Members: Thomas A. Manteuffel, Stephen F. McCormick.
Subjects/Keywords: nested iteration; first-order system least-squares; algebraic multigrid; domain decomposition; range decomposition; adaptive mesh refinement; Applied Mathematics; Numerical Analysis and Computation; Partial Differential Equations
to Zotero / EndNote / Reference
APA (6th Edition):
Mitchell, W. (2017). Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. (Doctoral Dissertation). University of Colorado. Retrieved from http://scholar.colorado.edu/appm_gradetds/80
Chicago Manual of Style (16th Edition):
Mitchell, Wayne. “Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.” 2017. Doctoral Dissertation, University of Colorado. Accessed January 21, 2018.
MLA Handbook (7th Edition):
Mitchell, Wayne. “Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.” 2017. Web. 21 Jan 2018.
Mitchell W. Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2018 Jan 21].
Available from: http://scholar.colorado.edu/appm_gradetds/80.
Council of Science Editors:
Mitchell W. Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. [Doctoral Dissertation]. University of Colorado; 2017. Available from: http://scholar.colorado.edu/appm_gradetds/80