Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
Published electronically: October 13, 2011
MathSciNet review: 2904579
Full-text PDF Free Access

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 $ 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 [Enhancements On Off] (What's this?)

  • 1. Pankaj K. Agarwal and Subhash Suri.
    Surface approximation and geometric partitions.
    Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 24-33, 1994.
    Arlington, Virginia, United States. MR 1285148 (95h:68181)
  • 2. G. Aubert and P. Kornprobst.
    Mathematical problems in image processing, volume 147 of Applied Mathematical Sciences.
    Springer-Verlag, New York, 2002.
    Partial differential equations and the calculus of variations, With a foreword by Olivier Faugeras. MR 1865346 (2002m:49001)
  • 3. Th. Aubin.
    Nonlinear analysis on manifolds. Monge-Ampère equations, volume 252 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].
    Springer-Verlag, New York, 1982. MR 681859 (85j:58002)
  • 4. E. Bänsch.
    Finite element discretization of the Navier-Stokes equations with a free capillary surface.
    Numer. Math., 88(2):203-235, 2001. MR 1826211 (2002h:76079)
  • 5. A. Bonito, R.H. Nochetto, and M.S. Pauletti.
    Geometrically consistent mesh modifications.
    SIAM J. Numer. Anal., 48 (2010), no. 5, 1877-1899. MR 2733102 (2011j:65263)
  • 6. D. Braess and W. Hackbusch.
    A new convergence proof for the multigrid method including the $ V$-cycle.
    SIAM J. Numer. Anal., 20(5):967-975, 1983. MR 714691 (85h:65233)
  • 7. J.H. Bramble, D.Y. Kwak, and J.E. Pasciak.
    Uniform convergence of multigrid $ V$-cycle iterations for indefinite and nonsymmetric problems.
    SIAM J. Numer. Anal., 31(6):1746-1763, 1994. MR 1302683 (95i:65170)
  • 8. J.H. Bramble, J.E. Pasciak, and J. Xu.
    The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms.
    Math. Comp., 56(193):1-34, 1991. MR 1052086 (91h:65159)
  • 9. J.H. Bramble and X. Zhang.
    The analysis of multigrid methods.
    In Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, pages 173-415. North-Holland, Amsterdam, 2000. 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, editors.
    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. A. Demlow.
    Higher-order finite element methods and pointwise error estimates for elliptic problems on surfaces.
    SIAM J. Numer. Anal., 47(2):805-827, 2009. MR 2485433 (2010a:65233)
  • 13. A. Demlow and G. Dziuk.
    An adaptive finite element method for the Laplace-Beltrami operator on implicitly defined surfaces.
    SIAM J. Numer. Anal., 45(1):421-442 (electronic), 2007. MR 2285862 (2008c:65320)
  • 14. G. Dogan, P. Morin, and R.H. Nochetto.
    A variational shape optimization approach for image segmentation with a Mumford-Shah functional.
    SIAM J. Sci. Comput., 30(6):3028-3049, 2008. MR 2452377 (2009j:68184)
  • 15. G. Dziuk.
    Finite elements for the Beltrami operator on arbitrary surfaces.
    In Partial differential equations and calculus of variations, volume 1357 of Lecture Notes in Math., pages 142-155. Springer, Berlin, 1988. MR 976234 (90i:65194)
  • 16. G. Dziuk and C. M. Elliott.
    Finite elements on evolving surfaces.
    IMA J. Numer. Anal., 27(2):262-292, 2007. MR 2317005 (2008c:65253)
  • 17. D. Gilbarg and N.S. Trudinger.
    Elliptic partial differential equations of second order, volume 224 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].
    Springer-Verlag, Berlin, second edition, 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(1-4):139-191 (2002), 2001.
    A posteriori error estimation and adaptive computational methods. MR 1887732 (2003a:65108)
  • 21. R. Kornhuber and H. Yserentant.
    Multigrid methods for discrete elliptic problems on triangular surfaces.
    Comput. Vis. Sci., 11(4-6):251-257, 2008. MR 2425494 (2009i:65236)
  • 22. Y.-J. Lee, J. Wu, J. Xu, and L. Zikatanov.
    A sharp convergence estimate for the method of subspace corrections for singular systems of equations.
    Math. Comp., 77(262):831-850, 2008. MR 2373182 (2008k:65106)
  • 23. J. Maes, A. Kunoth, and A. Bultheel.
    BPX-type preconditioners for second and fourth order elliptic problems on the sphere.
    SIAM J. Numer. Anal., 45(1):206-222 (electronic), 2007. MR 2285851 (2008c:65301)
  • 24. K. Mekchay.
    Convergence of Adaptive Finite Element Methods.
    PhD thesis, University of Maryland, 2005. MR 2708247
  • 25. K. Mekchay, P. Morin, and R.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
  • 26. Maxim A. Olshanskii and Arnold Reusken.
    A finite element method for surface PDEs: matrix properties.
    Numer. Math., 114(3):491-520, 2010. MR 2570076 (2010m:65289)
  • 27. Maxim A. Olshanskii, Arnold Reusken, and Jörg Grande.
    A finite element method for elliptic equations on surfaces.
    SIAM J. Numer. Anal., 47(5):3339-3358, 2009. MR 2551197 (2010k:65265)
  • 28. J. Sokołowski and J.-P. Zolésio.
    Introduction to shape optimization, volume 16 of Springer Series in Computational Mathematics.
    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)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65N30, 65N55

Retrieve articles in all journals with MSC (2010): 65N30, 65N55

Additional Information

Andrea Bonito
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843-3368

Joseph E. Pasciak
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843-3368

Received by editor(s): August 23, 2009
Received by editor(s) in revised form: March 23, 2011
Published electronically: October 13, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society