A class of parallel multiple‐front algorithms on subdomains

A class of parallel multiple‐front solution algorithms is developed for solving linear systems arising from discretization of boundary value problems and evolution problems. The basic substructuring approach and frontal algorithm on each subdomain are first modified to ensure stable factorization in situations where ill‐conditioning may occur due to differing material properties or the use of high degree finite elements (p methods). Next, the method is implemented on distributed‐memory multiprocessor systems with the final reduced (small) Schur complement problem solved on a single processor. A novel algorithm that implements a recursive partitioning approach on the subdomain interfaces is then developed. Both algorithms are implemented and compared in a least‐squares finite‐element scheme for viscous incompressible flow computation using h‐ and p‐finite element schemes. Copyright © 2003 John Wiley & Sons, Ltd.     

A frontal technique for vector computers

At the kernel of most scientific computations lies the solution of linear equations which, in finite element codes, is often performed by the frontal method. This method, like many algorithms for sparse matrices, is usually implemented with extensive use of indirect addressing which scarcely benefits from vectorization. As a consequence, present application codes only partially exploit the innovative features of supercomputer architectures. This paper describes a new version of the frontal technique which is designed for CRAY-like computers and is well suited to vector processing. Numerical tests have shown that the proposed algorithm is effective in improving the efficiency of finite element solutions on a vector machine.     

FEPACS: A computational tool for linear structural analysis

FEPACS (Finite Element Package for linear static, dynamic and instability Analysis of Composite Structures under hygro-thermo-mechanical loads) incorporates a complete library of consistent and correct 1-, 2- and 3-dimensional linear and quadratic general purpose finite elements. In this paper, we shall discuss the finite element technology that has gone into the package as well as its present modelling and solution capabilities. We shall also discuss briefly recent developments toward enhancing the package: Robust composite elements based on aC ⁰-continuous higher order transverse deformation plate/beam theory, and nonlinear element technology and solution strategies. Finally, we shall also briefly touch upon several satellite application modules that are in different stages of planning/development to aid FEPACS: damage assessment/prediction,expert-like advisors for solid modelling and finite element modelling/analysis, pre-/post-processing for FEPACS applications, structural optimisation and related finite element algorithms, and finally, a frontal solution module for FEPACS to enhance its feasibility for vectorisation/parallelisation.     

A three-step renumbering procedure for high-order finite element analysis

An efficient renumbering method for high-order finite element models is presented. The method can be used to reduce the profile and wavefront of a coefficient matrix arising in high-order finite element computation. The method indirectly performs node renumbering and involves three main steps. In the first step, nodes at corners of the elements are numbered using an existing renumbering algorithm. In the second step, elements are numbered in an ascending order of their least new corner node numbers. Finally, based on the new element numbers, both corner and non-corner nodes are renumbered using an algorithm that simulates the node elimination procedure in a frontal solution method. The method is compared to the algorithms that directly perform node renumbering. The numerical results indicate that the three-step algorithm presented here is an order of magnitude faster and the resulting renumbering produces excellent profile and wavefront characteristics of the coefficient matrix. © 1998 John Wiley & Sons, Ltd.     

Development and validation of a 3D computational tool to describe concrete behaviour at mesoscale. Application to the alkali-silica reaction

A finite element analysis of the large deformation of three-dimensional polycrystals is presented using pixel-based finite elements as well as finite elements conforming with grain boundaries. The macroscopic response is obtained through volume-averaging laws. A constitutive framework for elasto-viscoplastic response of single crystals is utilized along with a fully-implicit Lagrangian finite element algorithm for modeling microstructure evolution. The effect of grain size is included by considering a physically motivated measure of lattice incompatibility which provides an updated shearing resistance within grains. A domain decomposition approach is adopted for parallel computation to allow efficient large scale simulations. Conforming grids are adopted to simulate flexible and complex shapes of grains. The computed mechanical properties of polycrystals are shown to be consistent with experimental results for different grain sizes.     

A new sparse matrix vector multiplication graphics processing unit algorithm designed for finite element problems

Recently, graphics processing units (GPUs) have been increasingly leveraged in a variety of scientific computing applications. However, architectural differences between CPUs and GPUs necessitate the development of algorithms that take advantage of GPU hardware. As sparse matrix vector (SPMV) multiplication operations are commonly used in finite element analysis, a new SPMV algorithm and several variations are developed for unstructured finite element meshes on GPUs. The effective bandwidth of current GPU algorithms and the newly proposed algorithms are measured and analyzed for 15 sparse matrices of varying sizes and varying sparsity structures. The effects of optimization and differences between the new GPU algorithm and its variants are then subsequently studied. Lastly, both new and current SPMV GPU algorithms are utilized in the GPU CG solver in GPU finite element simulations of the heart. These results are then compared against parallel PETSc finite element implementation results. The effective bandwidth tests indicate that the new algorithms compare very favorably with current algorithms for a wide variety of sparse matrices and can yield very notable benefits. GPU finite element simulation results demonstrate the benefit of using GPUs for finite element analysis and also show that the proposed algorithms can yield speedup factors up to 12‐fold for real finite element applications. Copyright © 2015 John Wiley & Sons, Ltd.     

Algorithms for refining triangular grids suitable for adaptive and multigrid techniques

Two general algorithms for refining triangular computational meshes based on the bisection of triangles by the longest side are presented and discussed. The algorithms can be applied globally or locally for selective refinement of any conforming triangulation and always generate a new conforming triangulation after a finite number of interactions even when locally used. The algorithms also ensure that all angles in subsequent refined triangulations are greater than or equal to half the smallest angle in the original triangulation; the shape regularity of all triangles is maintained and the transition between small and large triangles is smooth in a natural way. Proofs of the above properties are presented. The second algorithm is a simpler, improved version of the first which retains most of the properties of the latter. The algorithms can be used either for constructing irregular computational meshes or for locally refining any given triangulation. In this sense they can be adequately combined with adaptive and/or multigrid techniques for solving finite element systems. Examples of the application of the algorithms are given and two possible generalizations are pointed out.     

A general methodology for structural shape optimization problems using automatic adaptive remeshing

The proposed methodology is based on the use of the adaptive mesh refinement (AMR ) techniques in the context of 2D shape optimization problems analysed by the finite element method. A suitable and very general technique for the parametrization of the optimization problem, using B-splines to define the boundary, is first presented. Then mesh generation, using the advancing frontal method, the error estimator and the mesh refinement criterion are studied in the context of shape optimization problems In particular, the analytical sensitivity analysis of the different items ruling the problem (B-splines. finite element mesh, structural behaviour and error estimator) is studied in detail. The sensitivities of the finite element mesh and error estimator permit their projection from one design to the next one leading to an a priori knowledge of the finite element error distribution on the new design without the necessity of any additional structural analysis. With this information the mesh refinement criterion permits one to build up a finite element mesh on the new design with a specified and controlled level of error. The robustness and reliability of the proposed methodology is checked by means of several examples.     

Obstacle identification using the TRAC algorithm with a second-order ABC

We consider obstacle identification using wave propagation. In such problems, one wants to find the location, shape, and size of an unknown obstacle from given measurements. We propose an algorithm for the identification task based on a time-reversed absorbing condition (TRAC) technique. Here, we apply the TRAC method to time-dependent linear acoustics, although our methodology can be applied to other wave-related problems as well, such as elastodynamics. There are two main contributions of our identification algorithm. The first contribution is the development of a robust and effective method for obstacle identification. While the original paper presented criteria for accepting or rejecting regions that enclose the obstacle, we use these criteria to develop an algorithm that automatically identifies the location of the obstacle. The second contribution is the utilization of an improved absorbing boundary condition (ABC) for the identification. We use the second-order Engquist-Majda ABC, and we implement it with a finite element scheme. To our knowledge, this is the first time that the second-order Engquist-Majda ABC is employed with the finite element method, as this boundary condition does not naturally fit in finite element schemes in its original form. Numerical experiments for the algorithms are presented.     

A parallel frontal solver for finite element applications

In finite element simulations, the overall computing time is dominated by the time needed to solve large sparse linear systems of equations. We report on the design and development of a parallel frontal code that can significantly reduce the wallclock time needed for the solution of these systems. The algorithm used is based on dividing the finite element domain into subdomains and applying the frontal method to each subdomain in parallel. The so‐called multiple front approach is shown to reduce the amount of work and memory required compared with the frontal method and, when run on a small number of processes, achieves good speedups. The code, HSL_MP42, has been developed for the Harwell Subroutine Library (http://www.numerical.rl.ac.uk/hsl). It is written in Fortran 90 and, by using MPI for message passing, achieves portability across a wide range of modern computer architectures. Copyright © 2001 John Wiley & Sons, Ltd.     

An isoparametric joint/interface element for finite element analysis

A generally applicable and simple joint/interface element for three- and two-dimensional finite element analysis is presented. The proposed element can model joints/interfaces between solid finite elements and shell finite elements. The derivation of the joint element stiffness is presented and algorithms for the treatment of nonlinear joint behaviour discussed. The performance of the element is tested on typical problems involving shell-to-shell and shell-to-solid interfaces.     

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.     

The use of dynamic data structures in finite element applications

The derivation of more efficient algorithms for finite element applications is not the primary goal of this article, but rather the efficient implementation of existing algorithms using dynamic data structures. In some cases the algorithms may be far from optimal, but serve to illustrate the advantages of dynamic data structures. In the first section, a tree data structure termed a PATRICIA tree is described and is shown to be suitable for storing data associated with finite element meshes. The manner in which the tree is constructed guarantees to provide rapid data retrieval times, competitive with those associated with static array data structures, whilst providing the added advantages of a dynamic data structure. The second section introduces a list of lists (LOL) data structure which is used to produce an efficient implementation of an example of a bandwidth reduction algorithm. Furthermore, the LOL data structure is also shown to be appropriate for implementing a novel method for extracting the domain boundary, with its orientation, from a given finite element connectivity matrix.     

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.     

MATRIX PROFILE AND WAVEFRONT REDUCTION BASED ON THE GRAPH THEORY AND WAVEFRONT MINIMIZATION

An effective hybrid renumbering method for reducing the profile and wavefront of a sparse matrix is presented. The method is an innovative combination of the classical graph theory approach and the wavefront minimization technique. A rooted level structure is generated first and the level of each node is determined. Then, for each element, the element level is defined as the minimal level of the nodes the element is connected to. Using element levels as weighting factors, the node and element numbering are then reassigned by minimizing wavefront on an element-by-element basis. The method can be used to generate node or element numbering for efficient implementation of finite element analyses using active column solvers or frontal solvers. It can also be applied to sparse matrices with a symmetric pattern of zeros. Because of the use of element levels, the entire structure of the matrix to be renumbered is taken into account during the local element-based wavefront minimization process. Therefore, the algorithm presented here combines the effectiveness of wavefront minimization schemes in local renumbering with the reliability of classical graph theory methods for global renumbering.     

Model updating based on an affine scaling interior optimization algorithm

Finite element model updating is usually considered as an optimization process. Affine scaling interior algorithms are powerful optimization algorithms that have been developed over the past few years. A new finite element model updating method based on an affine scaling interior algorithm and a minimization of modal residuals is proposed in this article, and a general finite element model updating program is developed based on the proposed method. The performance of the proposed method is studied through numerical simulation and experimental investigation using the developed program. The results of the numerical simulation verified the validity of the method. Subsequently, the natural frequencies obtained experimentally from a three-dimensional truss model were used to update a finite element model using the developed program. After updating, the natural frequencies of the truss and finite element model matched well.     

Parallel multigrid solvers for 3D unstructured finite element problems in large deformation elasticity and plasticity

Multigrid is a popular solution method for the set of linear algebraic equations that arise from PDEs discretized with the finite element method. The application of multigrid to unstructured grid problems, however, is not well developed. We discuss a method, that uses many of the same techniques as the finite element method itself, to apply standard multigrid algorithms to unstructured finite element problems. We use maximal independent sets (MISs) as a mechanism to automatically coarsen unstructured grids; the inherent flexibility in the selection of an MIS allows for the use of heuristics to improve their effectiveness for a multigrid solver. We present parallel algorithms, based on geometric heuristics, to optimize the quality of MISs and the meshes constructed from them, for use in multigrid solvers for 3D unstructured problems. We discuss parallel issues of our algorithms, multigrid solvers in general, and the parallel finite element application that we have developed to test our solver on challenging problems. We show that our solver, and parallel finite element architecture, does indeed scale well, with test problems in 3D large deformation elasticity and plasticity, with 40 million degree of freedom problem on 240 IBM four‐way SMP PowerPC nodes. Copyright © 2000 John Wiley & Sons, Ltd.     

Modelling convection in solidification processes using stabilized finite element techniques

Solidification of dendritic alloys is modelled using stabilized finite element techniques to study convection and macrosegregation driven by buoyancy and shrinkage. The adopted governing macroscopic conservation equations of momentum, energy and species transport are derived from their microscopic counterparts using the volume‐averaging method. A single domain model is considered with a fixed numerical grid and without boundary conditions applied explicitly on the freezing front. The mushy zone is modelled here as a porous medium with either an isotropic or an anisotropic permeability. The stabilized finite‐element scheme, previously developed by authors for modelling flows with phase change, is extended here to include effects of shrinkage, density changes and anisotropic permeability during solidification. The fluid flow scheme developed includes streamline‐upwind/Petrov–Galerkin (SUPG), pressure stabilizing/Petrov–Galerkin, Darcy stabilizing/Petrov–Galerkin and other stabilizing terms arising from changes in density in the mushy zone. For the energy and species equations a classical SUPG‐based finite element method is employed with minor modifications. The developed algorithms are first tested for a reference problem involving solidification of lead–tin alloy where the mushy zone is characterized by an isotropic permeability. Convergence studies are performed to validate the simulation results. Solidification of the same alloy in the absence of shrinkage is studied to observe differences in macrosegregation. Vertical solidification of a lead–tin alloy, where the mushy zone is characterized by an anisotropic permeability, is then simulated. The main aim here is to study convection and demonstrate formation of freckles and channels due to macrosegregation. The ability of stabilized finite element methods to model a wide variety of solidification problems with varying underlying phenomena in two and three dimensions is demonstrated through these examples. Copyright © 2005 John Wiley & Sons, Ltd.     

Challenges in Continuum Modelling of Intergranular Fracture

Abstract: Intergranular fracture in polycrystals is often simulated by finite elements coupled to a cohesive zone model for the interfaces, requiring cohesive laws for grain boundaries as a function of their geometry. We discuss three challenges in understanding intergranular fracture in polycrystals. First, 3D grain boundary geometries comprise a five‐dimensional space. Second, the energy and peak stress of grain boundaries have singularities for all commensurate grain boundaries, especially those with short repeat distances. Thirdly, fracture nucleation and growth depend not only upon the properties of grain boundaries, but also in crucial ways on edges, corners and triple junctions of even greater geometrical complexity. To address the first two challenges, we explore the physical underpinnings for creating functional forms to capture the hierarchical commensurability structure in the grain boundary properties. To address the last challenge, we demonstrate a method for atomistically extracting the fracture properties of geometrically complex local regions on the fly from within a finite element simulation.     

Knowledge-based methods and smart algorithms in computational mechanics

Effective methods leading to automated, computer-based solution of complex engineering design problems are studied in this paper. In particular, methods of automation of the finite element analyses are of primary interest here. These include algorithmic approaches, based on error estimation, adaptivity and smart algorithms, as well as heuristic approaches based on methods of knowledge engineering. A computational environment, which interactively couples h-p adaptive finite element methods with object-oriented programming and expert system tools, is presented. Several examples illustrate the merit and potential of the approaches studied here.