Adaptive algebraic multigrid coarsening strategies
The rapid increase in the power of today's supercomputers has made it feasible for the scientific community to turn to numerical simulations to model physical phenomena. Partial differential equations (PDEs) provide the mathematical expressions for many of these simulations, including fusion, accelerator design, groundwater and oil reservoirs, and climate. The gap that exists between the microscopic scales at which physical laws are given and the larger scales that these mathematical models typically describe lead to extremely large systems of linear equations.
To solve these large systems, iterative methods have been developed that start with some guess at the unknown solution and continually adjust it to fit the equations in some way. Of the more efficient of these iterative techniques are multilevel (multigrid, multiscale) methods, so called because of their use of several levels of resolution. These levels provide highly efficient representation and computation of the important model features, from very broad to very fine scales. Computing the broad scales is fast and efficient, and it dramatically reduces the need for numerous expensive fine-scale evaluation. As such, multiscale methods have revolutionized numerical simulation by providing fast solvers of physically important classes of equations, thus allowing much more complex models and dramatically reducing the response time of the simulation.
The efficiency of multigrid approaches depends upon the suitability of the hierarchy of coarse-scale equations. Geometric multigrid approaches choose this hierarchy using the geometry of the problem at hand. The so-called algebraic multigrid (AMG) approaches represent an attempt to be more generally applicable by constructing the sequence of coarse-scale equations automatically in a process referred to as the setup. Conventional AMG methods have been shown to be efficient iterative solvers for many of the large and sparse linear systems arising from the discretization of PDEs. However, these approaches rely on assumptions of the nature of the slow-to-converge error of relaxation to construct the coarse-scale equations; which limits their range of applicability. Recent efforts attempt to generalize the process for constructing the coarse-scale equations using adaptive algorithms. These adaptive or self-learning approaches use the method itself to compute these troublesome error components and, then, incorporate them into the solver.
The main goal of this thesis is to extend the applicability of algebraic multigrid algorithms. (Abstract shortened by UMI.)