Ben Southworth | University of Colorado at Boulder
On Nonsymmetric Algebraic Multigrid Solvers and Hyperbolic PDEs
Algebraic multigrid (AMG) solvers are a class of fast, parallel iterative methods for the solution of large sparse linear systems. AMG is traditionally designed for symmetric positive definite matrices resulting from the discretization of elliptic PDEs, such as the Laplace operator. The discretization of PDEs with hyperbolic character, on the other hand, often results in highly nonsymmetric matrices. Although steady state solutions or implicit treatment in time requires the solution of linear systems, there remains a fundamental lack of fast, parallel solvers amenable to such matrices.
This talk reviews AMG as an iterative method, highlighting why traditional techniques break down in the nonsymmetric setting. Building on this, a new nonsymmetric AMG method based on an approximate ideal restriction (AIR) is introduced. Convergence theory of AIR and details on the parallel implementation are discussed, followed by numerical results demonstrating AIR as an effective tool for the solution of various hyperbolic-type PDEs, such as radiative transport and electron kinetics problems.
Finally, I discuss coarse-grid correction in nonsymmetric AMG as an approximation to an orthogonal projection in some norm. In framing this based on angles between certain subspaces, explicit relations are derived between the multigrid interpolation and restriction operators such that this approximation is exact. I conclude with an overview on the status of nonsymmetric AMG solvers, including application areas where they may offer significant speedups.