Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

In Finite Element theory, and other methods in scientific computing for PDEs, one uses meshes which fulfill several regularity criteria, many of them being equivalent.

It is of interest to have notions of shape-regularity in arbitrary dimensions. While some authors use this as if there were full analogies of the two-dimensional theory to higher dimensions, it seems no one has ever before established this rigorously. Do you know a reference on this?

share|improve this question
    
Can you be a little more specific about what you mean by 'shape regularity'? Are you referring to the quality of the mesh? –  Paul Mar 4 '12 at 17:26
    
Shape-regularity as it is defined in standard FEM-textbooks. Also known as shape-uniformity. Means the simplices to not degenerate, i.e. some regularity measure does not degenerate. A usual definition is the quotient of diameter and inscribed circle radius of the simplex. –  shuhalo Mar 5 '12 at 14:36
1  
This question is highly sensitive to mesh topology. The only case that can be considered "fully explored" is for $P_1$ elements on simplicial meshes (cs.berkeley.edu/~jrs/jrspapers.html#quality). Quality measures on arbitrary meshes are very element and problem dependent. In many cases, a boundary layer for a CFD problem should have an aspect ratio of $10^6$, but most "quality measures" will say that is a "bad mesh" despite it having the right approximation properties. –  Jed Brown Aug 1 '12 at 7:42

2 Answers 2

The correct answer was already given by Jed Brown in a comment, but a brief explanation might help. Shape regularity enters into finite element methods when stitching together local interpolation errors to get a global interpolation error (which is an upper bound for the approximation error and hence, by Céa's lemma, for the discretization error). Basically, you get local interpolation errors by estimating the interpolation error on a reference element (using the Bramble-Hilbert lemma) and then transforming it to each local element. This transformation gives you

  1. the required power of the element size $h$ and
  2. a power of the condition number of the Jacobian of the transformation

on the right hand side of the estimate. In order to obtain a global error estimate with only this power of (the maximal occuring) $h$ on the right hand side, you thus need a uniform bound for this condition number.

For simplicial meshes, you can show (independently of the dimension!) that this condition number can be estimated by the ratio of the diameters of the inscribed and the circumscribed (or minimal containing) ball. (In two dimensions, this ratio can in turn be estimated by $2/\sin(\vartheta)$, where $\vartheta$ is the smallest angle of the triangle.) If this ratio is uniformly bounded for all elements, the mesh is called shape regular. Hence in this case the usual definition is already dimension independent. You can find a detailed treatment in Chapter 1.5 of Ern and Guermond, Theory and Practice of Finite Elements.

(For rectangular meshes, you would probably use bounds of the condition number in terms of ratios of maximal and minimal edge lengths, which also makes sense for arbitrary dimensions, although I don't have any reference for that.)

Note that this is a separate issue from mesh quality, which also takes into account the conditioning of the linear system arising from the discretization, and ignores the magnitude of the constants in the mentioned estimates.

share|improve this answer
    
Thank you very much, I am going to consult this book. –  shuhalo Oct 30 '12 at 15:47

If you are using an isoparametric formulation, the determinant of the Jacobian of your mapping has to be greater than zero in order to have a bijective mapping from the reference to the real elements. This generalizes to arbitrary dimensions, and this is the regularity criterion (if its not fulfilled its game over).

The other regularity criterion serve multiple purposes. You can have elements in which the determinant of the Jacobian is close to, but not, zero, which might lead to large errors. You might want to have a regular distribution of elements to achieve an even distribution of your error in "single-scale" problems, ...

Two possibilities are: using the diameter of the lagest n-sphere that fits inside your n-th dimensional element and trying to make this value regular across your mesh, and, restricting the minimum/maximum angles between your element faces, which are (n-1)-dimensional manifolds. Both criterion generalize to arbitrary dimensions.

There is a discussion about this in Bathe's Finite Element Procedures. I don´t remember exactly if this was also covered in Frey's and George's Mesh Generation or in Lisekin's Mesh Generation Methods.

share|improve this answer
1  
This measure is not scale invariant. The condition number of the Jacobian is at least scale invariant. –  Jed Brown Aug 1 '12 at 7:38
    
Hi @JedBrown, what do you mean? Could you elaborate? Thanks! –  gnzlbg Aug 9 '12 at 14:19
2  
Exactly what I said. If you change the size of the elements while preserving the shape, the determinant changes, therefore it can't possibly be used as a stand-alone quality metric. For simplicial elements, a common measure is the ratio of the diameter between inscribed and circumscribed $n$-balls. –  Jed Brown Aug 9 '12 at 17:18
    
I see! I was suggesting to check only that the determinant is greater than zero (as the most basic mesh quality criterion, because if its not fulfilled the mesh "won't work"). As you said, the size equals the scaling of a shape-preserving transformation. I don't think that one can get any meaningful information from it if the mapping from reference to real elements is not shape-preserving. –  gnzlbg Aug 9 '12 at 21:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.