Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics

Most of the recently proposed computational methods for solving partial differential equations on multiprocessor architectures stem from the 'divide and conquer' paradigm and involve some form of domain decomposition. For those methods which also require grids of points or patches of elements, it is often necessary to explicitly partition the underlying mesh, especially when working with local memory parallel processors. In this paper, a family of cost-effective algorithms for the automatic partitioning of arbitrary two- and three-dimensional finite element and finite difference meshes is presented and discussed in view of a domain decomposed solution procedure and parallel processing. The influence of the algorithmic aspects of a solution method (implicit/explicit computations), and the architectural specifics of a multiprocessor (SIMD/MIMD, startup/transmission time), on the design of a mesh partitioning algorithm are discussed. The impact of the partitioning strategy on load balancing, operation count, operator conditioning, rate of convergence and processor mapping is also addressed. Finally, the proposed mesh decomposition algorithms are demonstrated with realistic examples of finite element, finite volume, and finite difference meshes associated with the parallel solution of solid and fluid mechanics problems on the iPSC/2 and iPSC/860 multiprocessors.     

Stress intensity factor predictions: Comparison and round-off error

Practical steps required to obtain robust finite element triangular meshes for crack path and stress intensity calculation purposes are evaluated, and techniques to use their predictions to calculate fatigue lives, including load interaction effects, are discussed. These steps address: (a) how to simulate efficiently 2D crack paths under bi-axial loading using automatic remeshing schemes; (b) how to choose the best method to calculate stress intensity factors along the crack path; and (c) how the numerical problems associated with excessive FE mesh refinement along the crack path may affect predictions. Various modeling strategies are compared using different crack geometries and mesh refinements to quantify their performance, particularly when the elements around the crack tip are very small compared with the elements far from it. It is shown that, contrary to many other stress analysis applications, excessive mesh refinement may significantly degrade the calculation accuracy in crack problems. A limit for the elements size ratio is clearly established.     

Quality improvements in extruded meshes using topologically adaptive generalized elements

This paper describes a method to extrude near‐body volume meshes that exploits topologically adaptive generalized elements to improve local mesh quality. Specifically, an advancing layer algorithm for extruding volume meshes from surface meshes of arbitrary topology, appropriate for viscous fluid flows, is discussed. First, a two‐layer reference mesh is generated from the layer initial surface mesh by extruding along the local surface normals. The reference mesh is then smoothed using a Poisson equation. Local quality improvement operations such as edge collapse, face refinement, and local reconnection are performed in each layer to drive the mesh toward isotropy and improve the transition from the extruded mesh to a void‐filling tetrahedral mesh. A few example meshes along with quality plots are presented to demonstrate the efficacy of this approach. Copyright © 2004 John Wiley & Sons, Ltd.     

Dispersion analysis of finite element semidiscretizations of the two-dimensional wave equation

The dispersive properties of finite element semidiscretizations of the two-dimensional wave equation are examined. Both bilinear quadrilateral elements and linear triangular elements are considered with diagonal and nondiagonal mass matrices in uniform meshes. It is shown that mass diagonalization and underintegration of the stiffness matrix of the quadrilateral element markedly increases dispersive errors. The dispersive properties of triangular meshes depends on the mesh layout; certain layouts introduce optical modes which amplify numerically induced oscillations and dispersive errors. Compared to the five-point Laplacian finite difference operator, rectangular finite element semidiscretizations with consistent mass matrices provide superior fidelity regardless of the wave direction.     

An automatic adaptive refinement finite element procedure for 2D elastostatic analysis

An automatic adaptive refinement procedure for finite element analysis is presented. The procedure is applied to two-dimensional elastostatic problems to obtain solutions of prescribed accuracy. Through the combined use of new mesh generator using contour developed by Lo¹ and the concept of strain energy concentration, high-quality graded finite element meshes are generated. The whole process is fully automatic and no user intervention is required during the successive cycles of the mesh refinements. The Zienkiewicz and Zhu² error estimator is found to be effective and has been adopted for the present implementation. In the numerical examples tested, the error estimator gives an accurate error norm estimation and the effectivity index of the estimator converges to a value close to unity.     

An alternative pseudoperipheral node finder for resequencing schemes

Many resequencing algorithms for reducing the bandwidth, profile and wavefront of sparse symmetric matrices have been published. In finite element applications, the sparsity of a matrix is related to the nodal ordering of the finite element mesh. Some of the most successful algorithms, which are based on graph theory, require a pair of starting pseudoperipheral nodes. These nodes, located at nearly maximal distance apart, are determined using heuristic schemes. This paper presents an alternative pseadoperipheral node finder, which is based on the algorithm developed by Gibbs, Poole and Stockmeyer. This modified scheme is suitable for nodal reordering of finite meshes and provides more consistency in the effective selection of the starting nodes in problems where the selection becomes arbitrary due to the number of candidates for these starting nodes. This case arises, in particular, for square meshes. The modified scheme was implemented in Gibbs-Poole-Stockmeyer, Gibbs-King and Sloan algorithms. Test problems of these modified algorithms include: (1) Everstine's 30 benchmark problems; (2) sets of square, rectangular and annular (cylindrical) finite element meshes with quadrilateral and triangular elements; and (3) additional examples originating from mesh refinement schemes. The results demonstrate that the modifications to the original algorithms contribute to the improvement of the reliability of all the resequencing algorithms tested herein for the nodal reordering of finite element meshes.     

Adaptive error analysis in seepage problems

Numerical experiments in adapting variations of a computationally simple error estimator (the Zienkiewicz-Zhu estimator) to an existing finite element code are shown. The error estimator used allows both overall and local errors to be estimated. From the local estimates of error, refinements of the mesh are calculated to reach a prescribed error tolerance. These calculated refinements are used by a mesh refiner to produce a modified mesh which lowers the overall error to the prescribed value while keeping the mesh as crude as possible. The physical example on which these numerical experiments are performed is that of free surface flow through an earth dam with a toe drain. It is also shown how the problem formulation affects the error analysis and how the choice of computational scheme affects the mesh adaptation.     

An energy basis for mesh refinement of structural continua

This paper proposes an energy measure of discretization error and examines its use for finite element mesh refinement in the analysis of structural continua. The measure is based on the strain energy contributions by the admissible displacement response modes of an element. An element energy differential is obtained by separating the energy contribution due to the higher displacement modes. This measure is suitable for use with all element types based on the direct stiffness method. The paper presents results of membrane, plate and shell analyses using the measure. It compares sequences of analysis with successively improved meshes to explore the quality of the measure. It concludes that the element energy difference provides a quantitative measure of the efficiency of a given mesh and a qualitative measure which is useful for selecting further mesh refinements, when necessary.     

Delaunay versus max-min solid angle triangulations for three-dimensional mesh generation

The Delaunay triangulation has been used in several methods for generating finite element tetrahedral meshes in three-dimensional polyhedral regions. Other types of three-dimensional triangulations are possible, such as a triangulation satisfying a local max-min solid angle criterion. In this paper, we present experimental results to show that max-min solid angle triangulations are better than Delaunay triangulations for finite element tetrahedral meshes, since the former type of triangulations contains tetrahedra of better shape than the latter type. We also describe how mesh points are generated and triangulated in our tetrahedral mesh generation method.     

An automatic adaptive refinement procedure using triangular and quadrilateral meshes

An automatic adaptive refinement procedure for finite element analysis for two-dimensional stress analysis problems is presented. Through the combined use of the new mesh generator developed by the authors (to appear) for adaptive mesh generation and the Zienkiewicz-Zhu [Int. J. numer. Meth. Engng31, 1331–1382 (1992)] error estimator based on the superconvergent patch recovery technique, an adaptive refinement procedure can be formulated which can achieve the aimed accuracy very economically in one or two refinement steps. A simple method is also proposed to locate the existence and the position of singularities in the problem domain. Hence, little or no a priori knowledge about the location and strength of the singularities is required. The entire adaptive refinement procedure has been made fully automatic and no user intervention during successive cycles of mesh refinements is needed. The robustness and reliability of the refinement procedure have been tested by solving difficult practical problems involving complex domain geometry with many singularities. We found that in all the examples studied, regardless of the types of meshes employed, triangular and quadrilateral meshes, nearly optimal overall convergence rate is always achieved.     

An adaptive MsFEM for nonperiodic viscoelastic composites

We present a modification of the multiscale finite element method (MsFEM) for modeling of heterogeneous viscoelastic materials and an enhancement of this method by the adaptive generation of both meshes, ie, a macroscale coarse one and a microscale fine one. The fine mesh refinements are performed independently within coarse elements adjusting the microscale discretization to the microstructure, whereas the coarse mesh adaptation optimizes the macroscale approximation. Besides the coupling of the hp‐adaptive finite element method with the MsFEM we propose a modification of the MsFEM to accommodate for the analysis of transient nonlinear problems. We illustrate the efficiency and accuracy of the new approach for a number of benchmark examples, including the modeling of functionally graded material, and demonstrate the potential of our improvement for upscaling nonperiodic and nonlinear composites.     

A second-order face-centred finite volume method on general meshes with automatic mesh adaptation

A second-order face-centred finite volume strategy on general meshes is proposed. The method uses a mixed formulation in which a constant approximation of the unknown is computed on the faces of the mesh. Such information is then used to solve a set of problems, independent cell-by-cell, to retrieve the local values of the solution and its gradient. The main novelty of this approach is the introduction of a new basis function, utilised for the linear approximation of the primal variable in each cell. Contrary to the commonly used nodal basis, the proposed basis is suitable for computations on general meshes, including meshes with different cell types. The resulting approach provides second-order accuracy for the solution and first-order for its gradient, without the need of reconstruction procedures, is robust in the incompressible limit and insensitive to cell distortion and stretching. The second-order accuracy of the solution is exploited to devise an automatic mesh adaptivity strategy. An efficient error indicator is obtained from the computation of one extra local problem, independent cell-by-cell, and is used to drive mesh adaptivity. Numerical examples illustrating the approximation properties of the method and of the mesh adaptivity procedure are presented. The potential of the proposed method with automatic mesh adaptation is demonstrated in the context of microfluidics.     

Parallel adaptive finite element computations with hierarchical preconditioning

A parallel implementation of an adaptive finite element program is treated which is characterized by an underlying parallel dynamic data structure based on linked lists and tree structures. In conjunction with a conjugate gradient solver an efficient methodology for treating adaptive finite element systems is shown. This is achieved by preconditioning using hierarchical bases with and without a coarse grid solver and by new methods of quasi-optimal load balancing. The different levels of nested meshes needed for preconditioning are governed either by global or by adaptive refinements. A termination algorithm based on the vector method is implemented for the non deterministic adaptive mesh refinement procedure. The problems concerning load balancing due to adaptive refinement are solved by a dynamic load balancing for the nodes.This work has been supported by Deutsche Forschungsgemeinschaft under grant no. Ste238/26.     

Mesh objective continuum damage models for ductile fracture

During machining processes, the work piece material is subjected to high deformation rates, increased temperature, large plastic deformations, damage evolution and fracture. In this context the Johnson‐Cook failure model is often used even though it exhibits pathological mesh size dependence. To remove the mesh size sensitivity, a set of mesh objective damage models is proposed based on a local continuum damage formulation combined with the concept of a scalar damage phase field. The first model represents a mesh objective augmentation of the well‐established element removal model, whereas the second one degrades the continuum stress in a smooth fashion. Plane strain plate and hat specimens are used in the finite element simulations, with the restriction to the temperature and rate independent cases. To investigate the influence of mesh distortion, a structured and an unstructured meshes were used for the respective specimen. For structured meshes, the results clearly show that the pathological mesh size sensitivity is removed for both models. When considering unstructured meshes, the mesh size sensitivity is more complex as revealed by the considered hat‐specimen shear test. Nevertheless, the present work indicates that the proposed models can predict realistic ductile failure behaviors in a mesh objective fashion. Copyright © 2015 John Wiley & Sons, Ltd.     

Development of physically based meshes for two‐dimensional models of meandering channel flow

The choice of mesh generation and numerical solution strategies for two‐dimensional finite element models of fluvial flow have previously been based chiefly on experience and rule of thumb. This paper develops a rationale for the finite element modelling of flow in river channels, based on a study of flow around an annular reach. Analytical solutions of the two‐dimensional Shallow Water (St. Venant) equations are developed in plane polar co‐ordinates, and a comparison with results obtained from the TELEMAC‐2‐D finite element model indicates that of the two numerical schemes for the advection terms tested, a flux conservative transport scheme gives better results than a streamline upwind Petrov–Galerkin technique. In terms of mesh discretization, the element angular deviation is found to be the most significant control on the accuracy of the finite element solutions. A structured channel mesh generator is therefore developed which takes local channel curvature into account in the meshing process. Results indicate that simulations using curvature‐dependent meshes offer similar levels of accuracy to finer meshes made up of elements of uniform length, with the added advantage of improved model mass conservation in regions of high channel curvature. Copyright © 2000 John Wiley & Sons, Ltd.     

Adaptive finite element mesh refinement techniques inthree-dimensional micromagnetic modeling

Two different methods to adaptively refine tetrahedral finite element meshes are presented. The influence of the mesh refinement on the obtained results of micromagnetic calculations is demonstrated for the case of magnetization patterns in soft magnetic platelets. The specific addition of vertices and finite elements in inhomogeneous regions is used to resolve the magnetic structure on small length scales. A method discussed in detail is the shrinking of finite elements in regions with strong inhomogeneities     

Arbitrary placement of local meshes in a global mesh by the interface‐element method (IEM)

A new method is proposed to place local meshes in a global mesh with the aid of the interface‐element method (IEM). The interface‐elements use moving least‐square (MLS)‐based shape functions to join partitioned finite‐element domains with non‐matching interfaces. The supports of nodes are defined to satisfy the continuity condition on the interfaces by introducing pseudonodes on the boundaries of interface regions. Particularly, the weight functions of nodes on the boundaries of interface regions span only neighbouring nodes, ensuring that the resulting shape functions are identical to those of adjoining finite‐elements. The completeness of the shape functions of the interface‐elements up to the order of basis provides a reasonable transfer of strain fields through the non‐matching interfaces between partitioned domains. Taking these great advantages of the IEM, local meshes can be easily inserted at arbitrary places in a global mesh. Several numerical examples show the effectiveness of this technique for modelling of local regions in a global domain. Copyright © 2003 John Wiley & Sons, Ltd.     

The quasi-uniformity condition for reproducing kernel element method meshes

The reproducing kernel element method is a hybrid between finite elements and meshfree methods that provides shape functions of arbitrary order and continuity yet retains the Kronecker-δ property. To achieve these properties, the underlying mesh must meet certain regularity constraints. This paper develops a precise definition of these constraints, and a general algorithm for assessing a mesh is developed. The algorithm is demonstrated on several mesh types. Finally, a guide to generation of quasi-uniform meshes is discussed.     

Tetrahedral mesh generation based on space indicator functions

An algorithm for the generation of tetrahedral volume meshes is developed for highly irregular objects specified by volumetric representations such as domain indicator functions and tomography data. It is based on red–green refinement of an initial mesh derived from a body‐centered cubic lattice. A quantitative comparison of alternative types of initial meshes is presented. The minimum set of best‐quality green refinement schemes is identified. Boundary conformity is established by deforming or splitting surface‐crossing elements. Numerical derivatives of input data are strictly avoided. Furthermore, the algorithm features surface‐adaptive mesh density based on local surface roughness, which is an integral property of finite surface portions. Examples of applications are presented for computer tomography of porous media. Copyright © 2012 John Wiley & Sons, Ltd.     

Channelled waves in anisotropic mesh metamaterials

Channelled waves in 2D periodic anisotropic L-C mesh metamaterials have been investigated. Circuit simulation and the newly developed analytical model of a unit cell have demonstrated full qualitative agreement for both lossless and lossy cases. Isofrequencies for a lattice unit cell and the circuit simulations of finite meshes have shown that propagating waves are channelled from a point source as pencil beams which can travel only along specific trajectories. The beam direction varies with frequency, and at resonance frequency omega=1/(LC)^1/2, the phase and group velocities of the transmitted wave are orthogonal. The effect of losses was explored, and it is shown that losses can cause qualitative changes of the channelled wave type. It is shown that the channelled waves do not follow the laws of geometrical optics (Snell's law, specular reflection and so on) at the interfaces of L-C meshes but are governed by the conditions of phase synchronism and impedance matching. Only in the special case of dual L-C and C-L meshes with the interface parallel to the axis of rectangular grid excited at the resonance frequency (X=1) do the channels follow the trajectories of optical rays. A planar mesh test cell has been designed and applied to retrieving the unit cell L-C parameters from the S-parameter measurements