Non-Nested Multi-Level Solvers for Finite Element Discretisations of Mixed Problems

We consider a general framework for analysing the convergence of multi-grid solvers applied to finite element discretisations of mixed problems, both of conforming and nonconforming type. As a basic new feature, our approach allows to use different finite element discretisations on each level of the multi-grid hierarchy. Thus, in our multi-level approach, accurate higher order finite element discretisations can be combined with fast multi-level solvers based on lower order (nonconforming) finite element discretisations. This leads to the design of efficient multi-level solvers for higher order finite element discretisations. Received May 17, 2001; revised February 2, 2002 Published online April 25, 2002     

Localized tensor-based solvers for interactive finite element applications using C++ and Java

This paper presents techniques for solving systems of equations arising in finite element applications using a localized, tensor-based approach. The approach is localized in that a major part of the solution responsibility is delegated to vector degree-of-freedom objects, rather than residing solely in a global solver working on a monolithic data structure. The approach is tensor-based in that the fundamental quantities used for computation are considered to be second-order tensors. The localized data structure strategy provides the benefits of an efficient sparse and symmetric storage scheme without requiring complex implementation code. The tensor-based aspect of the approach can bring substantial performance benefits by increasing the granularity at which solution algorithms deal with their data. Java and C++ implementations of interactive finite element programs are used to demonstrate performance that is competitive with other available solvers, especially in the case of problems for which interactive analysis is feasible on commonly available hardware.     

Space–time <Emphasis Type="Italic">hp</Emphasis>-approximation of parabolic equations

A new space–time finite element method for the solution of parabolic partial differential equations is introduced. In a mesh and degree-dependent norm, it is first shown that the discrete bilinear form for the space–time problem is both coercive and continuous, yielding existence and uniqueness of the associated discrete solution. In a second step, error estimates in this mesh-dependent norm are derived. In particular, we show that combining low-order elements for the space variable together with an hp-approximation of the problem with respect to the temporal variable allows us to decrease the optimal convergence rates for the approximation of elliptic problems only by a logarithmic factor. For simultaneous space–time hp-discretization in both, the spatial as well as the temporal variable, overall exponential convergence in mesh-degree dependent norms on the space–time cylinder is proved, under analytic regularity assumptions on the solution with respect to the spatial variable. Numerical results for linear model problems confirming exponential convergence are presented.     

BDDC preconditioning for high-order Galerkin Least-Squares methods using inexact solvers

A high-order Galerkin Least-Squares (GLS) finite element discretization is combined with a Balancing Domain Decomposition by Constraints (BDDC) preconditioner and inexact local solvers to provide an efficient solution technique for large-scale, convection-dominated problems. The algorithm is applied to the linear system arising from the discretization of the two-dimensional advection–diffusion equation and Euler equations for compressible, inviscid flow. A Robin–Robin interface condition is extended to the Euler equations using entropy-symmetrized variables. The BDDC method maintains scalability for the high-order discretization of the diffusion-dominated flows, and achieves low iteration count in the advection-dominated regime. The BDDC method based on inexact local solvers with incomplete factorization and p = 1 coarse correction maintains the performance of the exact counterpart for the wide range of the Peclet numbers considered while at significantly reduced memory and computational costs.     

Weak discontinuity annihilation in solidification modelling

Discontinuous behaviour provides substantial obstacles to the efficient application of mesh based numerical techniques. Accounting for strong discontinuities is presently of particular interest to the finite element research community with for example the development of cohesive and enriched elements to cater for material separation. Although strong discontinuities are of importance, of equal if not of greater interest and the focus in this paper, are weak discontinuities, which are present at any material change. A recent innovation for accounting for weak discontinuities has been the discovery of non-physical variables which are founded and defined using transport equations.This paper is concerned with the application of the non-physical approach to solidification modelling in the presence of more than one material discontinuity. A typical feature of the enthalpy-temperature response in solidification is discontinuities at phase transition temperatures as a consequence of phase change and latent heat release. In these circumstances, depending on the conditions that prevail, an element in a finite element mesh can have more than one discontinuity present.Presented in the paper is a methodology that can cater for multiple discontinuities. The non-physical approach permits the precise removal of weak discontinuities arising in the governing transport equations. In order to facilitate the application of the approach the finite element equations are presented in the form of weighted transport equations. The method utilises a non-physical form of enthalpy that possesses a remarkable source distribution like property at a discontinuity. It is demonstrated in the paper that it is through this property that multiple discontinuities can be exactly removed from an element so facilitating the use of continuous approximations.The new methodology is applied to a range of simple problems to provide an in-depth treatment and for ease of understanding to demonstrate the methods remarkable accuracy and stability.     

采用PETSc的有限元并行计算实现与优化

可移植可扩展科学计算工具箱PETSc提供了高性能求解偏微分方程组的大量对象和解法库,基于此进行结构有限元并行计算,可降低难度和成本。给出了基于PETS的结构有限元并行计算实现方法,包括有限元方程组的并行形成和并行求解的实现。根据PETSc的特点,提出了提高计算性能的优化措施,即数据局部化和存储预分配。数值实验表明实现方法可行,优化措施效果明显。     

Multilevel algorithms for Rannacher–Turek finite element approximation of 3D elliptic problems

Generalizing the approach of a previous work of the authors, dealing with two-dimensional (2D) problems, we present multilevel preconditioners for three-dimensional (3D) elliptic problems discretized by a family of Rannacher Turek non-conforming finite elements. Preconditioners based on various multilevel extensions of two-level finite element methods (FEM) lead to iterative methods which often have an optimal order computational complexity with respect to the number of degrees of freedom of the system. Such methods were first presented by Axelsson and Vassilevski in the late-1980s, and are based on (recursive) two-level splittings of the finite element space. An important point to make is that in the case of non-conforming elements the finite element spaces corresponding to two successive levels of mesh refinement are not nested in general. To handle this, a proper two-level basis is required to enable us to fit the general framework for the construction of two-level preconditioners for conforming finite elements and to generalize the method to the multilevel case. In the present paper new estimates of the constant γ in the strengthened Cauchy–Bunyakowski–Schwarz (CBS) inequality are derived that allow an efficient multilevel extension of the related two-level preconditioners. Representative numerical tests well illustrate the optimal complexity of the resulting iterative solver, also for the case of non-smooth coefficients. The second important achievement concerns the experimental study of AMLI solvers applied to the case of micro finite element (μFEM) simulation. Here the coefficient jumps are resolved on the finest mesh only and therefore the classical CBS inequality based convergence theory is not directly applicable. The obtained results, however, demonstrate the efficiency of the proposed algorithms in this case also, as is illustrated by an example of microstructure analysis of bones.      

A new optimality criteria method for shape optimization of natural frequency problems

A new shape optimization method for natural frequency problems is presented. The approach is based on an optimality criterion for general continuum solids, which is derived in this paper for the maximization of the first natural frequency with a volume constraint. An efficient redesign rule for frequency problems is developed to achieve the required shape modifications. The optimality criterion is extended to volume minimization problems with multiple frequency constraints. The nonparametric geometry representation creates a complete design space for the optimization problem, which includes all possible solutions for the finite element discretization. The combination with the optimality criteria approach results in a robust and fast convergence, which is independent of the number of design variables. Sensitivity information of objective function and constraints are not required, which allows to solve the structural analysis task using fast and reliable industry standard finite element solvers like ABAQUS, ANSYS, I-DEAS, MARC, NASTRAN, or PERMAS. The new approach is currently being implemented in the optimization system TOSCA.     

Multidimensional exponentially fitted simplicial finite elements for convection-diffusion equations with tensor-valued diffusion

Abstract In this paper we propose and analyze an exponentially fitted simplicial finite element method for the numerical approximation of solutions to diffusion-convection equations with tensor-valued diffusion coefficients. The finite element method is first formulated using exponentially fitted finite element basis functions constructed on simplicial elements in arbitrary dimensions. Stability of the method is then proved by showing that the corresponding bilinear form is coercive. Upper error bounds for the approximate solution and the associated flux are established.     

A low order Galerkin finite element method for the Navier–Stokes equations of steady incompressible flow: a stabilization issue and iterative methods

A Galerkin finite element method is considered to approximate the incompressible Navier–Stokes equations together with iterative methods to solve a resulting system of algebraic equations. This system couples velocity and pressure unknowns, thus requiring a special technique for handling. We consider the Navier–Stokes equations in velocity––kinematic pressure variables as well as in velocity––Bernoulli pressure variables. The latter leads to the rotation form of nonlinear terms. This form of the equations plays an important role in our studies. A consistent stabilization method is considered from a new view point. Theory and numerical results in the paper address both the accuracy of the discrete solutions and the effectiveness of solvers and a mutual interplay between these issues when particular stabilization techniques are applied.     

<Emphasis FontCategory="NonProportional">FEMPAR</Emphasis>: An Object-Oriented Parallel Finite Element Framework

FEMPAR is an open source object oriented Fortran200X scientific software library for the high-performance scalable simulation of complex multiphysics problems governed by partial differential equations at large scales, by exploiting state-of-the-art supercomputing resources. It is a highly modularized, flexible, and extensible library, that provides a set of modules that can be combined to carry out the different steps of the simulation pipeline. FEMPAR includes a rich set of algorithms for the discretization step, namely (arbitrary-order) grad, div, and curl-conforming finite element methods, discontinuous Galerkin methods, B-splines, and unfitted finite element techniques on cut cells, combined with h-adaptivity. The linear solver module relies on state-of-the-art bulk-asynchronous implementations of multilevel domain decomposition solvers for the different discretization alternatives and block-preconditioning techniques for multiphysics problems. FEMPAR is a framework that provides users with out-of-the-box state-of-the-art discretization techniques and highly scalable solvers for the simulation of complex applications, hiding the dramatic complexity of the underlying algorithms. But it is also a framework for researchers that want to experience with new algorithms and solvers, by providing a highly extensible framework. In this work, the first one in a series of articles about FEMPAR, we provide a detailed introduction to the software abstractions used in the discretization module and the related geometrical module. We also provide some ingredients about the assembly of linear systems arising from finite element discretizations, but the software design of complex scalable multilevel solvers is postponed to a subsequent work.     

Fast Tensor-Product Solvers: Partially Deformed Three-dimensional Domains

We discuss the numerical solution of partial differential equations in a particular class of three-dimensional geometries; the two-dimensional cross section (in the xy-plane) can have a general shape, but is assumed to be invariant with respect to the third direction. Earlier work has exploited such geometries by approximating the solution as a truncated Fourier series in the z-direction. In this paper we propose a new solution algorithm which also exploits the tensor-product feature between the xy-plane and the z-direction. However, the new algorithm is not limited to periodic boundary conditions, but works for general Dirichlet and Neumann type of boundary conditions. The proposed algorithm also works for problems with variable coefficients as long as these can be expressed as a separable function with respect to the variation in the xy-plane and the variation in the z-direction. For problems where the new method is applicable, the computational cost is very competitive with the best iterative solvers. The new algorithm is easy to implement, and useful, both in a serial and parallel context. Numerical results demonstrating the superiority of the method are presented for three-dimensional Poisson and Helmholtz problems using both low order finite elements and high order spectral element discretizations.     

Error estimation and adaptive procedures based on superconvergent patch recovery (SPR) techniques

Summary  The paper discusses error estimation and adaptive finite element procedures for elasto-static and dynamic problems based on superconvergent patch recovery (SPR) techniques. The SPR is a postprocessing procedure to obtain improved finite element solutions by the least squares fitting of superconvergent stresses at certain sampling points in local patches. An enhancement of the original SPR by accounting for the equilibirum equations and boundary conditions is proposed. This enhancement improves the quality of postprocessed solutions considerably and thus provides an even more effective error estimate. The patch configuration of SPR can be either the union of elements surrounding a vertex node, thenode patch, or, the union of elements surrounding an element, theelement patch. It is shown that these two choices give normally comparable quality of postprocessed solutions. The paper is also concerned with the application of SPR techniques to a wide range of problems. The plate bending problem posted in mixed form where force and displacement variables are simultaneously used as unknowns is considered. For eigenvalue problems, a procedure of improving eigenpairs and error estimation of the eigenfrequency is presented. A postprocessed type of error estimate and an adaptive procedure for the semidiscrete finite element method are discussed. It is shown that the procedure is able to update the spatial mesh and the time step size so that both spatial and time discretization errors are controlled within specified tolerances. A discontinuous Galerkin method for solving structural dynamics is also presented.     

Performance of iterative methods in ANSYS on cray parallel/vector supercomputers

This paper describes recent work using iterative methods for the solution of linear systems in the ANSYS program. The ANSYS program, a general purpose finite element code widely used in structural analysis applications, has now added an iterative solver option. The development of robust iterative solvers and their use in commercial programs is discussed. Discussion of the applicability of iterative solvers as a general purpose solver will include the topics of robustness; as well as memory requirements and CPU performance. A new iterative solver for general purpose finite element codes which functions as a “black-box” solver using element-specific information and the underlying problem physics to construct an effective and inexpensive preconditioner is described. Some results are given from realistic examples comparing the performance of the iterative solver implemented in ANSYS with the traditional parallel/vector frontal solver used in ANSYS and a robust shifted incomplete Choleski iterative solver.     

An energy-preserving algorithm for nonlinear Hamiltonian wave equations with Neumann boundary conditions

In this paper, a novel energy-preserving numerical scheme for nonlinear Hamiltonian wave equations with Neumann boundary conditions is proposed and analyzed based on the blend of spatial discretization by finite element method (FEM) and time discretization by Average Vector Field (AVF) approach. We first use the finite element discretization in space, which leads to a system of Hamiltonian ODEs whose Hamiltonian can be thought of as the semi-discrete energy of the original continuous system. The stability of the semi-discrete finite element scheme is analyzed. We then apply the AVF approach to the Hamiltonian ODEs to yield a new and efficient fully discrete scheme, which can preserve exactly (machine precision) the semi-discrete energy. The blend of FEM and AVF approach derives a new and efficient numerical scheme for nonlinear Hamiltonian wave equations. The numerical results on a single-soliton problem and a sine-Gordon equation are presented to demonstrate the remarkable energy-preserving property of the proposed numerical scheme.     

Looking back at dense linear algebra software

Over the years, computational physics and chemistry served as an ongoing source of problems that demanded the ever increasing performance from hardware as well as the software that ran on top of it. Most of these problems could be translated into solutions for systems of linear equations: the very topic of numerical linear algebra. Seemingly then, a set of efficient linear solvers could be solving important scientific problems for years to come. We argue that dramatic changes in hardware designs precipitated by the shifting nature of the marketplace of computer hardware had a continuous effect on the software for numerical linear algebra. The extraction of high percentages of peak performance continues to require adaptation of software. If the past history of this adaptive nature of linear algebra software is any guide then the future theme will feature changes as well–changes aimed at harnessing the incredible advances of the evolving hardware infrastructure.     

Efficient monolithic simulation techniques for the stationary Lattice Boltzmann equation on general meshes

In this paper, we present special discretization and solution techniques for the numerical simulation of the Lattice Boltzmann equation (LBE). In Hübner and Turek (Computing, 81:281–296, 2007), the concept of the generalized mean intensity had been proposed for radiative transfer equations which we adapt here to the LBE, treating it as an analogous (semi-discretized) integro-differential equation with constant characteristics. Thus, we combine an efficient finite difference-like discretization based on short-characteristic upwinding techniques on unstructured, locally adapted grids with fast iterative solvers. The fully implicit treatment of the LBE leads to nonlinear systems which can be efficiently solved with the Newton method, even for a direct solution of the stationary LBE. With special exact preconditioning by the transport part due to the short-characteristic upwinding, we obtain an efficient linear solver for transport dominated configurations (macroscopic Stokes regime), while collision dominated cases (Navier-Stokes regime for larger Re numbers) are treated with a special block-diagonal preconditioning. Due to the new generalized equilibrium formulation (GEF) we can combine the advantages of both preconditioners, i.e. independence of the number of unknowns for convection-dominated cases with robustness for stiff configurations. We further improve the GEF approach by using hierarchical multigrid algorithms to obtain grid-independent convergence rates for a wide range of problem parameters, and provide representative results for various benchmark problems. Finally, we present quantitative comparisons between a highly optimized CFD-solver based on the Navier-Stokes equation (FeatFlow) and our new LBE solver (FeatLBE).     

On the use of inexact subdomain solvers for BDDC algorithms

The standard BDDC (balancing domain decomposition by constraints) preconditioner is shown to be equivalent to a preconditioner built from a partially subassembled finite element model. This results in a system of linear algebraic equations which is much easier to solve in parallel than the fully assembled model; the cost is then often dominated by that of the problems on the subdomains. An important role is also played, both in theory and practice, by an averaging operator and in addition exact Dirichlet solvers are used on the subdomains in order to eliminate the residual in the interior of the subdomains. The use of inexact solvers for these problems and even the replacement of the Dirichlet solvers by a trivial extension are considered. It is established that one of the resulting algorithms has the same eigenvalues as the standard BDDC algorithm, and the connection of another with the FETI-DP algorithm with a lumped preconditioner is also considered. Multigrid methods are used in the experimental work and under certain assumptions, it is established that the iteration count essentially remains the same as when exact solvers are used, while considerable gains in the speed of the algorithm can be realized since the cost of the exact solvers grows superlinearly with the size of the subdomain problems while the multigrid methods are linear.     

Parallel multilevel solution of nonlinear shell structures

The analysis of large-scale nonlinear shell problems asks for parallel simulation approaches. One crucial part of efficient and well scalable parallel FE-simulations is the solver for the system of equations. Due to the inherent suitability for parallelization one is very much directed towards preconditioned iterative solvers. However thin-walled-structures discretized by finite elements lead to ill-conditioned system matrices and therefore performance of iterative solvers is generally poor. This situation further deteriorates when the thickness change of the shell is taken into account. A preconditioner for this challenging class of problems is presented combining two approaches in a parallel framework. The first approach is a mechanically motivated improvement called ‘scaled director conditioning’ (SDC) and is able to remove the extra-ill conditioning that appears with three-dimensional shell formulations as compared to formulations that neglect thickness change of the shell. It is introduced at the element level and harmonizes well with the second approach utilizing a multilevel algorithm. Here a hierarchy of coarse grids is generated in a semi-algebraic sense using an aggregation concept. Thereby the complicated and expensive explicit generation of course triangulations can be avoided. The formulation of this combined preconditioning approach is given and the effects on the performance of iterative solvers is demonstrated via numerical examples.     

Aspects of an adaptive hp-finite element method: Adaptive strategy, conforming approximation and efficient solvers

The main components needed for an adaptive hp-version finite element algorithm are discussed: an adaptive hp-refinement strategy, effective methods for constructing conforming hp-approximations, and, efficient solvers for the large, ill-conditioned systems of linear equations. Together, these provide the methodology for an effective adaptive hp-version algorithm. The presentation emphasizes the links between the differing components showing how the algorithms may be implemented efficiently in practice. The main principles are illustrated by use of concrete examples so that a non-expert may develop their own adaptive hp-code. The performance of the whole algorithm is illustrated for some representative problems taken from linear elasticity.