Robust norm equivalencies for diffusion problems

Griebel, Michael; Scherer, Karl; Schweitzer, Marc

doi:10.1090/S0025-5718-07-01973-4

Robust norm equivalencies for diffusion problems
HTML articles powered by AMS MathViewer

by Michael Griebel, Karl Scherer and Marc Alexander Schweitzer;

Math. Comp. 76 (2007), 1141-1161

DOI: https://doi.org/10.1090/S0025-5718-07-01973-4

Published electronically: February 7, 2007

PDF | Request permission

Abstract:

Additive multilevel methods offer an efficient way for the fast solution of large sparse linear systems which arise from a finite element discretization of an elliptic boundary value problem. These solution methods are based on multilevel norm equivalencies for the associated bilinear form using a suitable subspace decomposition. To obtain a robust iterative scheme, it is crucial that the constants in the norm equivalence do not depend or depend only weakly on the ellipticity constants of the problem. In this paper we present such a robust norm equivalence for the model problem $- \nabla \omega \nabla u=f$ with a scalar diffusion coefficient $\omega$ in $\Omega \subset \mathbb {R}^2$. Our estimates involve only very weak information about $\omega$, and the results are applicable for a large class of diffusion coefficients. Namely, we require $\omega$ to be in the Muckenhoupt class $A_{1}(\Omega )$, a function class well-studied in harmonic analysis. The presented multilevel norm equivalencies are a main step towards the realization of an optimal and robust multilevel preconditioner for scalar diffusion problems.

References

R. E. Alcouffe, Achi Brandt, J. E. Dendy Jr., and J. W. Painter, The multigrid method for the diffusion equation with strongly discontinuous coefficients, SIAM J. Sci. Statist. Comput. 2 (1981), no. 4, 430–454. MR 639011, DOI 10.1137/0902035
S. Beuchler, R. Schneider, and C. Schwab, Multiresolution Weighted Norm Equivalences and Applications, Tech. Report 02-09, Prepreint–Reihe Sonderforschungsbereich 393 TU Chemnitz, 2002.
Folkmar Bornemann and Harry Yserentant, A basic norm equivalence for the theory of multilevel methods, Numer. Math. 64 (1993), no. 4, 455–476. MR 1213412, DOI 10.1007/BF01388699
Dietrich Braess, Finite elements, 2nd ed., Cambridge University Press, Cambridge, 2001. Theory, fast solvers, and applications in solid mechanics; Translated from the 1992 German edition by Larry L. Schumaker. MR 1827293
James H. Bramble and Jinchao Xu, Some estimates for a weighted $L^2$ projection, Math. Comp. 56 (1991), no. 194, 463–476. MR 1066830, DOI 10.1090/S0025-5718-1991-1066830-3
A. Brandt, Multi-Level Adaptive Technique (MLAT) for Fast Numerical Solution to Boundary Value Problems, Proc. of the Third Int. Conf. on Numerical Methods in Fluid Mechanics, Univ. Paris 1972 (New York, Berlin, Heidelberg) (H. Cabannes and R. Teman, eds.), Springer, 1973.
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
—, Algebraic Multigrid Theory: The Symmetric Case, Preliminary Proceedings for the International Multigrid Conference (Copper Mountain, Colorado), April 1983.
Achi Brandt, Algebraic multigrid theory: the symmetric case, Appl. Math. Comput. 19 (1986), no. 1-4, 23–56. Second Copper Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR 849831, DOI 10.1016/0096-3003(86)90095-0
A. Brandt, S. F. McCormick, and J. W. Ruge, Algebraic Multigrid for Automatic Multigrid Solutions with Application to Geodetic Computations, Technical Report, Institute for Computational Studies, Fort Collins, Colorado, October 1982.
—, Algebraic Multigrid for Sparse Matrix Equations, Sparsity and Its Applications (D. J. Evans, ed.), Cambridge University Press, 1984.
J. E. Dendy Jr., Black box multigrid, J. Comput. Phys. 48 (1982), no. 3, 366–386. MR 684260, DOI 10.1016/0021-9991(82)90057-2
Maksymilian Dryja, Marcus V. Sarkis, and Olof B. Widlund, Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions, Numer. Math. 72 (1996), no. 3, 313–348. MR 1367653, DOI 10.1007/s002110050172
T. Grauschopf, M. Griebel, and H. Regler, Additive multilevel preconditioners based on bilinear interpolation, matrix-dependent geometric coarsening and algebraic multigrid coarsening for second-order elliptic PDEs, Appl. Numer. Math. 23 (1997), no. 1, 63–95. Multilevel methods (Oberwolfach, 1995). MR 1438081, DOI 10.1016/S0168-9274(96)00062-1
W. Hackbusch, Ein iteratives Verfahren zur schnellen Auflösung elliptischer Randwertprobleme, Tech. Report 76-12, Mathematisches Institut, Universität zu Köln, 1976.
—, A Fast Numerical Method for Elliptic Boundary Value Problems with Variable Coefficients, 2nd GAMM-Conf. Numer. Meth. Fl. Mech. (Köln) (E. H. Hirschel and W. Geller, eds.), Deutsche Forschungs- und Versuchsanstalt für Luft- und Raumfahrt, 1977, pp. 50–57.
—, Multi-grid methods and applications, Springer, 1985.
Peter Oswald, On the robustness of the BPX-preconditioner with respect to jumps in the coefficients, Math. Comp. 68 (1999), no. 226, 633–650. MR 1620239, DOI 10.1090/S0025-5718-99-01041-8
J. W. Ruge and K. Stüben, Efficient Solution of Finite Difference and Finite Element Equations by Algebraic Multigrid, Multigrid Methods for Integral and Differential Equations (D. J. Paddon and H. Holstein, eds.), The Institute of Mathematics and its Applications Conference Series, Clarendon Press, 1985.
Elias M. Stein, Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, Princeton Mathematical Series, vol. 43, Princeton University Press, Princeton, NJ, 1993. With the assistance of Timothy S. Murphy; Monographs in Harmonic Analysis, III. MR 1232192
U. Trottenberg, C. W. Osterlee, and A. Schüller, Multigrid, Appendix A: An Introduction to Algebraic Multigrid by K. Stüben, pp. 413–532, Academic Press, San Diego, 2001.
W. L. Wan, Tony F. Chan, and Barry Smith, An energy-minimizing interpolation for robust multigrid methods, SIAM J. Sci. Comput. 21 (1999/00), no. 4, 1632–1649. MR 1756048, DOI 10.1137/S1064827598334277
Joseph Wloka, Partielle Differentialgleichungen, Mathematische Leitfäden. [Mathematical Textbooks], B. G. Teubner, Stuttgart, 1982 (German). Sobolevräume und Randwertaufgaben. [Sobolev spaces and boundary value problems]. MR 652934
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
Jinchao Xu, Counterexamples concerning a weighted $L^2$ projection, Math. Comp. 57 (1991), no. 196, 563–568. MR 1094965, DOI 10.1090/S0025-5718-1991-1094965-8
P. M. de Zeeuw, Matrix-dependent prolongations and restrictions in a blackbox multigrid solver, J. Comput. Appl. Math. 33 (1990), no. 1, 1–27. MR 1081238, DOI 10.1016/0377-0427(90)90252-U
—, Acceleration of Iterative Methods by Coarse Grid Corrections, Ph.D. thesis, University of Amsterdam, 1997.