Convergence analysis of variational and non-variational multigrid algorithms for the Laplace-Beltrami operator

Bonito, Andrea; Pasciak, Joseph

doi:10.1090/S0025-5718-2011-02551-2

Convergence analysis of variational and non-variational multigrid algorithms for the Laplace-Beltrami operator
HTML articles powered by AMS MathViewer

by Andrea Bonito and Joseph E. Pasciak PDF

Math. Comp. 81 (2012), 1263-1288 Request permission

Abstract:

We design and analyze variational and non-variational multigrid algorithms for the Laplace-Beltrami operator on a smooth and closed surface. In both cases, a uniform convergence for the $V$-cycle algorithm is obtained provided the surface geometry is captured well enough by the coarsest grid. The main argument hinges on a perturbation analysis from an auxiliary variational algorithm defined directly on the smooth surface. In addition, the vanishing mean value constraint is imposed on each level, thereby avoiding singular quadratic forms without adding additional computational cost.

Numerical results supporting our analysis are reported. In particular, the algorithms perform well even when applied to surfaces with a large aspect ratio.

References

Pankaj K. Agarwal and Subhash Suri, Surface approximation and geometric partitions, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994) ACM, New York, 1994, pp. 24–33. MR 1285148
Gilles Aubert and Pierre Kornprobst, Mathematical problems in image processing, Applied Mathematical Sciences, vol. 147, Springer-Verlag, New York, 2002. Partial differential equations and the calculus of variations; With a foreword by Olivier Faugeras. MR 1865346
Thierry Aubin, Nonlinear analysis on manifolds. Monge-Ampère equations, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 252, Springer-Verlag, New York, 1982. MR 681859, DOI 10.1007/978-1-4612-5734-9
Eberhard Bänsch, Finite element discretization of the Navier-Stokes equations with a free capillary surface, Numer. Math. 88 (2001), no. 2, 203–235. MR 1826211, DOI 10.1007/PL00005443
A. Bonito, R. H. Nochetto, and M. S. Pauletti, Geometrically consistent mesh modification, SIAM J. Numer. Anal. 48 (2010), no. 5, 1877–1899. MR 2733102, DOI 10.1137/100781833
D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the $V$-cycle, SIAM J. Numer. Anal. 20 (1983), no. 5, 967–975. MR 714691, DOI 10.1137/0720066
James H. Bramble, Do Y. Kwak, and Joseph E. Pasciak, Uniform convergence of multigrid $V$-cycle iterations for indefinite and nonsymmetric problems, SIAM J. Numer. Anal. 31 (1994), no. 6, 1746–1763. MR 1302683, DOI 10.1137/0731089
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms, Math. Comp. 56 (1991), no. 193, 1–34. MR 1052086, DOI 10.1090/S0025-5718-1991-1052086-4
James H. Bramble and Xuejun Zhang, The analysis of multigrid methods, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 173–415. MR 1804746
P.B. Canham. The minimum energy of bending as a possible explanation of the biconcave shape of the human red blood cell. Journal of Theoretical Biology, 26(1):61–81, January 1970.
P. G. Ciarlet and J.-L. Lions (eds.), Handbook of numerical analysis. Vol. II, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. MR 1115235
Alan Demlow, Higher-order finite element methods and pointwise error estimates for elliptic problems on surfaces, SIAM J. Numer. Anal. 47 (2009), no. 2, 805–827. MR 2485433, DOI 10.1137/070708135
Alan Demlow and Gerhard Dziuk, An adaptive finite element method for the Laplace-Beltrami operator on implicitly defined surfaces, SIAM J. Numer. Anal. 45 (2007), no. 1, 421–442. MR 2285862, DOI 10.1137/050642873
Günay Doǧan, Pedro Morin, and Ricardo H. Nochetto, A variational shape optimization approach for image segmentation with a Mumford-Shah functional, SIAM J. Sci. Comput. 30 (2008), no. 6, 3028–3049. MR 2452377, DOI 10.1137/070692066
Gerhard Dziuk, Finite elements for the Beltrami operator on arbitrary surfaces, Partial differential equations and calculus of variations, Lecture Notes in Math., vol. 1357, Springer, Berlin, 1988, pp. 142–155. MR 976234, DOI 10.1007/BFb0082865
G. Dziuk and C. M. Elliott, Finite elements on evolving surfaces, IMA J. Numer. Anal. 27 (2007), no. 2, 262–292. MR 2317005, DOI 10.1093/imanum/drl023
David Gilbarg and Neil S. Trudinger, Elliptic partial differential equations of second order, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 224, Springer-Verlag, Berlin, 1983. MR 737190, DOI 10.1007/978-3-642-61798-0
E Hebey. Nonlinear analysis on manifolds: Sobolev spaces and inequalities, volume 5 of Courant Lecture Notes in Mathematics. New York University, Courant Institute of Mathematical Sciences, New York, 1999.
W. Helfrich. Elastic properties of lipid bilayers - theory and possible experiments. Zeitschrift Fur Naturforschung C-A Journal Of Biosciences, 28:693, 1973.
M. Holst, Adaptive numerical treatment of elliptic systems on manifolds, Adv. Comput. Math. 15 (2001), no. 1-4, 139–191 (2002). A posteriori error estimation and adaptive computational methods. MR 1887732, DOI 10.1023/A:1014246117321
Ralf Kornhuber and Harry Yserentant, Multigrid methods for discrete elliptic problems on triangular surfaces, Comput. Vis. Sci. 11 (2008), no. 4-6, 251–257. MR 2425494, DOI 10.1007/s00791-008-0102-4
Young-Ju Lee, Jinbiao Wu, Jinchao Xu, and Ludmil Zikatanov, A sharp convergence estimate for the method of subspace corrections for singular systems of equations, Math. Comp. 77 (2008), no. 262, 831–850. MR 2373182, DOI 10.1090/S0025-5718-07-02052-2
Jan Maes, Angela Kunoth, and Adhemar Bultheel, BPX-type preconditioners for second and fourth order elliptic problems on the sphere, SIAM J. Numer. Anal. 45 (2007), no. 1, 206–222. MR 2285851, DOI 10.1137/050647414
Khamron Mekchay, Convergence of adaptive finite element methods, ProQuest LLC, Ann Arbor, MI, 2005. Thesis (Ph.D.)–University of Maryland, College Park. MR 2708247
Khamron Mekchay, Pedro Morin, and Ricardo H. Nochetto, AFEM for the Laplace-Beltrami operator on graphs: design and conditional contraction property, Math. Comp. 80 (2011), no. 274, 625–648. MR 2772090, DOI 10.1090/S0025-5718-2010-02435-4
Maxim A. Olshanskii and Arnold Reusken, A finite element method for surface PDEs: matrix properties, Numer. Math. 114 (2010), no. 3, 491–520. MR 2570076, DOI 10.1007/s00211-009-0260-4
Maxim A. Olshanskii, Arnold Reusken, and Jörg Grande, A finite element method for elliptic equations on surfaces, SIAM J. Numer. Anal. 47 (2009), no. 5, 3339–3358. MR 2551197, DOI 10.1137/080717602
Jan Sokołowski and Jean-Paul Zolésio, Introduction to shape optimization, Springer Series in Computational Mathematics, vol. 16, Springer-Verlag, Berlin, 1992. Shape sensitivity analysis. MR 1215733, DOI 10.1007/978-3-642-58106-9
T. J. Willmore, Riemannian geometry, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1993. MR 1261641