Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

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

Authors: Andrea Bonito and Joseph E. Pasciak
Journal: Math. Comp. 81 (2012), 1263-1288
MSC (2010): Primary 65N30, 65N55
Posted: October 13, 2011
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 -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

1. Pankaj K. Agarwal and Subhash Suri, Surface approximation and geometric partitions, Algorithms (Arlington, VA, 1994) ACM, New York, 1994, pp. 24–33. MR 1285148 (95h:68181)
2. 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 (2002m:49001)
3. 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 (85j:58002)
4. 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 (2002h:76079), http://dx.doi.org/10.1007/PL00005443
5. 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 (2011j:65263), http://dx.doi.org/10.1137/100781833
6. D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the 𝑉-cycle, SIAM J. Numer. Anal. 20 (1983), no. 5, 967–975. MR 714691 (85h:65233), http://dx.doi.org/10.1137/0720066
7. James H. Bramble, Do Y. Kwak, and Joseph E. Pasciak, Uniform convergence of multigrid 𝑉-cycle iterations for indefinite and nonsymmetric problems, SIAM J. Numer. Anal. 31 (1994), no. 6, 1746–1763. MR 1302683 (95i:65170), http://dx.doi.org/10.1137/0731089
8. 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 (91h:65159), http://dx.doi.org/10.1090/S0025-5718-1991-1052086-4
9. 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 (2001m:65183)
10. 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.
11. 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 (92f:65001)
12. 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 (2010a:65233), http://dx.doi.org/10.1137/070708135
13. 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 (electronic). MR 2285862 (2008c:65320), http://dx.doi.org/10.1137/050642873
14. 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 (2009j:68184), http://dx.doi.org/10.1137/070692066
15. 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 (90i:65194), http://dx.doi.org/10.1007/BFb0082865
16. G. Dziuk and C. M. Elliott, Finite elements on evolving surfaces, IMA J. Numer. Anal. 27 (2007), no. 2, 262–292. MR 2317005 (2008c:65253), http://dx.doi.org/10.1093/imanum/drl023
17. 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 (86c:35035)
18. 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.
19. W. Helfrich.
Elastic properties of lipid bilayers - theory and possible experiments.
Zeitschrift Fur Naturforschung C-A Journal Of Biosciences, 28:693, 1973.
20. 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 (2003a:65108), http://dx.doi.org/10.1023/A:1014246117321
21. 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 (2009i:65236), http://dx.doi.org/10.1007/s00791-008-0102-4
22. 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 (2008k:65106), http://dx.doi.org/10.1090/S0025-5718-07-02052-2
23. 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 (electronic). MR 2285851 (2008c:65301), http://dx.doi.org/10.1137/050647414
24. Khamron Mekchay, Convergence of adaptive finite element methods, ProQuest LLC, Ann Arbor, MI, 2005. Thesis (Ph.D.)–University of Maryland, College Park. MR 2708247
25. 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 (2012c:65202), http://dx.doi.org/10.1090/S0025-5718-2010-02435-4
26. 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 (2010m:65289), http://dx.doi.org/10.1007/s00211-009-0260-4
27. 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 (2010k:65265), http://dx.doi.org/10.1137/080717602
28. 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 (94d:49002)
29. T. J. Willmore, Riemannian geometry, Oxford Science Publications, The Clarendon Press Oxford University Press, New York, 1993. MR 1261641 (95e:53002)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|