Automatic element reordering for finite element analysis with frontal solution schemes

This paper describes an element reordering algorithm which is suitable for use with a frontal solution package. The procedure is shown to generate efficient element numberings for a wide variety of test examples. In an effort to obtain an optimum elimination order, the algorithm first renumbers the nodes, and then uses this result to resequence the elements. This intermediate step is necessary because of the nature of the frontal solution procedure, which assembles variables on an element-by-element basis but eliminates them node by node. To renumber the nodes, a modified version of the King¹ algorithm is used. In order to minimize the number of nodal numbering schemes that need to be considered, the starting nodes are selected automatically by using some concepts from graph theory. Once the optimum numbering sequence has been ascertained, the elements are then reordered in an ascending sequence of their lowest-numbered nodes. This ensures that the new elimination order is preserved as closely as possible. For meshes that are composed of a single type of high-order element, it is only necessary to consider the vertex nodes in the renumbering process. This follows from the fact that mesh numberings which are optimal for low-order elements are also optimal for high-order elements. Significant economies in the reordering strategy may thus be achieved. A computer implementation of the algorithm, written in FORTRAN IV, is given.     

A unified set of resequencing algorithms

A general algorithm for resequencing equations and finite element meshes is presented. This algorithm incorporates, in a unified form, the most successful resequencing schemes, namely: the Sloan, Gibbs–King (GK) and Gibbs–Poole–Stockmeyer (GPS) algorithms. As well it provides a context within which the development of new algorithms may take place with a minimum of change. It is easily programmed and has been shown to speed up the execution of the original GK algorithm.     

A comparasion of three resequencing algorithms for the reduction of matrix profile and wavefront

Three widely-used nodal resequencing algorithms were tested and compared for their ability to reduce matrix profile and root-mean-square (rms) wavefront, the latter being the most critical parameter in determining matrix decomposition time in the NASTRAN finite element computer program. The three algorithms are Cuthill–McKee (CM), Gibbs–Poole–Stockmeyer (GPS), and Levy. Results are presented for a diversified collection of 30 test problems ranging in size from 59 to 2680 nodes. It is concluded that GPS is exceptionally fast, and, for the conditions under which the test was made, the algorithm best able to reduce profile and rms wavefront consistently well. An extensive bibliography of resequencing algorithms is included.     

COMBINATION OF ADAPTIVITY AND MESH SMOOTHING FOR THE FINITE ELEMENT ANALYSIS OF SHELLS WITH INTERSECTIONS

A compatible hierarchical adaptive scheme is proposed which allows to control both density and geometrical properties of meshes with four-node linear finite shell elements. The algorithm produces a sequence of meshes with two aims, nearly equal distribution of the local error in each element and a mesh with regular elements, thus internal element angles near 90° and length ratios of adjacent element sides near unity. This goal is achieved in an efficient manner imposing a combination of a local smoothing algorithm with the adaptive mesh generation. New created nodes are positioned on the real shell surface and shell boundaries which may be given e.g. by CAD data. Also the shell directors are determined from the normals on the real geometry. Shell intersections are detected automatically as common curves of two adjacent shell parts. As a shell continuum cannot be assumed for these intersections and thus simple standard adaptive schemes fail, shell intersections have to be treated in a way similar to shell boundaries. For some numerical examples the developed algorithms are demonstrated and the resulting meshes are shown. © 1997 by John Wiley & Sons, Ltd.     

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.     

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.     

A distortion measure to validate and generate curved high‐order meshes on CAD surfaces with independence of parameterization

A framework to validate and generate curved nodal high‐order meshes on Computer‐Aided Design (CAD) surfaces is presented. The proposed framework is of major interest to generate meshes suitable for thin‐shell and 3D finite element analysis with unstructured high‐order methods. First, we define a distortion (quality) measure for high‐order meshes on parameterized surfaces that we prove to be independent of the surface parameterization. Second, we derive a smoothing and untangling procedure based on the minimization of a regularization of the proposed distortion measure. The minimization is performed in terms of the parametric coordinates of the nodes to enforce that the nodes slide on the surfaces. Moreover, the proposed algorithm repairs invalid curved meshes (untangling), deals with arbitrary polynomial degrees (high‐order), and handles with low‐quality CAD parameterizations (independence of parameterization). Third, we use the optimization procedure to generate curved nodal high‐order surface meshes by means of an a posteriori approach. Given a linear mesh, we increase the polynomial degree of the elements, curve them to match the geometry, and optimize the location of the nodes to ensure mesh validity. Finally, we present several examples to demonstrate the features of the optimization procedure, and to illustrate the surface mesh generation process. Copyright © 2015 John Wiley & Sons, Ltd.     

Fully automatic two dimensional mesh generation using normal offsetting

A technique, based on a normal offsetting procedure, for the fully automatic generation of two dimensional meshes suitable for finite element analysis is presented. The method positions nodes by first meshing the geometric entities that compose the object boundary, then offsetting those nodal locations along vectors normal to the boundary geometry. The offset row of nodes is processed to ensure a good nodal spacing appropriate for generating well shaped elements. Following processing, the new row is offset again and the cycle is repeated until the entire area is filled with nodes. The boundary based technique ensures good quality element shapes for analysis in critical boundary regions and facilitates applications involving integration of mesh generation with design geometry databases. Nodal locations are calculated based on local parameters avoiding the higher order time complexities associated with global calculations. A technique for controlling mesh density by overlaying an independent mesh density function on the geometry is also presented as part of the method. This approach allows mesh density to be automatically controlled by a variety of factors, such as previous analysis results, that are external to the actual mesh generation process. The independent nature of the function method allows different sources of density information to be used interchangeably without modification to the mesh generation procedure.     

基于基面力概念的余能原理任意网格有限元方法

利用基面力概念,给出一种任意形状网格都可以使用的柔度矩阵表达式的具体形式,运用拉格朗日乘子法得到以基面力为基本未知量的余能原理有限元支配方程,提出计算节点位移的表达式,编制出相应的任意网格有限元计算程序。该文对不同形状的单元网格以及畸变网格进行了计算分析,并与理论解和传统的有限元进行了对比和讨论。结果表明:该方法可以适用于任意形状的有限元网格,对网格的畸变不敏感。     

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.     

Node and element resequencing using the Laplacian of a finite element graph: Part I—General concepts and algorithm

A Finite Element Graph (FEG) is defined here as a nodal graph (G), a dual graph (G*), or a communication graph (G˙) associated with a generic finite element mesh. The Laplacian matrix ( L (G), L (G*) or L (G˙)), used for the study of spectral properties of an FEG, is constructed from usual vertex and edge connectivities of a graph. An automatic algorithm, based on spectral properties of an FEG (G, G* or G˙), is proposed to reorder the nodes and/or elements of the associated finite element mesh. The new algorithm is called Spectral PEG Resequencing (SFR). This algorithm uses global information in the graph, it does not depend on a pseudoperipheral vertex in the resequencing process, and it does not use any kind of level structure of the graph. Moreover, the SFR algorithm is of special advantage in computing environments with vector and parallel processing capabilities. Nodes or elements in the mesh can be reordered depending on the use of an adequate graph representation associated with the mesh. If G is used, then the nodes in the mesh are properly reordered for achieving profile and wavefront reduction of the finite element stiffness matrix. If either G* or G˙ is used, then the elements in the mesh are suitably reordered for a finite element frontai solver, A unified approach involving FEGs and finite element concepts is presented. Conclusions are inferred and possible extensions of this research are pointed out. In Part II of this work,¹ the computational implementation of the SFR algorithm is described and several numerical examples are presented. The examples emphasize important theoretical, numerical and practical aspects of the new resequencing method.     

A hierarchical approach to automatic finite element mesh generation

A point-based two-stage hierarchical method for automatic finite element mesh generation from a solid model is presented. Given the solid model of a component and the required nodal density distribution, nodes are generated according to the hierarchy—vertex, edge, face and solid. At the vertices, nodes are established naturally. Nodes on the edges, faces and inside the solid model are generated by recursive subdivision. The nodes are then connected to form a valid and well-conditioned finite element mesh of tetrahedron elements using modified Delaunay Triangulation. Checks are conducted to ensure the compatibility of geometry and topology between the solid model and the mesh.     

Optimization of a regularized distortion measure to generate curved high‐order unstructured tetrahedral meshes

We present a robust method for generating high‐order nodal tetrahedral curved meshes. The approach consists of modifying an initial linear mesh by first, introducing high‐order nodes, second, displacing the boundary nodes to ensure that they are on the computer‐aided design surface, and third, smoothing and untangling the mesh obtained after the displacement of the boundary nodes to produce a valid curved high‐order mesh. The smoothing algorithm is based on the optimization of a regularized measure of the mesh distortion relative to the original linear mesh. This means that whenever possible, the resulting mesh preserves the geometrical features of the initial linear mesh such as shape, stretching, and size. We present several examples to illustrate the performance of the proposed algorithm. Furthermore, the examples show that the implementation of the optimization problem is robust and capable of handling situations in which the mesh before optimization contains a large number of invalid elements. We consider cases with polynomial approximations up to degree ten, large deformations of the curved boundaries, concave boundaries, and highly stretched boundary layer elements. The meshes obtained are suitable for high‐order finite element analyses. Copyright © 2015 John Wiley & Sons, Ltd.     

Mapping Cohesive Fracture and Fragmentation Simulations to Graphics Processor Units

A graphics processor units(GPU)‐based computational framework is presented to deal with dynamic failure events simulated by means of cohesive zone elements. The work is divided into two parts. In the first part, we deal with pre‐processing of the information and verify the effectiveness of dynamic insertion of cohesive elements in large meshes in parallel. To this effect, we employ a novel and simplified topological data structure specialized for meshes with triangles, designed to run efficiently and minimize memory occupancy on the GPU. In the second part, we present a parallel explicit dynamics code that implements an extrinsic cohesive zone formulation where the elements are inserted ‘on‐the‐fly’, when needed and where needed. The main challenge for implementing a GPU‐based computational framework using an extrinsic cohesive zone formulation resides on being able to dynamically adapt the mesh, in a consistent way, by inserting cohesive elements on fractured facets. In order to handle that, we extend the conventional data structure used in the finite element method (based on element incidence) and store, for each element, references to the adjacent elements. This additional information suffices to consistently insert cohesive elements by duplicating nodes when needed. Currently, our data structure is specialized for triangular meshes, but an extension to tetrahedral meshes is feasible. The data structure is effective when used in conjunction with algorithms to traverse nodes and elements. Results from parallel simulations show an increase in performance when adopting strategies such as distributing different jobs among threads for the same element and launching many threads per element. To avoid concurrency on accessing shared entities, we employ graph coloring. In a pre‐processing phase, each node of the dual graph (bulk elements of the mesh as graph nodes) is assigned a color different from the colors assigned to adjacent nodes. In that fashion, elements of the same color can be processed in parallel without concurrency. All the procedures needed for the insertion of cohesive elements along fracture facets and for computing nodal properties are performed by threads assigned to triangles, invoking one kernel per color. Computations on existing cohesive elements are also performed based on adjacent bulk elements. Experiments show that GPU speedup increases with the number of nodes and bulk elements. Copyright © 2015 John Wiley & Sons, Ltd.     

Automatic metric 3D surface mesh generation using subdivision surface geometrical model. Part 2: Mesh generation algorithm and examples

In this paper, a new metric advancing front surface mesh generation scheme is suggested. This new surface mesh generator is based on a new geometrical model employing the interpolating subdivision surface concept. The target surfaces to be meshed are represented implicitly by interpolating subdivision surfaces which allow the presence of various sharp and discontinuous features in the underlying geometrical model. While the main generation steps of the new generator are based on a robust metric surface triangulation kernel developed previously, a number of specially designed algorithms are developed in order to combine the existing metric advancing front algorithm with the new geometrical model. As a result, the application areas of the new mesh generator are largely extended and can be used to handle problems involving extensive changes in domain geometry. Numerical experience indicates that, by using the proposed mesh generation scheme, high quality surface meshes with rapid varying element size and anisotropic characteristics can be generated in a short time by using a low‐end PC. Finally, by using the pseudo‐curvature element‐size controlling metric to impose the curvature element‐size requirement in an implicit manner, the new mesh generation procedure can also generate finite element meshes with high fidelity to approximate the target surfaces accurately. Copyright © 2003 John Wiley & Sons, Ltd.     

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.     

Automatic local refinement for irregular rectangular meshes

The use of local mesh refinements for the generation of meshes for the finite element or finite difference methods is studied. A class of rectangular meshes which admit restricted local refinements, referred to as irregular rectangular meshes, is introduced and its representation discussed. Properties of algorithms for mesh refinements are discussed from the viewpoints of termination with a mesh in the specified class, memory utilization, symmetry and fragmentation of the mesh.     

An approach to refining three-dimensional tetrahedral meshes based on Delaunay transformations

A technique for refining three-dimensional tetrahedral meshes is proposed in this paper. The proposed technique is capable of treating arbitrary unstructured tetrahedral meshes, convex or non-convex with multiple regions resulting in high quality constrained Delaunay triangulations. The tetrahedra generated are of high quality (nearly equilateral). Sliver tetrahedra, which present a real problem to many algorithms are not produced with the new method. The key to the generation of high quality tetrahedra is the iterative application of a set of topological transformations based on the Voronoi–Delaunay theory and a reposition of nodes technique. The computational requirements of the proposed technique are in linear relationship with the number of nodes and tetrahedra, making it ideal for direct employment in a fully automatic finite element analysis system for 3-D adaptive mesh refinement. Application to some test problems is presented to show the effectiveness and applicability of the new method.