Gene Golub Symposium
Generalizing Connectivity in Algebraic Multigrid
Luke Olson, University of Illinois at Urbana-Champaign
An essential ingredient in a successful Algebraic Multigrid (AMG) method is a proper description of the influence of one degree of freedom on another. If the (smooth) error at a particular location strongly depends on the behavior of the error at nearby locations (in the matrix graph), then the degrees of freedom are deemed strongly connected. An accurate designation of the connection strength in the matrix graph is crucial as the coarse set of degrees of freedom and associated intergrid transfer operators are constructed based on this decision.
Classical approaches to the strength of connection consider weights of the matrix graph directly. While this approach is straightforward and reasonably efficient, the application is limited to (near) M-matrices. In this talk, we describe a generalization of the definition of strength of connection by quantifying the connectivity through the evolution of a point source. This perspective is valuable as it encompasses both the classical view of dependence and more recent attempts based on energy.
We present details of the algorithm and numerical evidence for a variety of applications in support of our approach. Specifically, we highlight the integration of our approach in a smoothed aggregation based AMG setting and consider convection driven problems as well as applications in elasticity, both of which classical attempts at a classification of strength fail. Lastly, we also highlight the effectiveness of our approach for more complicated discretizations where classical strength of connection is also unsuccessful. In particular, we comment on the use of high-order and discontinuous elements.
