An inequality on the edge lengths of triangular meshes

We give a short proof of the following geometric inequality: for any two triangular meshes A and B of the same polygon C, if the number of vertices in A is at most the number of vertices in B, then the maximum length of an edge in A is at least the minimum distance between two vertices in B. Here the vertices in each triangular mesh include the vertices of the polygon and possibly additional Steiner points. The polygon must not be self-intersecting but may be non-convex and may even have holes. This inequality is useful for many purposes, especially in proving performance guarantees of mesh generation algorithms. For example, a weaker corollary of the inequality confirms a conjecture of Aurenhammer et al. [Theoretical Computer Science 289 (2002) 879-895] concerning triangular meshes of convex polygons, and improves the approximation ratios of their mesh generation algorithm for minimizing the maximum edge length and the maximum triangle perimeter of a triangular mesh.     

Discretization of second-order ordinary differential equations with symmetries

A number of publications (indicated in the Introduction) are overviewed that address the group properties, first integrals, and integrability of difference equations and meshes approximating second-order ordinary differential equations with symmetries. A new example of such equations is discussed in the overview. Additionally, it is shown that the parametric families of invariant difference schemes include exact schemes, i.e., schemes whose general solution coincides with the corresponding solution set of the differential equations at mesh nodes, which can be of arbitrary density. Thereby, it is shown that there is a kind of mathematical dualism for the problems under study: for a given physical process, there are two mathematical models: continuous and discrete. The former is described by continuous curves, while the latter, by points on these curves.     

Configurational-force-based structural updates and adaptive remeshing strategies

The application of configurational forces in h -adaptive strategies for fracture mechanics and inelasticity is investigated. Starting from a global Clausius-Planck inequality, dual equilibrium conditions are derived by means of a Coleman-type exploitation method. The remaining reduced dissipation inequality is used for the derivation of evolution equations for the internal variables. In fracture mechanics, crack loading conditions as well as a normality rule for the crack propagation are obtained. In the discrete setting, the crack propagation is governed by a configurational-force-driven update of the geometry model. The material balance equation is used to set up a h -adaptive refinement indicator. A relative global criterion is defined used for the decision on mesh refinement. In addition, a criterion on the element level is evaluated controlling the local refinement procedure. The capability of the proposed procedures is demonstrated by means of numerical examples. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Constructing orthogonal curvilinear meshes by solving initial value problems

Summary The purpose of this paper is to develop methods for constructing orthogonal curvilinear meshes suitable for solving partial differential equations over plane regions with smooth, curved boundaries. These curved meshes cover an annular strip along the boundary of the region which is included in the mesh. In this strip difference approximations of partial differential equations and boundary conditions can be set up as easily as they can for halfspace problems. The rest of the region and a suitable part of the annular strip can be covered by a square or rectangular mesh. In the present paper we consider the problem of determining curved meshes by solving nonlinear hyperbolic initial value problems which are formally related to the Cauchy-Riemann equations.This work was sponsored by the Swedish Institute for Applied Mathematics (ITM)     

A coarsening algorithm on adaptive red-green-blue refined meshes

Adaptive meshing is a fundamental component of adaptive finite element methods. This includes refining and coarsening meshes locally. In this work, we are concerned with the red-green-blue refinement strategy in two dimensions and its counterpart-coarsening. In general, coarsening algorithms are mostly based on an explicitly given refinement history. In this work, we present a coarsening algorithm on adaptive red-green-blue meshes in two dimensions without explicitly knowing the refinement history. To this end, we examine the local structure of these meshes, find an easy-to-verify criterion to adaptively coarsen red-green-blue meshes, and prove that this criterion generates meshes with the desired properties. We present a MATLAB implementation built on the red-green-blue refinement routine of the ameshref-package (Funken and Schmidt 2018, 2019).

     

Sobre la utilización de códigos de elementos finitos basados en mallados cartesianos en optimización estructural

The structural shape optimization is an iterative process built up by a higher level, which proposes the geometries to analyze, and a lower level which is in charge of analyzing, numerically, their structural response, usually by means of the Finite Element Method (FEM). These techniques normally report notorious advantages in an industrial environment, but their high computational cost is the main drawback. The efficiency of the global process requires the efficiency of both levels. This work focuses on the improvement of the efficiency of the lower level by using a methodology that uses a 2D linear elasticity code based on geometry-independent Cartesian grids, combined with FEM solution and recovery techniques, adapted to this framework. This mesh type simplifies the mesh generation and, in combination with a hierarchical data structure, reuses a great calculus amount. The recovery technique plays a double role: a) it is used in the Zienkiewicz-Zhu type error estimators allowing to quantify the FEM solution quality to guide the h-adaptive refinement process which minimizes the computational cost for a given accuracy; and b) it provides a solution, more accurate than the FEM one, that can be used. The numerical results, which include a comparative with a commercial code, show the effect of the proposed methodology improving the efficiency in the optimization process and in the solution quality.     

A linear and accurate diffusion scheme respecting the maximum principle on distorted meshes

This Note is devoted to the presentation of a linear diffusion scheme that respects the maximum principle on very distorted meshes. The main idea is to use a classical Finite Volumes scheme and to perform a first integration on the Voronoï mesh based on the centers of the cells. A second integration on the primary mesh is then performed. By construction the scheme preserves the maximum principle. A numerical example is also given. To cite this article: V. Siess, C. R. Acad. Sci. Paris, Ser. I 347 (2009).     

Configurational-Force-Based Adaptive FE Solver for a Phase Field Model of Fracture

The computational modeling of failure mechanisms in solids due to fracture based on sharp crack discontinuities suffers in situations with complex crack topologies. This can be overcome by diffusive crack modeling, based on the introduction of a crack phase field as outlined in [1, 2]. Following these formulations, we outline a thermodynamically consistent framework for phase field models of crack propagation in elastic solids, develop incremental variational principles and, as an extension to [1, 2], consider their numerical implementations by an efficient h-adaptive finite element method. A key problem of the phase field formulation is the mesh density, which is required for the resolution of the diffusive crack patterns. To this end, we embed the computational framework into an adaptive mesh refinement strategy that resolves the fracture process zones. We construct a configurational-force-based framework for h-adaptive finite element discretizations of the gradient-type diffusive fracture model. We develop a staggered computational scheme for the solution of the coupled balances in physical and material space. The balance in the material space is then used to set up indicators for the quality of the finite element mesh and accounts for a subsequent h-type mesh refinement. The capability of the proposed method is demonstrated by means of a numerical example. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Four-triangles adaptive algorithms for RTIN terrain meshes

We present a refinement and coarsening algorithm for the adaptive representation of Right-Triangulated Irregular Network (RTIN) meshes. The refinement algorithm is very simple and proceeds uniformly or locally in triangle meshes. The coarsening algorithm decreases mesh complexity by reducing unnecessary data points in the mesh after a given error criterion is applied. We describe the most important features of the algorithms and give a brief numerical study on the propagation associated with the adaptive scheme used for the refinement algorithm. We also present a comparison with a commercial tool for mesh simplification, Rational Reducer, showing that our coarsening algorithm offers better results in terms of accuracy of the generated meshes.     

Construction dʼun champ continu de métriques

Adaptive computation using adaptive meshes is now recognized as essential for solving complex PDE problems. This computation requires, at each step, the definition of a continuous metric field to govern the generation of the adapted meshes. In practice, via an appropriate a posteriori error estimation, metrics are calculated at the vertices of the computational domain mesh. In order to obtain a continuous metric field, the discrete field is interpolated in the whole domain mesh. In this Note, a new method for interpolating discrete metric fields, based on a so-called “natural decomposition” of metrics, is introduced. The proposed method is based on known matrix decompositions and is computationally robust and efficient. Some qualitative comparisons with classical methods are made to show the relevance of this methodology.     

The hp-MITC finite element method for the Reissner–Mindlin plate problem

The popular MITC finite elements used for the approximation of the Reissner–Mindlin plate are extended to the case where elements of non-uniform degree p distribution are used on locally refined meshes. Such an extension is of particular interest to the hp-version and hp-adaptive finite element methods. A priori error bounds are provided showing that the method is locking-free. The analysis is based on new approximation theoretic results for non-uniform Brezzi–Douglas–Fortin–Marini spaces, and extends the results obtained in the case of uniform order approximation on globally quasi-uniform meshes presented by Stenberg and Suri (SIAM J. Numer. Anal. 34 (1997) 544). Numerical examples illustrating the theoretical results and comparing the performance with alternative standard Galerkin approaches are presented for two new benchmark problems with known analytic solution, including the case where the shear stress exhibits a boundary layer. The new method is observed to be locking-free and able to provide exponential rates of convergence even in the presence of boundary layers.     

Coupling of h and p finite elements: Application to free vibration analysis of plates with curvilinear plan-forms

This paper presents a method for coupling isoparametric cubic quadrilateral h-elements and straight sided serendipity quadrilateral p-elements. The p-elements are used to model the interior of the domain while the h-elements are used to describe accurately the curved boundaries. At a common side shared by a p-element and an arbitrary number of h-elements, the field variables are minimized in the least square sense with respect to the degrees-of-freedom of the h-elements. This leads to a set of equations which relate the degrees-of-freedom of the coupled elements on the shared side. The method is applied to the calculation of frequencies for plates with curvilinear plan-forms. The effects of shear deformation and rotary inertia are taken into account. The frequencies are obtained for a sectorial plate with simply supported radial edges and free circular edge, an annular sectorial plate with simply supported radial edges and clamped circular edges, and a circular plate with one concentric ring support. Furthermore, new accurate frequencies are given for a fully clamped square plate with a corner cut-out. Constant meshes are used and convergence is sought by increasing progressively the degree p of the interpolating polynomial. The fast convergence and high accuracy of the method are validated through convergence and comparison studies.     

Complex fluid simulations with the parallel tree-based Lattice Boltzmann solver Musubi

We present the open source Lattice Boltzmann solver Musubi. It is part of the parallel simulation framework APES, which utilizes octrees to represent sparse meshes and provides tools from automatic mesh generation to post-processing. The octree mesh representation enables the handling of arbitrarily complex simulation domains, even on massively parallel systems. Local grid refinement is implemented by several interpolation schemes in Musubi. Various kernels provide different physical models based on stream-collide algorithms. These models can be computed concurrently and can be coupled with each other. This paper explains our approach to provide a flexible yet scalable simulation environment and elaborates its design principles and implementation details. The efficiency of our approach is demonstrated with a performance evaluation on two supercomputers and a comparison to the widely used Lattice Boltzmann solver Palabos.     

On the adjacencies of triangular meshes based on skeleton-regular partitions

For any 2D triangulation τ, the 1-skeleton mesh of τ is the wireframe mesh defined by the edges of τ, while that for any 3D triangulation τ, the 1-skeleton and the 2-skeleton meshes, respectively, correspond to the wireframe mesh formed by the edges of τ and the “surface” mesh defined by the triangular faces of τ. A skeleton-regular partition of a triangle or a tetrahedra, is a partition that globally applied over each element of a conforming mesh (where the intersection of adjacent elements is a vertex or a common face, or a common edge) produce both a refined conforming mesh and refined and conforming skeleton meshes. Such a partition divides all the edges (and all the faces) of an individual element in the same number of edges (faces). We prove that sequences of meshes constructed by applying a skeleton-regular partition over each element of the preceding mesh have an associated set of difference equations which relate the number of elements, faces, edges and vertices of the nth and (n−1)th meshes. By using these constitutive difference equations we prove that asymptotically the average number of adjacencies over these meshes (number of triangles by node and number of tetrahedra by vertex) is constant when n goes to infinity. We relate these results with the non-degeneracy properties of longest-edge based partitions in 2D and include empirical results which support the conjecture that analogous results hold in 3D.     

Monotone iterative methods for the adaptive finite element solution of semiconductor equations

Picard, Gauss–Seidel, and Jacobi monotone iterative methods are presented and analyzed for the adaptive finite element solution of semiconductor equations in terms of the Slotboom variables. The adaptive meshes are generated by the 1-irregular mesh refinement scheme. Based on these unstructured meshes and a corresponding modification of the Scharfetter–Gummel discretization scheme, it is shown that the resulting finite element stiffness matrix is an M-matrix which together with the Shockley–Read–Hall model for the generation–recombination rate leads to an existence–uniqueness–comparison theorem with simple upper and lower solutions as initial iterates. Numerical results of simulations on a MOSFET device model are given to illustrate the accuracy and efficiency of the adaptive and monotone properties of the present methods.     

Preventing deadlock during anisotropic 2D mesh adaptation in hp-adaptive FEM

The paper presents a grammar for anisotropic two-dimensional mesh adaptation in hp-adaptive Finite Element Method with rectangular elements. Expressing mesh transformations as grammar productions is useful for concurrency analysis thanks to exhibiting the partial causality order (Lamport relationship) between atomic operations. It occurs that a straightforward approach to modeling this process via grammar productions leads to potential deadlock in h-adaptation of the mesh. This fact is shown on a Petri net model of an exemplary adaptation. Therefore auxiliary productions are added to the grammar in order to ensure that any sequence of productions allowed by the grammar does not lead to a deadlock state. The fact that the enhanced grammar is deadlock-free is proven via a corresponding Petri net model. The proof has been performed by means of reachability graph construction and analysis. The paper is concluded with numerical simulations of magnetolluric measurements where the deadlock problem occurred.     

Shape regularity conditions for polygonal/polyhedral meshes,exemplified in a discontinuous Galerkin discretization

This article concerns shape regularity conditions on arbitrarily shaped polygonal/polyhedral meshes. In (J. Wang and X. Ye, A weak Galerkin mixed finite element method for second‐order elliptic problems, Math Comp 83 (2014), 2101–2126), a set of shape regularity conditions has been proposed, which allows one to prove important inequalities such as the trace inequality, the inverse inequality, and the approximation property of the L² projection on general polygonal/polyhedral meshes. In this article, we propose a simplified set of conditions which provides similar mesh properties. Our set of conditions has two advantages. First, it allows the existence of “small” edges/faces, as long as the shape of the polygon/polyhedron is regular. Second, coupled with an extra condition, we are now able to deal with nonquasiuniform meshes. As an example, we show that the discontinuous Galerkin method for Laplacian equations on arbitrarily shaped polygonal/polyhedral meshes, satisfying the proposed set of shape regularity conditions, achieves optimal rate of convergence. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 308–325, 2015     

A non-uniform basis order for the discontinuous Galerkin method of the acoustic and elastic wave equations

Here, we solve the time-dependent acoustic and elastic wave equations using the discontinuous Galerkin method for spatial discretization and the low-storage Runge-Kutta and Crank-Nicolson methods for time integration. The aim of the present paper is to study how to choose the order of polynomial basis functions for each element in the computational mesh to obtain a predetermined relative error. In this work, the formula 2p+1≈κhk, which connects the polynomial basis order p, mesh parameter h, wave number k, and free parameter κ, is studied. The aim is to obtain a simple selection method for the order of the basis functions so that a relatively constant error level of the solution can be achieved. The method is examined using numerical experiments. The results of the experiments indicate that this method is a promising approach for approximating the degree of the basis functions for an arbitrarily sized element. However, in certain model problems we show the failure of the proposed selection scheme. In such a case, the method provides an initial basis for a more general p-adaptive discontinuous Galerkin method.     

Toward anisotropic mesh construction and error estimation in the finite element method

Directional, anisotropic features like layers in the solution of partial differential equations can be resolved favorably by using anisotropic finite element meshes. An adaptive algorithm for such meshes includes the ingredients Error estimation and Information extraction/Mesh refinement. Related articles on a posteriori error estimation on anisotropic meshes revealed that reliable error estimation requires an anisotropic mesh that is aligned with the anisotropic solution. To obtain anisotropic meshes the so‐called Hessian strategy is used, which provides information such as the stretching direction and stretching ratio of the anisotropic elements. This article combines the analysis of anisotropic information extraction/mesh refinement and error estimation (for several estimators). It shows that the Hessian strategy leads to well‐aligned anisotropic meshes and, consequently, reliable error estimation. The underlying heuristic assumptions are given in a stringent yet general form. Numerical examples strengthen the exposition. Hence the analysis provides further insight into a particular aspect of anisotropic error estimation. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 625–648, 2002; DOI 10.1002/num.10023     

L 2 error estimates and superconvergence of the finite volume element methods on quadrilateral meshes

This paper is concerned with the finite volume element methods on quadrilateral mesh for second-order elliptic equation with variable coefficients. An error estimate in L ² norm is shown on the quadrilateral meshes consisting of h ²-parallelograms. Superconvergence of numerical solution is also derived in an average gradient norm on h ²-uniform quadrilateral meshes. Numerical examples confirm our theoretical conclusions.