Algebraic multigrid theory: The symmetric case (Q1821503)

A rigorous two-level theory is developed for general symmetric matrices and nonsymmetric ones using Kaczmarz relations, without assuming any regularity, not even any grid structure of the unknowns. The theory applies to algebraic multigrid processes, as well as to the usual geometric multigrid. It yields realistic estimates and answers to some basic algorithmic questions. The theory helps to rigorize local mode analyses and locally analyze cases where the latter does not apply. A preliminary version appeared in 1983.