OPERATOR-BASED INTERPOLATION FOR BOOTSTRAP ALGEBRAIC MULTIGRID

Abstract. Bootstrap Algebraic Multigrid (BAMG) is a multigrid-based solver for matrix equa-tions of the form Ax = b. Its aim is to automatically determine the interpolation weights used in algebraic multigrid (AMG) by locally fitting a set of test vectors that have been relaxed as solutions to the corresponding homogeneous equation, Ax = 0, and are then possibly improved later using a multilevel eigensolver. This paper introduces a flexible variant of BAMG that determines the in-terpolation weights indirectly by “collapsing ” the unwanted connections in “operator interpolation”. Compared to BAMG, this indirect BAMG approach (iBAMG) is more in the spirit of classical AMG, which collapses unwanted connections in operator interpolation based on the (restrictive) assumption that smooth error is locally constant. This paper studies the numerical performance of iBAMG and establishes an equivalence, under certain assumptions, between it and a slightly modified (standard) BAMG scheme. To focus on camparing BAMG and iBAMG and exposing their behavior as the problem size grows, the numerical experiments concentrate on Poisson-like scalar problems