ACA_2 - Automatic Coarse Grid Approximation and Restriction Derivation

Irad Yavneh

Department of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, Israel

Roman Wienands


Abstract

In a companion talk by Roman Wienands, a new automatic coarsening method (ACA_1) is described, that yields robust convergence behavior, while allowing explicit control of the coarse-grid stencil. In this talk we apply this formalism to automatically construct the restriction, as well as the coarse-grid operator. We call this approach ACA_2.

Given prescribed stencils (sparsity patterns) for the restriction and the coarse-grid operator, of sizes $N_R$ and $N_L$, respectively, we choose $N_L+N_R-1$ local basis functions per coarse-grid variable, and construct a restriction and a coarse-grid operator that provide an exact approximation for all functions belonging to the subspace spanned by these basis functions. By pre-computing a unique and sparse set of so-called Canonical Basis Functions (CBFs), the computational effort required for setup is not excessive. The resulting solver is compared with classical Black-Box multigrid (BBox) of Dendy (1982), and with ACA_1 that uses BBox restriction and prolongation, for a suite of diffusion problems with discontinuous coefficients.

We also present an algebraic viewpoint of both ACA_1 and ACA_2. We show that (Petrov)-Galerkin coarsening is in fact a special case of ACA_1, and demonstrate how ACA_1 gains sparsity in return for redundancy. We further describe some preliminary theoretical results, including conditions under which ACA_2 yields an exact solution at the coarse points.