Algebraic Theory of Two-Grid Methods

Abstract. About thirty years ago, Achi Brandt wrote a seminal paper providing a convergence theory for algebraic multigrid methods [Appl. Math. Comput., 19 (1986), pp. 23–56]. Since then, this theory has been improved and extended in a number of ways, and these results have been used in many works to analyze alge-braic multigrid methods and guide their developments. This paper makes a concise exposition of the state of the art. Results for symmetric and nonsymmetric matrices are presented in a unified way, highlighting the influence of the smoothing scheme on the convergence estimates. Attention is also paid to sharp eigenvalue bounds for the case where one uses a single smoothing step, allowing straightforward ap-plication to deflation-based preconditioners and two-level domain decomposition methods. Some new results are introduced whenever needed to complete the pic-ture, and the material is self-contained thanks to a collection of new proofs, often shorter than the original ones