Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Greedy bisection generates optimally adapted triangulations


Authors: Jean-Marie Mirebeau and Albert Cohen
Journal: Math. Comp. 81 (2012), 811-837
MSC (2010): Primary 65-XX; Secondary 41-XX
DOI: https://doi.org/10.1090/S0025-5718-2011-02459-2
Published electronically: September 28, 2011
MathSciNet review: 2869038
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the properties of a simple greedy algorithm for the generation of data-adapted anisotropic triangulations. Given a function $ f$, the algorithm produces nested triangulations $ \mathcal {T}_N$ and corresponding piecewise polynomial approximations $ f_N$ of $ f$. The refinement procedure picks the triangle which maximizes the local $ L^p$ approximation error, and bisects it in a direction which is chosen so to minimize this error at the next step. We study the approximation error in the $ L^p$ norm when the algorithm is applied to $ C^2$ functions with piecewise linear approximations. We prove that as the algorithm progresses, the triangles tend to adopt an optimal aspect ratio which is dictated by the local hessian of $ f$. For convex functions, we also prove that the adaptive triangulations satisfy the convergence bound $ \Vert f-f_N\Vert _{L^p} \leq CN^{-1}\Vert\sqrt {\det (d^2f)}\Vert _{L^\tau }$ with $ \frac 1 \tau :=\frac 1 p + 1$, which is known to be asymptotically optimal among all possible triangulations.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65-XX, 41-XX

Retrieve articles in all journals with MSC (2010): 65-XX, 41-XX


Additional Information

Jean-Marie Mirebeau
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France
Email: mirebeau@ann.jussieu.fr

Albert Cohen
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France-
Email: cohen@ann.jussieu.fr

DOI: https://doi.org/10.1090/S0025-5718-2011-02459-2
Received by editor(s): October 20, 2008
Received by editor(s) in revised form: June 15, 2010
Published electronically: September 28, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society