Robust norm equivalencies for diffusion problems
Authors:
Michael Griebel, Karl Scherer and Marc Alexander Schweitzer
Journal:
Math. Comp. 76 (2007), 1141-1161
MSC (2000):
Primary 65N55, 65F35; Secondary 65N30, 65F10
DOI:
https://doi.org/10.1090/S0025-5718-07-01973-4
Published electronically:
February 7, 2007
MathSciNet review:
2299769
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0096-3003%2886%2990095-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 https://doi.org/10.1016/0021-9991%2882%2990057-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 https://doi.org/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 https://doi.org/10.1016/S0168-9274%2896%2900062-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 https://doi.org/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 https://doi.org/10.1137/S1064827598334277
- Joseph Wloka, Partielle Differentialgleichungen, B. G. Teubner, Stuttgart, 1982 (German). Sobolevräume und Randwertaufgaben. [Sobolev spaces and boundary value problems]; Mathematische Leitfäden. [Mathematical Textbooks]. MR 652934
- Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI https://doi.org/10.1137/1034116
- Jinchao Xu, Counterexamples concerning a weighted $L^2$ projection, Math. Comp. 57 (1991), no. 196, 563–568. MR 1094965, DOI https://doi.org/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 https://doi.org/10.1016/0377-0427%2890%2990252-U
- ---, Acceleration of Iterative Methods by Coarse Grid Corrections, Ph.D. thesis, University of Amsterdam, 1997.
Retrieve articles in Mathematics of Computation with MSC (2000): 65N55, 65F35, 65N30, 65F10
Retrieve articles in all journals with MSC (2000): 65N55, 65F35, 65N30, 65F10
Additional Information
Michael Griebel
Affiliation:
Institut für Numerische Simulation, Universität Bonn, Germany
MR Author ID:
270664
Email:
griebel@ins.uni-bonn.de
Karl Scherer
Affiliation:
Institut für Angewandte Mathematik, Universität Bonn, Germany
Email:
scherer@iam.uni-bonn.de
Marc Alexander Schweitzer
Affiliation:
Institut für Numerische Simulation, Universität Bonn, Germany
Email:
m.a.schweitzer@ins.uni-bonn.de
Keywords:
Norm equivalency,
multilevel method,
preconditioning,
robustness
Received by editor(s):
August 4, 2004
Received by editor(s) in revised form:
August 3, 2006
Published electronically:
February 7, 2007
Additional Notes:
The authors were supported in part by the Sonderforschungsbereich 611 Singuläre Phänomene und Skalierung in Mathematischen Modellen sponsored by the Deutsche Forschungsgemeinschaft.
Article copyright:
© Copyright 2007
American Mathematical Society