Algebraic multigrid theory: The symmetric case

摘要

A rigorous two-level theory is developed for general symmetric matrices (and nonsymmetric ones using Kaczmarz relaxation), without assuming any regularity, not even any grid structure of the unknowns. The theory applies to algebraic multigrid (AMG) processes, as well as to the usual (geometric) multigrid. It yields very realistic estimates and precise answers to basic algorithmic questions, such as: In what algebraic sense does Gauss-Seidel (or Jacobi, Kaczmarz, line Gauss-Seidel, etc.) relaxation smooth the error? When is it appropriate to use block relaxation? What algebraic relations must be satisfied by the coarse-to-fine interpolations? What is the algorithmic role of the geometric origin of the problem? The theory helps to rigorize local mode analyses and locally analyze cases where the latter is inapplicable.