Robust BPX preconditioner for fractional Laplacians on bounded Lipschitz domains

Borthagaray, Juan; Nochetto, Ricardo; Wu, Shuonan; Xu, Jinchao

doi:10.1090/mcom/3857

Robust BPX preconditioner for fractional Laplacians on bounded Lipschitz domains
HTML articles powered by AMS MathViewer

by Juan Pablo Borthagaray, Ricardo H. Nochetto, Shuonan Wu and Jinchao Xu

Math. Comp. 92 (2023), 2439-2473

DOI: https://doi.org/10.1090/mcom/3857

Published electronically: June 9, 2023

HTML | PDF | Request permission

Abstract:

We propose and analyze a robust Bramble-Pasciak-Xu (BPX) preconditioner for the integral fractional Laplacian of order $s\in (0,1)$ on bounded Lipschitz domains. Compared with the standard BPX preconditioner, an additional scaling factor $1-\widetilde {\gamma }^s$, for some fixed $\widetilde {\gamma } \in (0,1)$, is incorporated to the coarse levels. For either quasi-uniform grids or graded bisection grids, we show that the condition numbers of the resulting systems remain uniformly bounded with respect to both the number of levels and the fractional power.

References

Gabriel Acosta and Juan Pablo Borthagaray, A fractional Laplace equation: regularity of solutions and finite element approximations, SIAM J. Numer. Anal. 55 (2017), no. 2, 472–495. MR 3620141, DOI 10.1137/15M1033952
Mark Ainsworth and Christian Glusa, Aspects of an adaptive finite element method for the fractional Laplacian: a priori and a posteriori error estimates, efficient implementation and multigrid solver, Comput. Methods Appl. Mech. Engrg. 327 (2017), 4–35. MR 3725761, DOI 10.1016/j.cma.2017.08.019
M. Ainsworth and C. Glusa, Towards an efficient finite element method for the integral fractional Laplacian on polygonal domains, Contemporary Computational Mathematics-A Celebration of the 80th Birthday of Ian Sloan, Springer, 2018, pp. 17–57.
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
A. Audrito, J.-C. Felipe-Navarro, and X. Ros-Oton, The Neumann problem for the fractional Laplacian: regularity up to the boundary, arXiv Preprint, arXiv:2006.10026, 2020.
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
D. A. Benson, S. W. Wheatcraft, and M. M. Meerschaert, Application of a fractional advection-dispersion equation, Water Resour. Res. 36 (2000), no. 6, 1403–1412.
Jean Bertoin, Lévy processes, Cambridge Tracts in Mathematics, vol. 121, Cambridge University Press, Cambridge, 1996. MR 1406564
Krzysztof Bogdan and Bartłomiej Dyda, The best constant in a fractional Hardy inequality, Math. Nachr. 284 (2011), no. 5-6, 629–638. MR 2663757, DOI 10.1002/mana.200810109
Matteo Bonforte, Alessio Figalli, and Juan Luis Vázquez, Sharp boundary behaviour of solutions to semilinear nonlocal elliptic equations, Calc. Var. Partial Differential Equations 57 (2018), no. 2, Paper No. 57, 34. MR 3773806, DOI 10.1007/s00526-018-1321-2
Andrea Bonito, Juan Pablo Borthagaray, Ricardo H. Nochetto, Enrique Otárola, and Abner J. Salgado, Numerical methods for fractional diffusion, Comput. Vis. Sci. 19 (2018), no. 5-6, 19–46. MR 3893441, DOI 10.1007/s00791-018-0289-y
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
Juan Pablo Borthagaray, Dmitriy Leykekhman, and Ricardo H. Nochetto, Local energy estimates for the fractional Laplacian, SIAM J. Numer. Anal. 59 (2021), no. 4, 1918–1947. MR 4283703, DOI 10.1137/20M1335509
Juan Pablo Borthagaray and Ricardo H. Nochetto, Besov regularity for the Dirichlet integral fractional Laplacian in Lipschitz domains, J. Funct. Anal. 284 (2023), no. 6, Paper No. 109829, 33. MR 4530901, DOI 10.1016/j.jfa.2022.109829
J. P. Borthagaray and R. H. Nochetto, Constructive approximation on graded meshes for the integral fractional Laplacian, arXiv Preprint, arXiv:2109.00451, 2021.
Juan Pablo Borthagaray, Ricardo H. Nochetto, and Abner J. Salgado, Weighted Sobolev regularity and rate of approximation of the obstacle problem for the integral fractional Laplacian, Math. Models Methods Appl. Sci. 29 (2019), no. 14, 2679–2717. MR 4053241, DOI 10.1142/S021820251950057X
Jean Bourgain, Haim Brezis, and Petru Mironescu, Another look at Sobolev spaces, Optimal control and partial differential equations, IOS, Amsterdam, 2001, pp. 439–455. MR 3586796
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
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
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
Zhen-Qing Chen and Renming Song, Two-sided eigenvalue estimates for subordinate processes in domains, J. Funct. Anal. 226 (2005), no. 1, 90–113. MR 2158176, DOI 10.1016/j.jfa.2005.05.004
P. Ciarlet Jr., Analysis of the Scott-Zhang interpolation in the fractional order Sobolev spaces, J. Numer. Math. 21 (2013), no. 3, 173–180. MR 3118443, DOI 10.1515/jnum-2013-0007
Rama Cont and Peter Tankov, Financial modelling with jump processes, Chapman & Hall/CRC Financial Mathematics Series, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2042661
Wolfgang Dahmen and Angela Kunoth, Multilevel preconditioning, Numer. Math. 63 (1992), no. 3, 315–344. MR 1186345, DOI 10.1007/BF01385864
Eleonora Di Nezza, Giampiero Palatucci, and Enrico Valdinoci, Hitchhiker’s guide to the fractional Sobolev spaces, Bull. Sci. Math. 136 (2012), no. 5, 521–573. MR 2944369, DOI 10.1016/j.bulsci.2011.12.004
Maksymilian Dryja and Olof B. Widlund, Multilevel additive methods for elliptic finite element problems, Parallel algorithms for partial differential equations (Kiel, 1990) Notes Numer. Fluid Mech., vol. 31, Friedr. Vieweg, Braunschweig, 1991, pp. 58–69. MR 1167868
Qiang Du, Li Tian, and Xuying Zhao, A convergent adaptive finite element algorithm for nonlocal diffusion and peridynamic models, SIAM J. Numer. Anal. 51 (2013), no. 2, 1211–1234. MR 3045653, DOI 10.1137/120871638
Lawrence C. Evans, Partial differential equations, 2nd ed., Graduate Studies in Mathematics, vol. 19, American Mathematical Society, Providence, RI, 2010. MR 2597943, DOI 10.1090/gsm/019
Markus Faustmann, Jens Markus Melenk, and Dirk Praetorius, Quasi-optimal convergence rate for an adaptive method for the integral fractional Laplacian, Math. Comp. 90 (2021), no. 330, 1557–1587. MR 4273109, DOI 10.1090/mcom/3603
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
Heiko Gimperlein and Jakub Stocek, Space-time adaptive finite elements for nonlocal parabolic variational inequalities, Comput. Methods Appl. Mech. Engrg. 352 (2019), 137–171. MR 3948751, DOI 10.1016/j.cma.2019.04.019
Heiko Gimperlein, Jakub Stocek, and Carolina Urzúa-Torres, Optimal operator preconditioning for pseudodifferential boundary problems, Numer. Math. 148 (2021), no. 1, 1–41. MR 4265897, DOI 10.1007/s00211-021-01193-9
M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), no. 2, 163–180. MR 1324736, DOI 10.1007/s002110050115
Pierre Grisvard, Elliptic problems in nonsmooth domains, Classics in Applied Mathematics, vol. 69, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. Reprint of the 1985 original [ MR0775683]; With a foreword by Susanne C. Brenner. MR 3396210, DOI 10.1137/1.9781611972030.ch1
Gerd Grubb, Fractional Laplacians on domains, a development of Hörmander’s theory of $\mu$-transmission pseudodifferential operators, Adv. Math. 268 (2015), 478–528. MR 3276603, DOI 10.1016/j.aim.2014.09.018
Michael Karkulik and Jens Markus Melenk, $\mathcal H$-matrix approximability of inverses of discretizations of the fractional Laplacian, Adv. Comput. Math. 45 (2019), no. 5-6, 2893–2919. MR 4047021, DOI 10.1007/s10444-019-09718-5
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 350177
V. Maz′ya and T. Shaposhnikova, On the Bourgain, Brezis, and Mironescu theorem concerning limiting embeddings of fractional Sobolev spaces, J. Funct. Anal. 195 (2002), no. 2, 230–238. MR 1940355, DOI 10.1006/jfan.2002.3955
William McLean, Strongly elliptic systems and boundary integral equations, Cambridge University Press, Cambridge, 2000. MR 1742312
S. V. Nepomnyaschikh, Decomposition and fictitious domains methods for elliptic boundary value problems, Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Norfolk, VA, 1991) SIAM, Philadelphia, PA, 1992, pp. 62–72. MR 1189564
Ricardo H. Nochetto, Kunibert G. Siebert, and Andreas Veeser, Theory of adaptive finite element methods: an introduction, Multiscale, nonlinear and adaptive approximation, Springer, Berlin, 2009, pp. 409–542. MR 2648380, DOI 10.1007/978-3-642-03413-8_{1}2
Ricardo H. Nochetto and Andreas Veeser, Primer of adaptive finite element methods, Multiscale and adaptivity: modeling, numerics and applications, Lecture Notes in Math., vol. 2040, Springer, Heidelberg, 2012, pp. 125–225. MR 3076038, DOI 10.1007/978-3-642-24079-9
Ricardo H. Nochetto, Tobias von Petersdorff, and Chen-Song Zhang, A posteriori error analysis for a class of integral equations and variational inequalities, Numer. Math. 116 (2010), no. 3, 519–552. MR 2684296, DOI 10.1007/s00211-010-0310-y
P. Oswald, Norm equivalencies and multilevel Schwarz preconditioning for variational problems, Friedrich-Schiller-Univ., 1992.
Xavier Ros-Oton and Joaquim Serra, The Dirichlet problem for the fractional Laplacian: regularity up to the boundary, J. Math. Pures Appl. (9) 101 (2014), no. 3, 275–302 (English, with English and French summaries). MR 3168912, DOI 10.1016/j.matpur.2013.06.003
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
D. W. Sims, E. J. Southall, N. E. Humphries, G. C. Hays, C. J. A. Bradshaw, J. W. Pitchford, A. James, M. Z. Ahmed, A. S. Brierley, M. A. Hindell, et al., Scaling laws of marine predator search behaviour, Nature 451 (2008), no. 7182, 1098–1102.
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
Luc Tartar, An introduction to Sobolev spaces and interpolation spaces, Lecture Notes of the Unione Matematica Italiana, vol. 3, Springer, Berlin; UMI, Bologna, 2007. MR 2328004
Enrico Valdinoci, From the long jump random walk to the fractional Laplacian, Bol. Soc. Esp. Mat. Apl. SeMA 49 (2009), 33–44. MR 2584076
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
Jinchao Xu, Theory of multilevel methods, ProQuest LLC, Ann Arbor, MI, 1989. Thesis (Ph.D.)–Cornell University. MR 2637710
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing 56 (1996), no. 3, 215–235 (English, with English and German summaries). International GAMM-Workshop on Multi-level Methods (Meisdorf, 1994). MR 1393008, DOI 10.1007/BF02238513
Jinchao Xu, An introduction to multigrid convergence theory, Iterative methods in scientific computing (Hong Kong, 1995) Springer, Singapore, 1997, pp. 169–241. MR 1661962
Jinchao Xu, Long Chen, and Ricardo H. Nochetto, Optimal multilevel methods for $H(\textrm {grad})$, $H(\textrm {curl})$, and $H(\textrm {div})$ systems on graded and unstructured grids, Multiscale, nonlinear and adaptive approximation, Springer, Berlin, 2009, pp. 599–659. MR 2648382, DOI 10.1007/978-3-642-03413-8_{1}4
Jinchao Xu and Ludmil Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc. 15 (2002), no. 3, 573–597. MR 1896233, DOI 10.1090/S0894-0347-02-00398-3
Kôsaku Yosida, Functional analysis, Die Grundlehren der mathematischen Wissenschaften, Band 123, Academic Press, Inc., New York; Springer-Verlag, Berlin, 1965. MR 180824
Xuejun Zhang, Multilevel Schwarz methods, Numer. Math. 63 (1992), no. 4, 521–539. MR 1189535, DOI 10.1007/BF01385873
Xuan Zhao, Xiaozhe Hu, Wei Cai, and George Em Karniadakis, Adaptive finite element method for fractional differential equations using hierarchical matrices, Comput. Methods Appl. Mech. Engrg. 325 (2017), 56–76. MR 3693419, DOI 10.1016/j.cma.2017.06.017