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

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.

1. 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, https://doi.org/10.1137/0902035
2. S. Beuchler, R. Schneider, and C. Schwab, Multiresolution Weighted Norm Equivalences and Applications, Tech. Report 02-09, Prepreint-Reihe Sonderforschungsbereich 393 TU Chemnitz, 2002.
3. 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, https://doi.org/10.1007/BF01388699
4. 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
5. James H. Bramble and Jinchao Xu, Some estimates for a weighted 𝐿² projection, Math. Comp. 56 (1991), no. 194, 463–476. MR 1066830, https://doi.org/10.1090/S0025-5718-1991-1066830-3
6. 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.
7. Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, https://doi.org/10.1090/S0025-5718-1977-0431719-X
8. -, Algebraic Multigrid Theory: The Symmetric Case, Preliminary Proceedings for the International Multigrid Conference (Copper Mountain, Colorado), April 1983.
9. 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, https://doi.org/10.1016/0096-3003(86)90095-0
10. 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.
11. -, Algebraic Multigrid for Sparse Matrix Equations, Sparsity and Its Applications (D. J. Evans, ed.), Cambridge University Press, 1984.
12. J. E. Dendy Jr., Black box multigrid, J. Comput. Phys. 48 (1982), no. 3, 366–386. MR 684260, https://doi.org/10.1016/0021-9991(82)90057-2
13. 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, https://doi.org/10.1007/s002110050172
14. 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, https://doi.org/10.1016/S0168-9274(96)00062-1
15. W. Hackbusch, Ein iteratives Verfahren zur schnellen Auflösung elliptischer Randwertprobleme, Tech. Report 76-12, Mathematisches Institut, Universität zu Köln, 1976.
16. -, 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.
17. -, Multi-grid methods and applications, Springer, 1985.
18. 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, https://doi.org/10.1090/S0025-5718-99-01041-8
19. 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.
20. 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
21. 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.
22. 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, https://doi.org/10.1137/S1064827598334277
23. 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
24. Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, https://doi.org/10.1137/1034116
25. Jinchao Xu, Counterexamples concerning a weighted 𝐿² projection, Math. Comp. 57 (1991), no. 196, 563–568. MR 1094965, https://doi.org/10.1090/S0025-5718-1991-1094965-8
26. 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, https://doi.org/10.1016/0377-0427(90)90252-U
27. -, Acceleration of Iterative Methods by Coarse Grid Corrections, Ph.D. thesis, University of Amsterdam, 1997.