The analysis of smoothers for multigrid algorithms

The purpose of this paper is to provide a general technique for defining and analyzing smoothing operators for use in multigrid algorithms. The smoothing operators considered are based on subspace decomposition and include point, line, and block versions of Jacobi and Gauss-Seidel iteration as well as generalizations. We shall show that these smoothers will be effective in multigrid algorithms provided that the subspace decomposition satisfies two simple conditions. In many applications, these conditions are trivial to verify.