Algebraic analysis of aggregation-based multigrid. (Q2889400)

Numerical solution of a system \(Ax=b\) is considered, where \(A\) is large, sparse, symmetric and positive definite. A two-grid scheme using an agglomeration of unknowns into pairwise disjoint sets is studied. In spite of the classical multigrid theory, the numbers of pre- and post-smoothing steps can be different. The quantity \(\mu _X\) in the convergence factor \(1-1/\mu _X\) can be bounded by a product of two parameters, \(\mu _X\leq q\cdot \mu _D\), where \(q\) depends only on a smoother and the approximation property constant \(\mu _D\) depends only on a prolongation matrix \(P\). Moreover, the constant \(\mu _D\) is not greater than the maximum of locally computable (for every aggregate) quantities \(\mu _D^{(k)}\) which can be easily estimated e.g., for problems with a regular grid and piecewise constant coefficients and with \(A\) diagonally dominant. The choice of \(P\) leading to the minimal values of \(\mu _D^{(k)}\) is indicated: the eigenvectors of modified diagonal blocks of \(A\) corresponding to their smallest eigenvalues should be chosen as the nonzero parts of columns of \(P\). As an example, the equation with anisotropic Laplacian on a rectangular grid is studied. The conditions are specified, under which line-wise aggregates are more advantageous than box-wise aggregates.