Smoothers can have a strong effect on both the convergence rate of a multigrid algorithm and on the cost per iteration. The potential for improvement of convergence is particularly high when the problem being solved is one with strongly varying coefficients, and some smoothers are very expensive when used on a massively parallel computer.
We describe an algorithm for generating a sparse matrix Z that serves very well as a parallel smoother, with nearly optimal convergence rate. Moreover, the algorithm which constructs Z is itself highly parallel, and uses only local information about the sparse matrix A that the multigrid algorithm is inverting.
Our smoother Z is defined by means of a quadrature over the null-space of the projection operator. More specifically, Z is defined to minimize a quadratic functional the main component of which is a quadrature approximation to a weighted L_2 norm of the residual after one iteration. The minimization may be constrained by equations the smoother should satisfy in particular situations. In particular, we usually constrain the smoother to have a given sparsity pattern. This may be taken to be the sparsity pattern of the sparse matrix A, but this is certainly not the only pattern one may wish to consider.
We observe that these quadrature based smoothers are very close to the best smoothers of the same sparsity pattern, and far superior to the more usual sparse smoothers.