Performance comparison of data‐reordering algorithms for sparse matrix–vector multiplication in edge‐based unstructured grid computations

Several performance improvements for finite‐element edge‐based sparse matrix–vector multiplication algorithms on unstructured grids are presented and tested. Edge data structures for tetrahedral meshes and triangular interface elements are treated, focusing on nodal and edges renumbering strategies for improving processor and memory hierarchy use. Benchmark computations on Intel Itanium 2 and Pentium IV processors are performed. The results show performance improvements in CPU time ranging from 2 to 3. Copyright © 2005 John Wiley & Sons, Ltd.     

Overlapping Schwarz preconditioners for spectral element discretizations of convection‐diffusion problems

The classical overlapping Schwarz algorithm is here extended to stabilized spectral element discretizations of convection‐diffusion problems. The algorithm solves iteratively the resulting non‐symmetric system of linear equations by a preconditioned GMRES method. The preconditioner is built from local convection‐diffusion solvers on overlapping subdomains and from a coarse convection‐diffusion solver on a coarse mesh defined by the subdomain boundaries. Several numerical experiments on test problems in the plane indicate that this algorithm retains the fast convergence rate and optimal scalability properties of classical overlapping methods for diffusion dominated problems. Fast convergence is also obtained for convection dominated problems without closed streamlines and with a moderate number of subdomains. Copyright © 2001 John Wiley & Sons, Ltd.     

Some useful strategies for unstructured edge‐based solvers on shared memory machines

Three strategies for shared memory parallel edge‐based solvers are proposed which guarantee that nodes belonging to one thread are not accessed by other threads for vertex‐centered discretizations (replace nodes by cells in case of cell‐centered discretizations). The algorithms reorder the edges in groups in order for the parallelization to take place at the edge level, possibly through multiple passes, which constitutes the bulk of the work in an edge‐based solver. These strategies are presented in an increasing order of programming effort and their performances are also compared. Various renumbering algorithms are considered. Results and timings are given for a classical Computational Fluid Dynamics compressible edge‐based solver and a Numerical Weather Prediction compressible dynamic solver for dry air, as well as computational details to illustrate the efficiency of the proposed approach. The influence of the point renumbering on the final edge grouping and efficiency is also studied through numerical results. Copyright © 2010 John Wiley & Sons, Ltd.     

Polyhedral elements by means of node/edge‐based smoothed finite element method

The node‐based or edge‐based smoothed finite element method is extended to develop polyhedral elements that are allowed to have an arbitrary number of nodes or faces, and so retain a good geometric adaptability. The strain smoothing technique and implicit shape functions based on the linear point interpolation make the element formulation simple and straightforward. The resulting polyhedral elements are free from the excessive zero‐energy modes and yield a robust solution very much insensitive to mesh distortion. Several numerical examples within the framework of linear elasticity demonstrate the accuracy and convergence behavior. The smoothed finite element method‐based polyhedral elements in general yield solutions of better accuracy and faster convergence rate than those of the conventional finite element methods. Copyright © 2016 John Wiley & Sons, Ltd.     

F‐bar aided edge‐based smoothed finite element method using tetrahedral elements for finite deformation analysisof nearly incompressible solids

A new smoothed finite element method (S‐FEM) with tetrahedral elements for finite strain analysis of nearly incompressible solids is proposed. The proposed method is basically a combination of the F‐bar method and edge‐based S‐FEM with tetrahedral elements (ES‐FEM‐T4) and is named ‘F‐barES‐FEM‐T4’. F‐barES‐FEM‐T4 inherits the accuracy and shear locking‐free property of ES‐FEM‐T4. At the same time, it also inherits the volumetric locking‐free property of the F‐bar method. The isovolumetric part of the deformation gradient ( F ^iso) is derived from the F of ES‐FEM‐T4, whereas the volumetric part ( F ^vol) is derived from the cyclic smoothing of J(=det( F )) between elements and nodes. Some demonstration analyses confirm that F‐barES‐FEM‐T4 with a sufficient number of cyclic smoothings suppresses the pressure oscillation in nearly incompressible materials successfully with no increase in DOF. Moreover, they reveal that our method is capable of relaxing the corner locking issue arising at the corner in the cylinder barreling analysis. Copyright © 2016 John Wiley & Sons, Ltd.     

Dispersion error reduction for acoustic problems using the edge‐based smoothed finite element method (ES‐FEM)

The paper reports a detailed analysis on the numerical dispersion error in solving 2D acoustic problems governed by the Helmholtz equation using the edge‐based smoothed finite element method (ES‐FEM), in comparison with the standard FEM. It is found that the dispersion error of the standard FEM for solving acoustic problems is essentially caused by the ‘overly stiff’ feature of the discrete model. In such an ‘overly stiff’ FEM model, the wave propagates with an artificially higher ‘numerical’ speed, and hence the numerical wave‐number becomes significantly smaller than the actual exact one. Owing to the proper softening effects provided naturally by the edge‐based gradient smoothing operations, the ES‐FEM model, however, behaves much softer than the standard FEM model, leading to the so‐called very ‘close‐to‐exact’ stiffness. Therefore the ES‐FEM can naturally and effectively reduce the dispersion error in the numerical solution in solving acoustic problems. Results of both theoretical and numerical studies will support these important findings. It is shown clearly that the ES‐FEM suits ideally well for solving acoustic problems governed by the Helmholtz equations, because of the crucial effectiveness in reducing the dispersion error in the discrete numerical model. Copyright © 2010 John Wiley & Sons, Ltd.     

Simulations of flow through fluid/porous layers by a characteristic‐based method on unstructured grids

An upwind characteristic‐based finite volume method on unstructured grids is employed for numerical simulation of incompressible laminar flow and forced convection heat transfer in 2D channels containing simultaneously fluid layers and fluid‐saturated porous layers. Hydrodynamic and heat transfer results are reported for two configurations: the first one is a backward‐facing step channel with a porous block inserted behind the step, and the second one is a partially porous channel with discrete heat sources on the bottom wall. The effects of Darcy numbers on heat transfer augmentation and pressure loss were investigated for low Reynolds laminar flows. The results demonstrate the accuracy and robustness of the numerical scheme proposed, and suggest that partially porous insertion in a channel can significantly improve heat transfer performance with affordable pressure loss. Copyright © 2001 John Wiley & Sons, Ltd.     

Insight into the flow‐condition‐based interpolation finite element approach: solution of steady‐state advection–diffusion problems

The flow‐condition‐based interpolation (FCBI) finite element approach is studied in the solution of advection–diffusion problems. Two FCBI procedures are developed and tested with the original FCBI method: in the first scheme, a general solution of the advection–diffusion equation is embedded into the interpolation, and in the second scheme, the link‐cutting bubbles approach is used in the interpolation. In both procedures, as in the original FCBI method, no artificial parameters are included to reach stability for high Péclet number flows. The procedures have been implemented for two‐dimensional analysis and the results of some test problems are presented. These results indicate good stability and accuracy characteristics and the potential of the FCBI solution approach. Copyright © 2005 John Wiley & Sons, Ltd.     

Edge‐based finite element techniques for non‐linear solid mechanics problems

Edge‐based data structures are used to improve computational efficiency of inexact Newton methods for solving finite element non‐linear solid mechanics problems on unstructured meshes. Edge‐based data structures are employed to store the stiffness matrix coefficients and to compute sparse matrix–vector products needed in the inner iterative driver of the inexact Newton method. Numerical experiments on three‐dimensional plasticity problems have shown that memory and computer time are reduced, respectively, by factors of 4 and 6, compared with solutions using element‐by‐element storage and matrix–vector products. Copyright © 2001 John Wiley & Sons, Ltd.     

Assembly of finite element methods on graphics processors

Recently, graphics processing units (GPUs) have had great success in accelerating many numerical computations. We present their application to computations on unstructured meshes such as those in finite element methods. Multiple approaches in assembling and solving sparse linear systems with NVIDIA GPUs and the Compute Unified Device Architecture (CUDA) are created and analyzed. Multiple strategies for efficient use of global, shared, and local memory, methods to achieve memory coalescing, and optimal choice of parameters are introduced. We find that with appropriate preprocessing and arrangement of support data, the GPU coprocessor using single‐precision arithmetic achieves speedups of 30 or more in comparison to a well optimized double‐precision single core implementation. We also find that the optimal assembly strategy depends on the order of polynomials used in the finite element discretization. Copyright © 2010 John Wiley & Sons, Ltd.     

High‐order finite volume schemes on unstructured grids using moving least‐squares reconstruction. Application to shallow water dynamics

This paper introduces the use of moving least‐squares (MLS) approximations for the development of high‐order finite volume discretizations on unstructured grids. The field variables and their successive derivatives can be accurately reconstructed using this mesh‐free technique in a general nodal arrangement. The methodology proposed is used in the construction of two numerical schemes for the shallow water equations on unstructured grids: a centred Lax–Wendroff method with added shock‐capturing dissipation, and a Godunov‐type upwind scheme, with linear and quadratic reconstructions. This class of mesh‐free techniques provides a robust and general approximation framework which represents an interesting alternative to the existing procedures, allowing, in addition, an accurate computation of the viscous fluxes. Copyright © 2005 John Wiley & Sons, Ltd.     

Algebraic multigrid for finite element elasticity equations: Determination of nodal dependence via edge‐matrices and two‐level convergence

We study an algebraic multigrid (AMG) method for solving elliptic finite element equations of linear elasticity problems. In this method, which has been proposed in (Kraus, SIAM J Sci Comput 2008; 30 : 505–524), the coarsening is based on the so‐called edge‐matrices, which allows to generalize the concept of strong and weak connections, as used in the classical AMG, to ‘algebraic vertices’ that accumulate the nodal degrees of freedom in case of vector‐field problems. The major contribution of this work is related to the investigation of a measure for the nodal dependence and on the generation of the edge‐matrices, which are the basic building blocks of this method. A natural measure is the cosine of the abstract angle between the two subspaces spanned by the basis functions corresponding to the respective algebraic vertices. Another original contribution of this work is a two‐level convergence analysis of the method. The presented numerical results cover also problems with jumps in Young's modulus of elasticity and orthotropic materials. Copyright © 2010 John Wiley & Sons, Ltd.     

Bubble‐enhanced smoothed finite element formulation: a variational multi‐scale approach for volume‐constrained problems in two‐dimensional linear elasticity

This paper presents a bubble‐enhanced smoothed finite element formulation for the analysis of volume‐constrained problems in two‐dimensional linear elasticity. The new formulation is derived based on the variational multi‐scale approach in which unequal order displacement‐pressure pairs are used for the mixed finite element approximation and hierarchical bubble function is selected for the fine‐scale displacement approximation. An area‐weighted averaging scheme is employed for the two‐scale smoothed strain calculation under the framework of edge‐based smoothed FEM. The smoothed fine‐scale solution is shown to naturally contain the stress field jump of the smoothed coarse‐scale solution across the boundary of edge‐based smoothing domain and thus provides the possibility to stabilize the global solution for volume‐constrained problems. A global monolithic solution strategy is employed, and the fine‐scale solution is solved without the consideration of approximating the strong form of the fine‐scale equation. Several numerical examples are analyzed to demonstrate the accuracy of the present formulation. Copyright © 2014 John Wiley & Sons, Ltd.     

A residual‐based finite element method for the Helmholtz equation

A new residual‐based finite element method for the scalar Helmholtz equation is developed. This method is obtained from the Galerkin approximation by appending terms that are proportional to residuals on element interiors and inter‐element boundaries. The inclusion of residuals on inter‐element boundaries distinguishes this method from the well‐known Galerkin least‐squares method and is crucial to the resulting accuracy of this method. In two dimensions and for regular bilinear quadrilateral finite elements, it is shown via a dispersion analysis that this method has minimal phase error. Numerical experiments are conducted to verify this claim as well as test and compare the performance of this method on unstructured meshes with other methods. It is found that even for unstructured meshes this method retains a high level of accuracy. Copyright © 2000 John Wiley & Sons, Ltd.     

Mechanically based models: Adaptive refinement for B‐spline finite element

This article presents two new methods for adaptive refinement of a B‐spline finite element solution within an integrated mechanically based computer aided engineering system. The proposed techniques for adaptively refining a B‐spline finite element solution are a local variant of np‐refinement and a local variant of h‐refinement. The key component in the np‐refinement is the linear co‐ordinate transformation introduced into the refined element. The transformation is constructed in such a way that the transformed nodal configuration of the refined element is identical to the nodal configuration of the neighbour elements. Therefore, the assembly proceeds as with classic finite elements, while the solution approximation conforms exactly along the inter‐element boundaries. For the h‐refinement, this transformation is introduced into a construction that merges the super element from the finite element world with the hierarchical B‐spline representation from the computational geometry. In the scope of developing sculptured surfaces, the proposed approach supports C⁰ as well as the Hermite B‐spline C¹ continuous shapes. For sculptured solids, C⁰ continuity only is considered in this article. The feasibility of the proposed methods in the scope of the geometric design is demonstrated by several examples of creating sculptured surfaces and volumetric solids. Numerical performance of the methods is demonstrated for a test case of the two‐dimensional Poisson equation. Copyright © 2003 John Wiley & Sons, Ltd.     

Analysis of two‐grid methods for reaction‐diffusion equations by expanded mixed finite element methods

We present two efficient methods of two‐grid scheme for the approximation of two‐dimensional semi‐linear reaction‐diffusion equations using an expanded mixed finite element method. To linearize the discretized equations, we use two Newton iterations on the fine grid in our methods. Firstly, we solve an original non‐linear problem on the coarse grid. Then we use twice Newton iterations on the fine grid in our first method, and while in second method we make a correction on the coarse grid between two Newton iterations on the fine grid. These two‐grid ideas are from Xu's work (SIAM J. Sci. Comput. 1994; 15 :231–237; SIAM J. Numer. Anal. 1996; 33 :1759–1777) on standard finite element method. We extend the ideas to the mixed finite element method. Moreover, we obtain the error estimates for two algorithms of two‐grid method. It is showed that coarse space can be extremely coarse and we achieve asymptotically optimal approximation as long as the mesh sizes satisfy H =??(h^¼) in the first algorithm and H =??(h^?) in second algorithm. Copyright © 2006 John Wiley & Sons, Ltd.     

Improving multigrid performance for unstructured mesh drift–diffusion simulations on 147,000 cores

This study considers the scaling of three algebraic multigrid aggregation schemes for a finite element discretization of a drift–diffusion system, specifically the drift–diffusion model for semiconductor devices. The approach is more general and can be applied to other systems of partial differential equations. After discretization on unstructured meshes, a fully coupled multigrid preconditioned Newton–Krylov solution method is employed. The choice of aggregation scheme for generating coarser levels has a significant impact on the performance and scalability of the multigrid preconditioner. For the test cases considered, the uncoupled aggregation scheme, which aggregates/combines the immediate neighbors, followed by repartitioning and data redistribution for the coarser level matrices on a subset of the Message Passing Interface (MPI) processes, outperformed the two other approaches, including the baseline aggressive coarsening scheme. Scaling results are presented up to 147,456 cores on an IBM Blue Gene/P platform. A comparison of the scaling of a multigrid V‐cycle and W‐cycle is provided. Results for 65,536 cores demonstrate that a factor of 3.5 × reduction in time between the uncoupled aggregation and baseline aggressive coarsening scheme can be obtained by significantly reducing the iteration count due to the increased number of multigrid levels and the generation of better quality aggregates. Copyright © 2012 John Wiley & Sons, Ltd.     

Constraint‐corrected J–R curve based on three‐dimensional finite element analyses

Three‐dimensional (3D) finite element analyses are carried out on single‐edge bend [SE(B)] specimens for which the J‐integral resistance curves (J–R curves) have been experimentally determined to develop the constraint‐corrected J–R curves for the X80 grade pipe steel. The constraint parameters considered in this study include Q_HRR, Q_SSY, Q_{SSY_m}, Q_LM, Q_BM1, Q_BM2, A₂, h and T_z. The constraint‐corrected J–R curves were developed on the basis of the constraint parameters obtained from finite element analysis and experimentally determined J–R curves associated with deeply cracked and medium‐cracked SE(B) specimens and validated against shallow‐cracked SE(B) specimens. The analysis results indicate that all the constraint parameters considered in this study except Q_HRR, Q_SSY, Q_{SSY_m} and Q_LM lead to reasonably accurate constraint‐corrected J–R curves if the crack extensions are relatively small (≤0.7 mm). For larger crack extensions (≤1.5 mm), the Q_BM1‐based constraint‐corrected J–R curve leads to the most accurate predictions of J among all the constraint parameters considered.     

On the accuracy of finite volume and discontinuous Galerkin discretizations for compressible flow on unstructured grids

This paper presents a comparison between two high‐order methods. The first one is a high‐order finite volume (FV) discretization on unstructured grids that uses a meshfree method (moving least squares (MLS)) in order to construct a piecewise polynomial reconstruction and evaluate the viscous fluxes. The second method is a discontinuous Galerkin (DG) scheme. Numerical examples of inviscid and viscous flows are presented and the solutions are compared. The accuracy of both methods, for the same grid resolution, is similar, although the DG scheme requires a larger number of degrees of freedom than the FV–MLS method. Copyright © 2009 John Wiley & Sons, Ltd.