Multilevel decompositions and norms for negative order Sobolev spaces

Führer, Thomas

doi:10.1090/mcom/3674

Multilevel decompositions and norms for negative order Sobolev spaces
HTML articles powered by AMS MathViewer

by Thomas Führer HTML | PDF

Math. Comp. 91 (2022), 183-218 Request permission

Abstract:

We consider multilevel decompositions of piecewise constants on simplicial meshes that are stable in $H^{-s}$ for $s\in (0,1)$. Proofs are given in the case of uniformly and locally refined meshes. Our findings can be applied to define local multilevel diagonal preconditioners that lead to bounded condition numbers (independent of the mesh-sizes and levels) and have optimal computational complexity. Furthermore, we discuss multilevel norms based on local (quasi-)projection operators that allow the efficient evaluation of negative order Sobolev norms. Numerical examples and a discussion on several extensions and applications conclude this article.

References

Mark Ainsworth, William McLean, and Thanh Tran, The conditioning of boundary element equations on locally refined meshes and preconditioning by diagonal scaling, SIAM J. Numer. Anal. 36 (1999), no. 6, 1901–1932. MR 1712149, DOI 10.1137/S0036142997330809
Mario Arioli and Daniel Loghin, Discrete interpolation norms with applications, SIAM J. Numer. Anal. 47 (2009), no. 4, 2924–2951. MR 2551152, DOI 10.1137/080729360
Trygve Bærland, Miroslav Kuchta, and Kent-Andre Mardal, Multigrid methods for discrete fractional Sobolev spaces, SIAM J. Sci. Comput. 41 (2019), no. 2, A948–A972. MR 3934111, DOI 10.1137/18M1191488
Jöran Bergh and Jörgen Löfström, Interpolation spaces. An introduction, Grundlehren der Mathematischen Wissenschaften, No. 223, Springer-Verlag, Berlin-New York, 1976. MR 0482275, DOI 10.1007/978-3-642-66451-9
Stefano Berrone, Andrea Bonito, Rob Stevenson, and Marco Verani, An optimal adaptive fictitious domain method, Math. Comp. 88 (2019), no. 319, 2101–2134. MR 3957888, DOI 10.1090/mcom/3414
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
Folkmar A. Bornemann, Interpolation spaces and optimal multilevel preconditioners, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 3–8. MR 1312371, DOI 10.1090/conm/180/01950
James H. Bramble, Joseph E. Pasciak, and Panayot S. Vassilevski, Computational scales of Sobolev norms with application to preconditioning, Math. Comp. 69 (2000), no. 230, 463–480. MR 1651742, DOI 10.1090/S0025-5718-99-01106-0
Carsten Burstedde, On the numerical evaluation of fractional Sobolev norms, Commun. Pure Appl. Anal. 6 (2007), no. 3, 587–605. MR 2318290, DOI 10.3934/cpaa.2007.6.587
Claudio Canuto, Anita Tabacco, and Karsten Urban, The wavelet element method. I. Construction and analysis, Appl. Comput. Harmon. Anal. 6 (1999), no. 1, 1–52. MR 1664902, DOI 10.1006/acha.1997.0242
S. N. Chandler-Wilde, D. P. Hewett, and A. Moiola, Interpolation of Hilbert and Sobolev spaces: quantitative estimates and counterexamples, Mathematika 61 (2015), no. 2, 414–443. MR 3343061, DOI 10.1112/S0025579314000278
Huangxin Chen, Ronald H. W. Hoppe, and Xuejun Xu, Uniform convergence of local multigrid methods for the time-harmonic Maxwell equation, ESAIM Math. Model. Numer. Anal. 47 (2013), no. 1, 125–147. MR 2968698, DOI 10.1051/m2an/2012023
Huangxin Chen, Xuejun Xu, and Weiying Zheng, Local multilevel methods for second-order elliptic problems with highly discontinuous coefficients, J. Comput. Math. 30 (2012), no. 3, 223–248. MR 2928972, DOI 10.4208/jcm.1109-m3401
Long Chen, Ricardo H. Nochetto, and Jinchao Xu, Optimal multilevel methods for graded bisection grids, Numer. Math. 120 (2012), no. 1, 1–34. MR 2885595, DOI 10.1007/s00211-011-0401-4
Wolfgang Dahmen, Helmut Harbrecht, and Reinhold Schneider, Adaptive methods for boundary integral equations: complexity and convergence estimates, Math. Comp. 76 (2007), no. 259, 1243–1274. MR 2299773, DOI 10.1090/S0025-5718-07-01970-9
A. Ern, T. Gudi, I. Smears, and M. Vohralík, Equivalence of local- and global-best approximations, a simple stable local commuting projector, and optimal hp approximation estimates in H(div), IMA J. Numer. Anal., March 2021, draa103, published online. DOI 10.1093/imanum/draa103
Markus Faustmann, Jens Markus Melenk, and Maryam Parvizi, On the stability of Scott-Zhang type operators and application to multilevel preconditioning in fractional diffusion, ESAIM Math. Model. Numer. Anal. 55 (2021), no. 2, 595–625. MR 4238777, DOI 10.1051/m2an/2020079
Michael Feischl, Thomas Führer, Dirk Praetorius, and Ernst P. Stephan, Optimal additive Schwarz preconditioning for hypersingular integral equations on locally refined triangulations, Calcolo 54 (2017), no. 1, 367–399. MR 3612925, DOI 10.1007/s10092-016-0190-3
Thomas Führer, Alexander Haberl, Dirk Praetorius, and Stefan Schimanko, Adaptive BEM with inexact PCG solver yields almost optimal computational costs, Numer. Math. 141 (2019), no. 4, 967–1008. MR 3923519, DOI 10.1007/s00211-018-1011-1
Thomas Führer and Norbert Heuer, Optimal quasi-diagonal preconditioners for pseudodifferential operators of order minus two, J. Sci. Comput. 79 (2019), no. 2, 1161–1181. MR 3969005, DOI 10.1007/s10915-018-0887-3
Stefan Funken, Dirk Praetorius, and Philipp Wissgott, Efficient implementation of adaptive P1-FEM in Matlab, Comput. Methods Appl. Math. 11 (2011), no. 4, 460–490. MR 2875100, DOI 10.2478/cmam-2011-0026
Dietmar Gallistl, Mira Schedensack, and Rob P. Stevenson, A remark on newest vertex bisection in any space dimension, Comput. Methods Appl. Math. 14 (2014), no. 3, 317–320. MR 3228913, DOI 10.1515/cmam-2014-0013
I. G. Graham, W. Hackbusch, and S. A. Sauter, Finite elements on degenerate meshes: inverse-type inequalities and applications, IMA J. Numer. Anal. 25 (2005), no. 2, 379–407. MR 2126208, DOI 10.1093/imanum/drh017
Helmut Harbrecht and Reinhold Schneider, Biorthogonal wavelet bases for the boundary element method, Math. Nachr. 269/270 (2004), 167–188. MR 2074780, DOI 10.1002/mana.200310171
Norbert Heuer, Additive Schwarz method for the $p$-version of the boundary element method for the single layer potential operator on a plane screen, Numer. Math. 88 (2001), no. 3, 485–511. MR 1835468, DOI 10.1007/s211-001-8012-7
Norbert Heuer, Ernst P. Stephan, and Thanh Tran, Multilevel additive Schwarz method for the $h$-$p$ version of the Galerkin boundary element method, Math. Comp. 67 (1998), no. 222, 501–518. MR 1451325, DOI 10.1090/S0025-5718-98-00926-0
R. Hiptmair, Operator preconditioning, Comput. Math. Appl. 52 (2006), no. 5, 699–706. MR 2275559, DOI 10.1016/j.camwa.2006.10.008
Ralf Hiptmair, Carlos Jerez-Hanckes, and Shipeng Mao, Extension by zero in discrete trace spaces: inverse estimates, Math. Comp. 84 (2015), no. 296, 2589–2615. MR 3378840, DOI 10.1090/mcom/2955
Ralf Hiptmair, Haijun Wu, and Weiying Zheng, Uniform convergence of adaptive multigrid methods for elliptic problems and Maxwell’s equations, Numer. Math. Theory Methods Appl. 5 (2012), no. 3, 297–332. MR 2948766, DOI 10.4208/nmtma.2012.m1128
J.-L. Lions and E. Magenes, Non-homogeneous boundary value problems and applications. Vol. I, Die Grundlehren der mathematischen Wissenschaften, Band 181, Springer-Verlag, New York-Heidelberg, 1972. Translated from the French by P. Kenneth. MR 0350177
Peter Oswald, Multilevel finite element approximation, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, Stuttgart, 1994. Theory and applications. MR 1312165, DOI 10.1007/978-3-322-91215-2
P. Oswald, Multilevel norms for $H^{-1/2}$, Computing 61 (1998), no. 3, 235–255. MR 1660404, DOI 10.1007/BF02684352
P. Oswald, Interface preconditioners and multilevel extension operators, Eleventh International Conference on Domain Decomposition Methods (London, 1998) DDM.org, Augsburg, 1999, pp. 97–104. MR 1827414
J. Peetre, A theory of interpolation of normed spaces, Notas de Matemática, No. 39, Instituto de Matemática Pura e Aplicada, Conselho Nacional de Pesquisas, Rio de Janeiro, 1968. MR 0243340
Gregor Schmidlin and Christoph Schwab, Wavelet Galerkin BEM on unstructured meshes by aggregation, Multiscale and multiresolution methods, Lect. Notes Comput. Sci. Eng., vol. 20, Springer, Berlin, 2002, pp. 359–378. MR 1928575, DOI 10.1007/978-3-642-56205-1_{1}2
L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483–493. MR 1011446, DOI 10.1090/S0025-5718-1990-1011446-7
Rob Stevenson, Piecewise linear (pre-)wavelets on non-uniform meshes, Multigrid methods V (Stuttgart, 1996) Lect. Notes Comput. Sci. Eng., vol. 3, Springer, Berlin, 1998, pp. 306–319. MR 1727799, DOI 10.1007/978-3-642-58734-4_{1}8
Rob Stevenson, Stable three-point wavelet bases on general meshes, Numer. Math. 80 (1998), no. 1, 131–158. MR 1642527, DOI 10.1007/s002110050363
Rob Stevenson, The completion of locally refined simplicial partitions created by bisection, Math. Comp. 77 (2008), no. 261, 227–241. MR 2353951, DOI 10.1090/S0025-5718-07-01959-X
Rob Stevenson and Raymond van Venetië, Uniform preconditioners for problems of negative order, Math. Comp. 89 (2020), no. 322, 645–674. MR 4044445, DOI 10.1090/mcom/3481
Rob Stevenson and Raymond van Venetië, Uniform preconditioners for problems of positive order, Comput. Math. Appl. 79 (2020), no. 12, 3516–3530. MR 4094780, DOI 10.1016/j.camwa.2020.02.009
Rob Stevenson and Raymond van Venetië, Uniform preconditioners of linear complexity for problems of negative order, Comput. Methods Appl. Math. 21 (2021), no. 2, 469–478. MR 4235816, DOI 10.1515/cmam-2020-0052
Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
Thanh Tran and Ernst P. Stephan, Additive Schwarz methods for the $h$-version boundary element method, Appl. Anal. 60 (1996), no. 1-2, 63–84. MR 1623443, DOI 10.1080/00036819608840418
Hans Triebel, Interpolation theory, function spaces, differential operators, North-Holland Mathematical Library, vol. 18, North-Holland Publishing Co., Amsterdam-New York, 1978. MR 503903
Haijun Wu and Zhiming Chen, Uniform convergence of multigrid V-cycle on adaptively refined finite element meshes for second order elliptic problems, Sci. China Ser. A 49 (2006), no. 10, 1405–1429. MR 2287269, DOI 10.1007/s11425-006-2005-5
Jinbiao Wu and Hui Zheng, Uniform convergence of multigrid methods for adaptive meshes, Appl. Numer. Math. 113 (2017), 109–123. MR 3588590, DOI 10.1016/j.apnum.2016.11.005