Volume 10, pp. 1-20, 2000.

General highly accurate algebraic coarsening

Achi Brandt

Abstract

General purely algebraic approaches for repeated coarsening of deterministic or statistical field equations are presented, including a universal way to gauge and control the quality of the coarse-level set of variables, and generic procedures for deriving the coarse-level set of equations. They apply to the equations arising from variational as well as non-variational discretizations of general, elliptic as well as non-elliptic, partial differential systems, on structured or unstructured grids. They apply to many types of disordered systems, such as those arising in composite materials, inhomogeneous ground flows, “twisted geometry” discretizations and Dirac equations in disordered gauge fields, and also to non-PDE systems. The coarsening can be inexpensive with low accuracy, as needed for multigrid solvers, or more expensive and highly accurate, as needed for other applications (e.g., once-for-all derivation of macroscopic equations). Extensions to non-local and highly indefinite (wave) operators are briefly discussed. The paper re-examines various aspects of algebraic multigrid (AMG) solvers, suggesting some new approaches for relaxation, for interpolation, and for convergence acceleration by recombining iterants. An application to the highly-disordered Dirac equations is briefly reviewed.

Full Text (PDF) [163 KB], BibTeX

Key words

multiscale algorithms, multigrid, algebraic multigrid, AMG, nonlinear AMG, unstructured grids, coarsening, distributive coarsening, homogenization, compatible relaxation, Dirac equations.

AMS subject classifications

35A40, 65F10, 65K10, 65M55, 65N22, 65N55, 65Y05, 76M20.

Links to the cited ETNA articles

[12]	Vol. 6 (1997), pp. 1-34 Achi Brandt: The Gauss Center research in multiscale scientific computation
[19]	Vol. 6 (1997), pp. 162-181 A. Brandt and I. Livshits: Wave-ray multigrid method for standing wave equations
[40]	Vol. 6 (1997), pp. 271-290 T. Washio and C. W. Oosterlee: Krylov subspace acceleration for nonlinear multigrid schemes

ETNA articles which cite this article

Vol. 30 (2008), pp. 323-345 Christian Mense and Reinhard Nabben: On algebraic multilevel methods for non-symmetric systems - convergence results

Vol. 37 (2010), pp. 276-295 J. Brannick, A. Frommer, K. Kahl, S. MacLachlan, and L. Zikatanov: Adaptive reduction-based multigrid for nearly singular and highly disordered physical systems

Vol. 37 (2010), pp. 367-385 David M. Alber and Luke N. Olson: Coarsening invariance and bucket-sorted independent sets for algebraic multigrid

Vol. 44 (2015), pp. 472-496 Achi Brandt, James Brannick, Karsten Kahl, and Irene Livshits: Algebraic distance for anisotropic diffusion problems: multilevel results

Vol. 48 (2018), pp. 348-361 Matthias Bolten, Karsten Kahl, Daniel Kressner, Francisco Macedo, and Sonja Sokolović: Multigrid methods combined with low-rank approximation for tensor-structured Markov chains

< Back