Stochastic Domain Decomposition for Time Dependent Adaptive Mesh Generation

The efficient generation of meshes is an important component in the numerical solution of problems in physics and engineering. Of interest are situations where global mesh quality and a tight coupling to the solution of the physical partial differential equation (PDE) is important. We consider parabolic PDE mesh generation and present a method for the construction of adaptive meshes in two spatial dimensions using stochastic domain decomposition that is suitable for an implementation in a multi- or many-core environment. Methods for mesh generation on periodic domains are also provided. The mesh generator is coupled to a time dependent physical PDE and the system is evolved using an alternating solution procedure. The method uses the stochastic representation of the exact solution of a parabolic linear mesh generator to find the location of an adaptive mesh along the (artificial) subdomain interfaces. The deterministic evaluation of the mesh over each subdomain can then be obtained completely independently using the probabilistically computed solutions as boundary conditions. A small scaling study is provided to demonstrate the parallel performance of this stochastic domain decomposition approach to mesh generation. We demonstrate the approach numerically and compare the mesh obtained with the corresponding single domain mesh using a representative mesh quality measure.     

On using meshes of mixed element types in adaptive finite element analysis

Four different automatic mesh generators capable of generating either triangular meshes or hybrid meshes of mixed element types have been used in the mesh generation process. The performance of these mesh generators were tested by applying them to the adaptive finite element refinement procedure. It is found that by carefully controlling the quality and grading of the quadrilateral elements, an increase in efficiency over pure triangular meshes can be achieved. Furthermore, if linear elements are employed, an optimal hybrid mesh can be obtained most economically by a combined use of the mesh coring technique suggested by Lo and Lau and a selective removal of diagonals from the triangular element mesh. On the other hand, if quadratic elements are used, it is preferable to generate a pure triangular mesh first, and then obtain a hybrid mesh by merging of triangles.     

A constrained optimization approach to finite element mesh smoothing

The quality of a finite element solution has been shown to be affected by the quality of the underlying mesh. A poor mesh may lead to unstable and/or inaccurate finite element approximations. Mesh quality is often characterized by the “smoothness” or “shape” of the elements (triangles in 2-D or tetrahedra in 3-D). Most automatic mesh generators produce an initial mesh where the aspect ratio of the elements are unacceptably high. In this paper, a new approach to produce acceptable quality meshes from a topologically valid initial mesh is presented. Given an initial mesh (nodal coordinates and element connectivity), a “smooth” final mesh is obtained by solving a constrained optimization problem. The variables for the iterative optimization procedure are the nodal coordinates (excluding, the boundary nodes) of the finite element mesh, and appropriate bounds are imposed on these to prevent an unacceptable finite element mesh. Examples are given of the application of the above method for 2- and 3-D meshes generated using automatic mesh generators. Results indicate that the new method not only yields better quality elements when compared with the traditional Laplacian smoothing, but also guarantees a valid mesh unlike the Laplacian method.     

Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation

Several promising approaches for hexahedral mesh generation work as follows: Given a prescribed quadrilateral surface mesh they first build the combinatorial dual of the hexahedral mesh. This dual mesh is converted into the primal hexahedral mesh, and finally embedded and smoothed into the given domain. Two such approaches, the modified whisker weaving algorithm by Folwell and Mitchell, as well as a method proposed by the author, rely on an iterative elimination of certain dual cycles in the surface mesh. An intuitive interpretation of the latter method is that cycle eliminations correspond to complete sheets of hexahedra in the volume mesh.

Although these methods can be shown to work in principle, the quality of the generated meshes heavily relies on the dual cycle structure of the given surface mesh. In particular, it seems that difficulties in the hexahedral meshing process and poor mesh qualities are often due to self-intersecting dual cycles. Unfortunately, all previous work on quadrilateral surface mesh generation has focused on quality issues of the surface mesh alone but has disregarded its suitability for a high-quality extension to a three-dimensional mesh.

In this paper, we develop a new method to generate quadrilateral surface meshes without self-intersecting dual cycles. This method reuses previous b-matching problem formulations of the quadrilateral mesh refinement problem. The key insight is that the b-matching solution can be decomposed into a collection of simple cycles and paths of multiplicity two, and that these cycles and paths can be consistently embedded into the dual surface mesh.

A second tool uses recursive splitting of components into simpler subcomponents by insertion of internal two-manifolds. We show that such a two-manifold can be meshed with quadrilaterals such that the induced dual cycle structure of each subcomponent is free of self-intersections if the original component satisfies this property. Experiments show that we can achieve hexahedral meshes with a good quality.     

A Numerical Study of Blowup in the Harmonic Map Heat Flow Using the MMPDE Moving Mesh Method

The numerical solution of the harmonic heat map flow problems with blowup in finite or infinite time is considered using an adaptive moving mesh method. A properly chosen monitor function is derived so that the moving mesh method can be used to simulate blowup and produce accurate blowup profiles which agree with formal asymptotic analysis. Moreover, the moving mesh method has finite time blowup when the underlying continuous problem does. In situations where the continuous problem has infinite time blowup, the moving mesh method exhibits finite time blowup with a blowup time tending to infinity as the number of mesh points increases. The inadequacy of a uniform mesh solution is clearly demonstrated.     

A model to simplify 2D triangle meshes with irregular shapes

We present a 2D triangle mesh simplification model which is able to produce high quality approximations of any original planar mesh, regardless of the shape of the original mesh. This method consists of two phases: a self-organizing algorithm and a triangulation algorithm. The self-organizing algorithm is an unsupervised incremental clustering algorithm which provides us a set of nodes representing the best approximation of the original mesh. The triangulation algorithm reconstructs the simplified mesh from the planar points obtained by the self-organizing training process. Some examples are detailed with the purpose of demonstrating the ability of the model to perform the task of simplifying an original mesh with irregular shape.     

Parallel anisotropic mesh adaptivity with dynamic load balancing for cardiac electrophysiology

Simulations in cardiac electrophysiology generally use very fine meshes and small time steps to resolve highly localized wavefronts. This expense motivates the use of mesh adaptivity, which has been demonstrated to reduce the overall computational load. However, even with mesh adaptivity performing such simulations on a single processor is infeasible. Therefore, the adaptivity algorithm must be parallelised. Rather than modifying the sequential adaptive algorithm, the parallel mesh adaptivity method introduced in this paper focuses on dynamic load balancing in response to the local refinement and coarsening of the mesh. In essence, the mesh partition boundary is perturbed away from mesh regions of high relative error, while also balancing the computational load across processes. The parallel scaling of the method when applied to physiologically realistic heart meshes is shown to be good as long as there are enough mesh nodes to distribute over the available parallel processes. It is shown that the new method is dominated by the cost of the sequential adaptive mesh procedure and that the parallel overhead of inter-process data migration represents only a small fraction of the overall cost.     

解Stokes特征值问题的一种两水平稳定化有限元方法

基于局部Gauss积分,研究了解Stokes特征值问题的一种两水平稳定化有限元方法．该方法涉及在网格步长为H的粗网格上解一个Stokes特征值问题,在网格步长为h=O(H2)的细网格上解一个Stokes问题．这样使其能够仍旧保持最优的逼近精度,求得的解和一般的稳定化有限元解具有相同的收敛阶,即直接在网格步长为h的细网格上解一个Stokes特征值问题．因此,该方法能够节省大量的计算时间．数值试验验证了理论结果．     

Combined unstructured and hanging-node-based remeshing with boundary control for metal forming simulations

During finite element simulation of metal forming process, the mesh which represents the workpiece undergoes extreme large deformation, which could result in highly distorted mesh and numerical failure in simulation. To overcome the problem and improve computation efficiency, advancing front quad meshing technique and non–conforming mesh refinement approach are combined to generate new mesh according to desired mesh size distribution. Application of the combined remeshing strategy to rolling simulation will be presented. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

TWO-GRID CHARACTERISTIC FINITE VOLUME METHODS FOR NONLINEAR PARABOLIC PROBLEMS＊

In this work, two-grid characteristic finite volume schemes for the nonlinear parabolic problem are considered. In our algorithms, the diffusion term is discretized by the finite volume method, while the temporal differentiation and advection terms are treated by the characteristic scheme. Under some conditions about the coefficients and exact solution, optimal error estimates for the numerical solution are obtained. Furthermore, the two- grid characteristic finite volume methods involve solving a nonlinear equation on coarse mesh with mesh size H, a large linear problem for the Oseen two-grid characteristic finite volume method on a fine mesh with mesh size h = O（H2） or a large linear problem for the Newton two-grid characteristic finite volume method on a fine mesh with mesh size h = 0（I log hll/2H3）. These methods we studied provide the same convergence rate as that of the characteristic finite volume method, which involves solving one large nonlinear problem on a fine mesh with mesh size h. Some numerical results are presented to demonstrate the efficiency of the proposed methods.     

A dynamic data structure suitable for adaptive mesh refinement in finite element method

This paper describes a dynamic data structure and its implementation, used for an optimum mesh generator. The implementation of this mesh generator was a part of a software package implemented to solve electromagnetic field problems using the finite element method. This mesh generator takes advantage of the Delaunay algorithm, which maximizes the summation of the smallest angles in all triangles and thus creates a mesh that is proved to be an optimum mesh for use in the finite element method. The dynamic data structure is explained and the source code is reviewed. The programs have been written in Pascal programming language.     

Interpolation by quadratic splines

Convergence properties of quadratic spline interpolation of continuous functions that does not necessarily take place at the midpoints of mesh intervals are investigated. A theorem giving lower bounds on the elements of the inverse of certain tridiagonal matrices is proved. This result is used to precisely relate the norm of certain interpolating projections to the points of interpolation and local mesh ratios. It is shown, for example, that for Lipschitz continuous functions, any choice of interpolation points, one in each mesh interval, uniformly bounded away from the mesh points, yields convergence at the best possible rate with no mesh ratio restriction.     

Error estimation,adaptivity and data transfer in enriched plasticity continua to analysis of shear band localization

In this paper, an adaptive FE analysis is presented based on error estimation, adaptive mesh refinement and data transfer for enriched plasticity continua in the modelling of strain localization. As the classical continuum models suffer from pathological mesh-dependence in the strain softening models, the governing equations are regularized by adding rotational degrees-of-freedom to the conventional degrees-of-freedom. Adaptive strategy using element elongation is applied to compute the distribution of required element size using the estimated error distribution. Once a new mesh is generated, state variables and history-dependent variables are mapped from the old finite element mesh to the new one. In order to transfer the history-dependent variables from the old to new mesh, the values of internal variables available at Gauss point are first projected at nodes of old mesh, then the values of the old nodes are transferred to the nodes of new mesh and finally, the values at Gauss points of new elements are determined with respect to nodal values of the new mesh. Finally, the efficiency of the proposed model and computational algorithms is demonstrated by several numerical examples.     

Asymptotic behaviour of the containment of certain mesh patterns

We present some results on the proportion of permutations of length n containing certain mesh patterns as n grows large, and give exact enumeration results in some cases. In particular, we focus on mesh patterns where entire rows and columns are shaded. We prove some general results which apply to mesh patterns of any length, and then consider mesh patterns of length four. An important consequence of these results is to show that the proportion of permutations containing a mesh pattern can take a wide range of values between 0 and 1.     

Stress recovery procedure for solving boundary value problems in the mechanics of a deformable solid by the finite element method

A stress recovery procedure, based on the determination of the forces at the mesh points using a stiffness matrix obtained by the finite element method for the variational Lagrange equation, is described. The vectors of the forces reduced to the mesh points are constructed for the known stiffness matrices of the elements using the displacements at the mesh points found from the solution of the problem. On the other hand, these mesh point forces are determined in terms of the unknown forces distributed over the surface of an element and given shape functions. As a result, a system of Fredholm integral equations of the first kind is obtained, the solution of which gives these distributed forces. The stresses at the mesh points are determined for the values of these forces found on the surfaces of the finite element mesh (including at the mesh points) using the Cauchy relations, which relate the forces, stresses and the normal to the surface. The special features of the use of the stress recovery procedure are demonstrated for a plane problem in the linear theory of elasticity.     

Smooth interpolation of a mesh of curves

The interpolation of a mesh of curves by a smooth regularly parametrized surface with one polynomial piece per facet is studied. Not every mesh with a well-defined tangent plane at the mesh points has such an interpolant: the curvature of mesh curves emanating from mesh points with an even number of neighbors must satisfy an additional vertex enclosure constraint. The constraint is weaker than previous analyses in the literature suggest and thus leads to more efficient constructions. This is illustrated by an implemented algorithm for the local interpolation of a cubic curve mesh by a piecewise [bi]quarticC ¹ surface. The scheme is based on an alternative sufficient constraint that forces the mesh curves to interpolate second-order data at the mesh points. Rational patches, singular parametrizations, and the splitting of patches are interpreted as techniques to enforce the vertex enclosure constraint.Communicated by Wolfgang Dahmen.     

Unstructured tetrahedral mesh generation technology

We present a robust unstructured tetrahedral mesh generation technology. This technology is a combination of boundary discretization methods, an advancing front technique and a Delaunay-based mesh generation technique. For boundary mesh generation we propose four different approaches using analytical boundary parameterization, interface with CAD systems, surface mesh refinement, and constructive solid geometry. These methods allow us to build a flexible grid generation technology with a user friendly interface.     

Composite mesh difference methods for elliptic boundary value problems

Summary The purpose of this paper is to develop composite mesh difference methods for elliptic boundary value problems over regions with curved, smooth boundaries. A curved mesh will cover an annular strip along the boundary of the region which is included in the mesh. For the rest of the region and for a suitable inner part of the annular strip a square or rectangular mesh will be used. On each mesh a difference approximation is set up as well as couplings between them. Only second order methods for second order elliptic equations will be treated in detail.This research was supported by the Swedish Institute for Applied Mathematics (ITM)     

Bakhvalov-Shishkin网格上求解边界层问题的差分进化算法

该文在Bakhvalov-Shishkin网格上求解具有左边界层或右边界层的对流扩散方程,并采用差分进化算法对Bakhvalov-Shishkin网格中的参数进行优化,获得了该网格上具有最优精度的数值解.对三个算例进行了数值模拟,数值结果表明:采用差分进化算法求解具有较高的计算精度和收敛性,特别是边界层的数值解精度明显...     

Finite Element Simulations with Adaptively Moving Mesh for the Reaction Diffusion System

A moving mesh method is proposed for solving reaction-diffusion equations. The finite element method is used to solving the partial different equation system, and an efficient scheme is applied to implement mesh moving. In the practical calculations, the moving mesh step and the problem equation solver are performed alternatively. Serveral numerical examples are presented, including the Gray-Scott, the Activator-Inhibitor and a case with a growing domain. It is illustrated numerically that the moving mesh method costs much lower, compared with the numerical schemes on a fixed mesh. Even in the case of complex pattern dynamics described by the reaction-diffusion systems, the adapted meshes can capture the details successfully.