Local approximation estimators for algebraic multigrid. (English) Zbl 1037.65131

Summary: In smoothed aggregation algebraic multigrid, the prolongator is defined by smoothing of the output of a simpler tentative prolongator. The weak approximation property for the tentative prolongator is known to give a bound on the convergence factor of the two-level and even multilevel method. It is known how to bound the constants in the weak approximation property when the system matrix is given as the sum of positive semidefinite local matrices. In practice, however, the local matrices are often not known to the solver, or the problem is given in terms of local matrices and additional constraints.
We characterize the matrices that can be decomposed into a sum of local positive semidefinite matrices with only given rows and columns allowed to be nonzero, and we show that such a decomposition may not always exist. We then propose a construction of approximate local matrices that may be used for local estimates. Finally, we show how eliminating the constraints from the local matrices can be used to obtain rigorous bounds.


65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
Full Text: EuDML EMIS