Two-level Smoothed Aggregation Methods

This book, that is based on a scientific material of our works [7, 8, 9, 11], is concerned with an improved convergence analysis of our polynomially accelerated two-level method of [4] and the convergence analysis of its modifications proposed here. The analyzed methods are used for solving linear systems with a positive definite matrix. The methods are based on a smoothed aggregation concept where, in order to make small coarse-space sizes possible, we allow for an aggressive coarsening, that is compensated by massive polynomial smoothing. We show that, for a coarse-space characterized by the diameter of the aggregates H and the fine-level space with the mesh size h, it is sufficient to use O(H/h) elementary smoothing steps to compensate the dependence of the convergence rate estimate on the coarsening ratio H/h, and get thereby a convergence rate estimate indepen- dent of the coarse-space size. This feature is not new here; the methods reviewed in [4] belong to this category. In this book, we are interested in a radical improvement of the asymptotic convergence bound with respect to the degree of the smoothing polynomial for certain modifications of the methods presented in [4].