A New Algorithmic Approach to Multigrid-Homogenization

Folkmar Bornemann
Munich University of Technology, Germany


Elliptic boundary value problems with diffusion coefficients that rapidly and strongly vary on fine scales pose severe problems to standard multilevel methods. This is because those methods construct coarse grid operators which do not properly approximate the coarse scale structure of the problem. For instance, even if the fine scale problem is isotropic the coarse scale operator can be anisotropic.

In analogy to the asymptotic case, the construction of well-chosen coarse grid operators is called numerical homogenization. Recently, several researchers discovered that, while standard multilevel methods suffer, the multiscale structure itself is ideally suited for accomplishing that task. In principle, three approaches have been suggested:

  1. Methods based on successive Schur-complements, computable using wavelet bases. However, in this approach the coarse grid operator becomes global and one does not obtain information about effective diffusion matrices.
  2. Methods based on ideas stemming from algebraic multigrid, like matrix-dependent prolongations. These methods can also be viewed as a kind of ILU-localization of the (global) Schur-complement approach. They work correctly for layered materials and certain probability densities. However, there are problems like checkerboard-structures where these methods do nothing better than standard multigrid.
  3. Semi-analytical methods based on asymptotic results. These methods work correctly, however, only for quite a restricted class of problems: diffusion coefficients stemming from periodic media.

By analyzing all these drawbacks the author has realized the importance of conserving from fine to coarse scale those properties which are continuous with respect to the so-called H-convergence of diffusion matrices. This analysis has led to a new, solution-dependent way of constructing coarse grid operators, iteratively within a multigrid cycle. Numerical examples will show the promising features of the new approach.