An algebraic multilevel method for anisotropic elliptic equations based on subgraph matching

This paper presents a strength of connection measure for algebraic multilevel algorithms for a class of linear systems corresponding to the graph Laplacian on a general graph. The coarsening in the multilevel algorithm is based on partitioning in subgraphs (using matching) of the underlying graph. Our idea is to define a local measure of the quality of the matching that follows from a commutative diagram we introduce, whose maximum gives an upper bound on the stability (energy seminorm) of the orthogonal projection on the coarse space. As an application, we focus on utilizing this measure as a tool for constructing coarse spaces for anisotropic diffusion problems. Specifically, we consider the diffusion equation with grid aligned as well as non-grid-aligned anisotropies in the diffusion coefficient and show that the strength of connection measure is able to appropriately capture the correct anisotropic behavior in both cases. We then study a coarsening algorithm that uses this measure in a greedy strategy to find the subgraph partitioning (set of aggregates). The process forms an initial set of subgraphs, each consisting of a single vertex, and then adds vertices to these subgraphs corresponding to the local direction of the anisotropy as determined by the proposed measure.