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.     

Automatic generation of transitional meshes

Advances in commercial computer‐aided design software have made finite element analysis with three‐dimensional solid finite elements routinely available. Since these analyses usually confine themselves to those geometrical objects for which particular CAD systems can produce finite element meshes, expanding the capability of analyses becomes an issue of expanding the capability of generating meshes. This paper presents a method for stitching together two three‐dimensional meshes with diverse elements that can include tetrahedral, pentahedral and hexahedral solid finite elements. The stitching produces a mesh that coincides with the edges which already exist on the portion of boundaries that will be joined. Moreover, the transitional mesh does not introduce new edges on these boundaries. Since the boundaries of the regions to be stitched together can have a mixture of triangles and quadrilaterals, tetrahedral and pyramidal elements provide the transitional elements required to honor these constraints. On these boundaries a pyramidal element shares its base face with the quadrilateral faces of hexahedra and pentahedra. Tetrahedral elements share a face with the triangles on the boundary. Tetrahedra populate the remaining interior of the transitional region. Copyright © 2001 John Wiley & Sons, Ltd.     

A non‐oscillatory method for spallation studies

This paper introduces a non‐oscillatory method, the finite element flux‐corrected transport (FE‐FCT) method for spallation studies. This method includes the implementation of a one‐dimensional FCT algorithm into a total Lagrangian finite element method. Consequently, the FE‐FCT method can efficiently eliminate fluctuations behind shock wave fronts without smearing them. In multidimensional simulations, the one‐dimensional FCT algorithm is used on each grid line of the structured meshes to correct the corresponding component of nodal velocities separately. The requirement of structured meshes is satisfied by using an implicit function so that arbitrary boundaries of the simulated object can be described. In this paper, the proposed FE‐FCT method is applied in spallation studies. One‐ and two‐dimensional examples show this non‐oscillatory method could be one of the candidates to accurately predict spallation and the spall thickness. Copyright © 2005 John Wiley & Sons, Ltd.     

Clustered generalized finite element methods for mesh unrefinement,non‐matching and invalid meshes

In spite of significant advancements in automatic mesh generation during the past decade, the construction of quality finite element discretizations on complex three‐dimensional domains is still a difficult and time demanding task. In this paper, the partition of unity framework used in the generalized finite element method (GFEM) is exploited to create a very robust and flexible method capable of using meshes that are unacceptable for the finite element method, while retaining its accuracy and computational efficiency. This is accomplished not by changing the mesh but instead by clustering groups of nodes and elements. The clusters define a modified finite element partition of unity that is constant over part of the clusters. This so‐called clustered partition of unity is then enriched to the desired order using the framework of the GFEM. The proposed generalized finite element method can correctly and efficiently deal with: (i) elements with negative Jacobian; (ii) excessively fine meshes created by automatic mesh generators; (iii) meshes consisting of several sub‐domains with non‐matching interfaces. Under such relaxed requirements for an acceptable mesh, and for correctly defined geometries, today's automated tetrahedral mesh generators can practically guarantee successful volume meshing that can be entirely hidden from the user. A detailed technical discussion of the proposed generalized finite element method with clustering along with numerical experiments and some implementation details are presented. Copyright © 2006 John Wiley & Sons, Ltd.     

Automatic generation of anisotropic quadrilateral meshes on three‐dimensional surfaces using metric specifications

A new algorithm for constructing full quadrilateral anisotropic meshes on 3D surfaces is proposed in this paper. The proposed method is based on the advancing front and the systemic merging techniques. Full quadrilateral meshes are constructed by systemically converting triangular elements in the background meshes into quadrilateral elements.By using the metric specifications to describe the element characteristics, the proposed algorithm is applicable to convert both isotropic and anisotropic triangular meshes into full quadrilateral meshes. Special techniques for generating anisotropic quadrilaterals such as new selection criteria of base segment for merging, new approaches for the modifications of the background mesh and construction of quadrilateral elements, are investigated and proposed in this study. Since the final quadrilateral mesh is constructed from a background triangular mesh and the merging procedure is carried out in the parametric space, the mesh generator is robust and no expensive geometrical computation that is commonly associated with direct quadrilateral mesh generation schemes is needed. Copyright © 2002 John Wiley & Sons, Ltd.     

On the robustness and efficiency of integration algorithms for a 3D finite strain phenomenological SMA constitutive model

Most devices based on shape memory alloys experience large rotations and moderate or finite strains. This motivates the development of finite‐strain constitutive models together with the appropriate computational counterparts. To this end, in the present paper a three‐dimensional finite‐strain phenomenological constitutive model is investigated and a robust and efficient integration algorithm is proposed. Properly defining the variables, extensively used regularization schemes are avoided and a nucleation–completion criterion is defined. Moreover, introducing a logarithmic mapping, a new form of time‐discrete equations is proposed. The solution algorithm as well as a suitable initial guess for the resultant nonlinear equations are also deeply discussed. Extensive numerical tests are performed to show robustness as well as efficiency of the proposed integration algorithm. Implementation of the integration algorithm within a user‐defined subroutine UMAT in the commercial nonlinear finite element software ABAQUS/Standard makes also possible the solution of a variety of boundary value problems. The obtained results show the efficiency and robustness of the proposed approach and confirm the improved efficiency (in terms of solution CPU time) when a nucleation–completion criterion is used instead of regularization schemes, as well as when a logarithmic mapping is used for the time‐discrete evolution equation instead of an exponential mapping. Copyright © 2010 John Wiley & Sons, Ltd.     

A consistent point‐searching algorithm for solution interpolation in unstructured meshes consisting of 4‐node bilinear quadrilateral elements

To translate and transfer solution data between two totally different meshes (i.e. mesh 1 and mesh 2), a consistent point‐searching algorithm for solution interpolation in unstructured meshes consisting of 4‐node bilinear quadrilateral elements is presented in this paper. The proposed algorithm has the following significant advantages: (1) The use of a point‐searching strategy allows a point in one mesh to be accurately related to an element (containing this point) in another mesh. Thus, to translate/transfer the solution of any particular point from mesh 2 to mesh 1, only one element in mesh 2 needs to be inversely mapped. This certainly minimizes the number of elements, to which the inverse mapping is applied. In this regard, the present algorithm is very effective and efficient. (2) Analytical solutions to the local co‐ordinates of any point in a four‐node quadrilateral element, which are derived in a rigorous mathematical manner in the context of this paper, make it possible to carry out an inverse mapping process very effectively and efficiently. (3) The use of consistent interpolation enables the interpolated solution to be compatible with an original solution and, therefore guarantees the interpolated solution of extremely high accuracy. After the mathematical formulations of the algorithm are presented, the algorithm is tested and validated through a challenging problem. The related results from the test problem have demonstrated the generality, accuracy, effectiveness, efficiency and robustness of the proposed consistent point‐searching algorithm. Copyright © 1999 John Wiley & Sons, Ltd.     

Comparison of high‐order curved finite elements

Several finite element techniques used in domains with curved boundaries are discussed and compared, with particular emphasis in two issues: the exact boundary representation of the domain and the consistency of the approximation. The influence of the number of integration points on the accuracy of the computation is also studied. Two‐dimensional numerical examples, solved with continuous and discontinuous Galerkin formulations, are used to test and compare all these methodologies. In every example shown, the recently proposed NURBS‐enhanced finite element method (NEFEM) provides the maximum accuracy for a given spatial discretization, at least one order of magnitude more accurate than classical isoparametric finite element method (FEM). Moreover, NEFEM outperforms Cartesian FEM and p‐FEM, stressing the importance of the geometrical model as well as the relevance of a consistent approximation in finite element simulations. Copyright © 2011 John Wiley & Sons, Ltd.     

An efficient time‐domain perfectly matched layers formulation for elastodynamics on spherical domains

Many practical applications require the analysis of elastic wave propagation in a homogeneous isotropic media in an unbounded domain. One widely used approach for truncating the infinite domain is the so‐called method of perfectly matched layers (PMLs). Most existing PML formulations are developed for finite difference methods based on the first‐order velocity‐stress form of the elasticity equations, and they are not straight‐forward to implement using standard finite element methods (FEMs) on unstructured meshes. Some of the problems with these formulations include the application of boundary conditions in half‐space problems and in the treatment of edges and/or corners for time‐domain problems. Several PML formulations, which do work with FEMs have been proposed, although most of them still have some of these problems and/or they require a large number of auxiliary nodal history/memory variables. In this work, we develop a new PML formulation for time‐domain elastodynamics on a spherical domain, which reduces to a two‐dimensional formulation under the assumption of axisymmetry. Our formulation is well‐suited for implementation using FEMs, where it requires lower memory than existing formulations, and it allows for natural application of boundary conditions. We solve example problems on two‐dimensional and three‐dimensional domains using a high‐order discontinuous Galerkin (DG) discretization on unstructured meshes and explicit time‐stepping. We also study an approach for stabilization of the discrete equations, and we show several practical applications for quality factor predictions of micromechanical resonators along with verifying the accuracy and versatility of our formulation. Copyright © 2014 John Wiley & Sons, Ltd.     

Inverse mapping and distortion measures for quadrilaterals with curved boundaries

By using the theory of geodesics in differential geometry, inverse relations of the mapping for 8-node quadrilaterals with curved boundaries are derived and expressed in terms of the element geodesic co-ordinates defined at the local origin. The parameters in the expressions of the geodesic co-ordinates in terms of the isoparametric co-ordinates are suggested to be the distortion measures of the element. The mathematical meanings of these parameters can be discussed and explained by using the coefficient vectors in the equations defining the isoparametric co-ordinate transformation. This method of defining the element distortion measures is consistent and general, and can be applied to any other two- or three-dimensional isoparametric finite elements.     

Autonomous decentralized finite element method and its applications

In this paper, a new solution procedure using the finite element technique in order to solve problems of structure analysis is proposed. This procedure is called the autonomous decentralized finite element method because it is based on the characteristic autonomy and decentralization in life or biological systems (life‐like approach). The fundamental approach is developed according to an idea of cellular automata manipulation by the new neighbourhood model. The finite element method with an algorithm of the relaxation method is adopted as the solution procedure in this approach. The proposed procedure demonstrates that it is a powerful means of numerical analysis for many kinds of structural problems that are structural morphogenesis, structural optimization and structural inverse problems. Our procedure is applied to numerical analysis of three simple plane models: (1) The structural shape analysis problem for the prescribed displacement mode of a truss structure, (2) An adaptive structure remodelling problem on an elastic continuum, (3) An identification problem of thermal conductivity on a continuum. The effectiveness and validity of our idea are shown from their numerical results. Copyright © 2003 John Wiley & Sons, Ltd.     

Efficient simulation of multi‐body contact problems on complex geometries: A flexible decomposition approach using constrained minimization

We consider the numerical simulation of non‐linear multi‐body contact problems in elasticity on complex three‐dimensional geometries. In the case of warped contact boundaries and non‐matching finite element meshes, particular emphasis has to be put on the discretization of the transmission of forces and the non‐penetration conditions at the contact interface. We enforce the discrete contact constraints by means of a non‐conforming domain decomposition method, which allows for optimal error estimates. Here, we develop an efficient method to assemble the discrete coupling operator by computing the triangulated intersection of opposite element faces in a locally adjusted projection plane but carrying out the required quadrature on the faces directly. Our new element‐based algorithm does not use any boundary parameterizations and is also suitable for isoparametric elements. The emerging non‐linear system is solved by a monotone multigrid method of optimal complexity. Several numerical examples in 3D illustrate the effectiveness of our approach. Copyright © 2008 John Wiley & Sons, Ltd.     

On the application of higher‐order elements in the hierarchical interface‐enriched finite element method

This article introduces a new algorithm for evaluating enrichment functions in the higher‐order hierarchical interface‐enriched finite element method (HIFEM), which enables the fully mesh‐independent simulation of multiphase problems with intricate morphologies. The proposed hierarchical enrichment technique can accurately capture gradient discontinuities along materials interfaces that are in close proximity, in contact, and even intersecting with one another using nonconforming finite element meshes for discretizing the problem. We study different approaches for creating higher‐order HIFEM enrichments corresponding to six‐node triangular elements and analyze the advantages and shortcomings of each approach. The preferred method, which yields the lowest computational cost and highest accuracy, relies on a special mapping between the local and global coordinate systems for evaluating enrichment functions. A comprehensive convergence study is presented to show that this method yields similar convergence rate and precision as those of the standard FEM with conforming meshes. Finally, we demonstrate the application of the higher‐order HIFEM for simulating the thermal and deformation responses of several materials systems and engineering problems with complex geometries. Copyright © 2015 John Wiley & Sons, Ltd.     

Isoparametric Hermite elements

Isoparametric Hermite elements are created using Bogner–Fox–Schmit rectangles on a reference domain and mapping these numerically onto the computational domain. The difficulties involved in devising explicit C¹ shape functions for isoparametric elements are thus avoided, and the resulting elements have all the benefits of full C¹ continuity, the simplicity of the Bogner–Fox–Schmit element and the geometrical flexibility expected from higher-order isoparametric elements. The numerical mapping consists in the finite element solution of a linear boundary value problem, which is inexpensive and is carried out as a preprocessing operation—the required derivatives of the mapping then being supplied to the main analysis as data. Some care is required in defining the differential boundary conditions, and guidance on this is provided. Examples are given showing the success of the mapping procedure, and the use of the resulting elements in the solution of some boundary value problems. The numerical results confirm a convergence analysis provided for the new isoparametric Hermite element.     

Mesh grading technique using modified isoparametric shape functions and its application to wave propagation problems

Mesh grading of finite element meshes is greatly simplified by allowing two or more finer elements to abut the entire straight or curved edge of a neighbouring coarser element. This paper proposes the technique by which it can be achieved while maintaining inter-element compatibility by introducing modified shape functions. The concepts and potential advantages of this technique are described in detail for two-dimensional isoparametric quadrilateral elements, although the same procedure can also be applied to other element types including three-dimensional. Implementation of this technique to existing finite element programs requires only minimal modifications. Finally, numerical examples are presented to illustrate the application of the mesh grading technique to several wave propagation problems.     

A 2-D five-noded finite element to model power singularity

A 2-D five-noded finite element which contains a singularity is developed. The new element is compatible with cubic standard isoparametric elements. The main advantage of using cubic isoparametric elements over quadratic elements is to reduce the number of elements required to model a structure for results of comparable accuracy. The element is tested on two different examples. In the first example, an edge crack problem is analyzed using two different meshes. The second example is a crack perpendicular to the interface problem which is solved for two different specific composites. The results obtained using the proposed element are compared with those obtained using other existing elements in the literature. Those comparisons demonstrate the superiority of the present technique in using less number of elements and nodes to produce accurate results.     

Explicit expressions for energy release rates using virtual crack extensions

A new finite element technique for calculating energy release rates is presented. An explicit expression for energy changes due to virtual crack extensions is formulated based on a variation of isoparametric element mappings. Energy release rates are calculated directly from integral expressions evaluated over singular quarter-point isoparametric elements surrounding the crack tip. Since the energy release rates are expressed in variational form, there is no need for the analyst to select a small finite crack extension to simulate a virtual crack extension. The method is shown to produce very accurate solutions even with fairly coarse element meshes. A similar technique for mixed-mode fracture based on mutual potential energy release rates is described.     

A new stabilized finite element method for reaction–diffusion problems: The source‐stabilized Petrov–Galerkin method

This paper proposes a new stabilized finite element method to solve singular diffusion problems described by the modified Helmholtz operator. The Galerkin method is known to produce spurious oscillations for low diffusion and various alternatives were proposed to improve the accuracy of the solution. The mostly used methods are the well‐known Galerkin least squares and Galerkin gradient least squares (GGLS). The GGLS method yields the exact nodal solution in the one‐dimensional case and for a uniform mesh. However, the behavior of the method deteriorates slightly in the multi‐dimensional case and for non‐uniform meshes. In this work we propose a new stabilized finite element method that leads to improved accuracy for multi‐dimensional problems. For the one‐dimensional case, the new method leads to the same results as the GGLS method and hence provides exact nodal solutions to the problem on uniform meshes. The proposed method is a Galerkin discretization used to solve a modified equation that includes a term depending on the gradient of the original partial differential equation. Copyright © 2008 John Wiley & Sons, Ltd.     

The synthesis of near-optimum finite element meshes with interactive computer graphics

A new approach to the generation of near-optimum finite element meshes is presented. Like other current methods, the procedure presented uses the results of a previous analysis to improve the idealization, but unlike other procedures a new element mesh is generated in each cycle with the aid of interactive computer graphics. The procedure generates near-optimum two-dimensional meshes on one cycle employing a grid optimization criterion based on variations in the strain energy density and using a software system which operates like an interactive finite element preprocessor. The example problems presented demonstrate the efficiency and flexibility of the approach.     

Interface handling for three‐dimensional higher‐order XFEM‐computations in fluid–structure interaction

Three‐dimensional higher‐order eXtended finite element method (XFEM)‐computations still pose challenging computational geometry problems especially for moving interfaces. This paper provides a method for the localization of a higher‐order interface finite element (FE) mesh in an underlying three‐dimensional higher‐order FE mesh. Additionally, it demonstrates, how a subtetrahedralization of an intersected element can be obtained, which preserves the possibly curved interface and allows therefore exact numerical integration. The proposed interface algorithm collects initially a set of possibly intersecting elements by comparing their ‘eXtended axis‐aligned bounding boxes’. The intersection method is applied to a highly reduced number of intersection candidates. The resulting linearized interface is used as input for an elementwise constrained Delaunay tetrahedralization, which computes an appropriate subdivision for each intersected element. The curved interface is recovered from the linearized interface in the last step. The output comprises triangular integration cells representing the interface and tetrahedral integration cells for each intersected element. Application of the interface algorithm currently concentrates on fluid–structure interaction problems on low‐order and higher‐order FE meshes, which may be composed of any arbitrary element types such as hexahedra, tetrahedra, wedges, etc. Nevertheless, other XFEM‐problems with explicitly given interfaces or discontinuities may be tackled in addition. Multiple structures and interfaces per intersected element can be handled without any additional difficulties. Several parallelization strategies exist depending on the desired domain decomposition approach. Numerical test cases including various geometrical exceptions demonstrate the accuracy, robustness and efficiency of the interface handling. Copyright © 2009 John Wiley & Sons, Ltd.