Rate optimality of adaptive finite element methods with respect to overall computational costs

Gantner, Gregor; Haberl, Alexander; Praetorius, Dirk; Schimanko, Stefan

doi:10.1090/mcom/3654

Rate optimality of adaptive finite element methods with respect to overall computational costs
HTML articles powered by AMS MathViewer

by Gregor Gantner, Alexander Haberl, Dirk Praetorius and Stefan Schimanko HTML | PDF

Math. Comp. 90 (2021), 2011-2040 Request permission

Abstract:

We consider adaptive finite element methods for second-order elliptic PDEs, where the arising discrete systems are not solved exactly. For contractive iterative solvers, we formulate an adaptive algorithm which monitors and steers the adaptive mesh-refinement as well as the inexact solution of the arising discrete systems. We prove that the proposed strategy leads to linear convergence with optimal algebraic rates. Unlike prior works, however, we focus on convergence rates with respect to the overall computational costs. In explicit terms, the proposed adaptive strategy thus guarantees quasi-optimal computational time. In particular, our analysis covers linear problems, where the linear systems are solved by an optimally preconditioned CG method as well as nonlinear problems with strongly monotone nonlinearity which are linearized by the so-called Zarantonello iteration.

References

Mark Ainsworth and J. Tinsley Oden, A posteriori error estimation in finite element analysis, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2000. MR 1885308, DOI 10.1002/9781118032824
Mario Amrein and Thomas P. Wihler, Fully adaptive Newton-Galerkin methods for semilinear elliptic partial differential equations, SIAM J. Sci. Comput. 37 (2015), no. 4, A1637–A1657. MR 3365566, DOI 10.1137/140983537
Mario Arioli, Emmanuil H. Georgoulis, and Daniel Loghin, Stopping criteria for adaptive finite element solvers, SIAM J. Sci. Comput. 35 (2013), no. 3, A1537–A1559. MR 3068564, DOI 10.1137/120867421
Roland Becker, Shipeng Mao, and Zhongci Shi, A convergent nonconforming adaptive finite element method with quasi-optimal complexity, SIAM J. Numer. Anal. 47 (2010), no. 6, 4639–4659. MR 2595052, DOI 10.1137/070701479
Liudmila Belenki, Lars Diening, and Christian Kreuzer, Optimality of an adaptive finite element method for the $p$-Laplacian equation, IMA J. Numer. Anal. 32 (2012), no. 2, 484–510. MR 2911397, DOI 10.1093/imanum/drr016
Alex Bespalov, Alexander Haberl, and Dirk Praetorius, Adaptive FEM with coarse initial mesh guarantees optimal convergence rates for compactly perturbed elliptic problems, Comput. Methods Appl. Mech. Engrg. 317 (2017), 318–340. MR 3612759, DOI 10.1016/j.cma.2016.12.014
Peter Binev, Wolfgang Dahmen, and Ron DeVore, Adaptive finite element methods with convergence rates, Numer. Math. 97 (2004), no. 2, 219–268. MR 2050077, DOI 10.1007/s00211-003-0492-7
Andrea Bonito and Ricardo H. Nochetto, Quasi-optimal convergence rate of an adaptive discontinuous Galerkin method, SIAM J. Numer. Anal. 48 (2010), no. 2, 734–771. MR 2670003, DOI 10.1137/08072838X
Annalisa Buffa, Carlotta Giannelli, Philipp Morgenstern, and Daniel Peterseim, Complexity of hierarchical refinement for a class of admissible mesh configurations, Comput. Aided Geom. Design 47 (2016), 83–92. MR 3545984, DOI 10.1016/j.cagd.2016.04.003
C. Carstensen, M. Feischl, M. Page, and D. Praetorius, Axioms of adaptivity, Comput. Math. Appl. 67 (2014), no. 6, 1195–1253. MR 3170325, DOI 10.1016/j.camwa.2013.12.003
Carsten Carstensen and Joscha Gedicke, An adaptive finite element eigenvalue solver of asymptotic quasi-optimal computational complexity, SIAM J. Numer. Anal. 50 (2012), no. 3, 1029–1057. MR 2970733, DOI 10.1137/090769430
J. Manuel Cascon, Christian Kreuzer, Ricardo H. Nochetto, and Kunibert G. Siebert, Quasi-optimal convergence rate for an adaptive finite element method, SIAM J. Numer. Anal. 46 (2008), no. 5, 2524–2550. MR 2421046, DOI 10.1137/07069047X
J. Manuel Cascón and Ricardo H. Nochetto, Quasioptimal cardinality of AFEM driven by nonresidual estimators, IMA J. Numer. Anal. 32 (2012), no. 1, 1–29. MR 2875241, DOI 10.1093/imanum/drr014
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
Scott Congreve and Thomas P. Wihler, Iterative Galerkin discretizations for strongly monotone problems, J. Comput. Appl. Math. 311 (2017), 457–472. MR 3552717, DOI 10.1016/j.cam.2016.08.014
Lars Diening and Christian Kreuzer, Linear convergence of an adaptive finite element method for the $p$-Laplacian equation, SIAM J. Numer. Anal. 46 (2008), no. 2, 614–638. MR 2383205, DOI 10.1137/070681508
Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
Linda El Alaoui, Alexandre Ern, and Martin Vohralík, Guaranteed and robust a posteriori error estimates and balancing discretization and linearization errors for monotone nonlinear problems, Comput. Methods Appl. Mech. Engrg. 200 (2011), no. 37-40, 2782–2795. MR 2811915, DOI 10.1016/j.cma.2010.03.024
Alexandre Ern and Martin Vohralík, Adaptive inexact Newton methods with a posteriori stopping criteria for nonlinear diffusion PDEs, SIAM J. Sci. Comput. 35 (2013), no. 4, A1761–A1791. MR 3072765, DOI 10.1137/120896918
M. Feischl, T. Führer, and D. Praetorius, Adaptive FEM with optimal convergence rates for a certain class of nonsymmetric and possibly nonlinear problems, SIAM J. Numer. Anal. 52 (2014), no. 2, 601–625. MR 3176325, DOI 10.1137/120897225
Thomas Führer, Zur Kopplung von finiten Elementen und Randelementen, Ph.D. Thesis, TU Wien Institute of Analysis and Sicnetific Computing, 2014.
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 Dirk Praetorius, A linear Uzawa-type FEM-BEM solver for nonlinear transmission problems, Comput. Math. Appl. 75 (2018), no. 8, 2678–2697. MR 3787479, DOI 10.1016/j.camwa.2017.12.035
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
Gregor Gantner, Alexander Haberl, Dirk Praetorius, and Bernhard Stiftner, Rate optimal adaptive FEM with inexact solver for nonlinear operators, IMA J. Numer. Anal. 38 (2018), no. 4, 1797–1831. MR 3867383, DOI 10.1093/imanum/drx050
Gregor Gantner, Daniel Haberlik, and Dirk Praetorius, Adaptive IGAFEM with optimal convergence rates: hierarchical B-splines, Math. Models Methods Appl. Sci. 27 (2017), no. 14, 2631–2674. MR 3723732, DOI 10.1142/S0218202517500543
Eduardo M. Garau, Pedro Morin, and Carlos Zuppa, Convergence of an adaptive Kačanov FEM for quasi-linear problems, Appl. Numer. Math. 61 (2011), no. 4, 512–529. MR 2754575, DOI 10.1016/j.apnum.2010.12.001
Eduardo M. Garau, Pedro Morin, and Carlos Zuppa, Quasi-optimal convergence rate of an AFEM for quasi-linear problems of monotone type, Numer. Math. Theory Methods Appl. 5 (2012), no. 2, 131–156. MR 2911871, DOI 10.4208/nmtma.2012.m1023
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
Pascal Heid, Dirk Praetorius, and Thomas P. Wihler, Energy contraction and optimal convergence of adaptive iterative linearized finite element methods, Comput. Methods Appl. Math. 21 (2021), no. 2, 407–422. MR 4235817, DOI 10.1515/cmam-2021-0025
Pascal Heid and Thomas P. Wihler, Adaptive iterative linearization Galerkin methods for nonlinear problems, Math. Comp. 89 (2020), no. 326, 2707–2734. MR 4136544, DOI 10.1090/mcom/3545
Pascal Heid and Thomas P. Wihler, On the convergence of adaptive iterative linearized Galerkin methods, Calcolo 57 (2020), no. 3, Paper No. 24, 23. MR 4131951, DOI 10.1007/s10092-020-00368-4
Paul Houston and Thomas P. Wihler, An $hp$-adaptive Newton-discontinuous-Galerkin finite element approach for semilinear elliptic boundary value problems, Math. Comp. 87 (2018), no. 314, 2641–2674. MR 3834680, DOI 10.1090/mcom/3308
Michael Karkulik, David Pavlicek, and Dirk Praetorius, On 2D newest vertex bisection: optimality of mesh-closure and $H^1$-stability of $L_2$-projection, Constr. Approx. 38 (2013), no. 2, 213–234. MR 3097045, DOI 10.1007/s00365-013-9192-4
Philipp Morgenstern and Daniel Peterseim, Analysis-suitable adaptive T-mesh refinement with linear complexity, Comput. Aided Geom. Design 34 (2015), 50–66. MR 3341848, DOI 10.1016/j.cagd.2015.02.003
Pedro Morin, Ricardo H. Nochetto, and Kunibert G. Siebert, Data oscillation and convergence of adaptive FEM, SIAM J. Numer. Anal. 38 (2000), no. 2, 466–488. MR 1770058, DOI 10.1137/S0036142999360044
Carl-Martin Pfeiler and Dirk Praetorius, Dörfler marking with minimal cardinality is a linear complexity problem, Math. Comp. 89 (2020), no. 326, 2735–2752. MR 4136545, DOI 10.1090/mcom/3553
Joachim Schöberl, Jens M. Melenk, Clemens Pechstein, and Sabine Zaglmayr, Additive Schwarz preconditioning for $p$-version triangular and tetrahedral finite elements, IMA J. Numer. Anal. 28 (2008), no. 1, 1–24. MR 2387903, DOI 10.1093/imanum/drl046
Rob Stevenson, Optimality of a standard adaptive finite element method, Found. Comput. Math. 7 (2007), no. 2, 245–269. MR 2324418, DOI 10.1007/s10208-005-0183-0
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
Andreas Veeser, Convergent adaptive finite elements for the nonlinear Laplacian, Numer. Math. 92 (2002), no. 4, 743–770. MR 1935808, DOI 10.1007/s002110100377
Rüdiger Verfürth, A posteriori error estimation techniques for finite element methods, Oxford University Press, Oxford, 2013., DOI 10.1093/acprof:oso/9780199679423.001.0001
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
X. Xu, H. Chen, and R. H. W. Hoppe, Optimality of local multilevel methods on adaptively refined meshes for elliptic boundary value problems, J. Numer. Math. 18 (2010), no. 1, 59–90. MR 2629823, DOI 10.1515/JNUM.2010.003
Eberhard Zeidler, Nonlinear functional analysis and its applications. II/B, Springer-Verlag, New York, 1990. Nonlinear monotone operators; Translated from the German by the author and Leo F. Boron. MR 1033498, DOI 10.1007/978-1-4612-0985-0