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.     

Truly monolithic algebraic multigrid for fluid–structure interaction

The coupling of flexible structures to incompressible fluids draws a lot of attention during the last decade. Many different solution schemes have been proposed. In this contribution, we concentrate on the strong coupling fluid–structure interaction by means of monolithic solution schemes. Therein, a Newton–Krylov method is applied to the monolithic set of nonlinear equations. Such schemes require good preconditioning to be efficient. We propose two preconditioners that apply algebraic multigrid techniques to the entire fluid–structure interaction system of equations. The first is based on a standard block Gauss–Seidel approach, where approximate inverses of the individual field blocks are based on a algebraic multigrid hierarchy tailored for the type of the underlying physical problem. The second is based on a monolithic coarsening scheme for the coupled system that makes use of prolongation and restriction projections constructed for the individual fields. The resulting nonsymmetric monolithic algebraic multigrid method therefore involves coupling of the fields on coarse approximations to the problem yielding significantly enhanced performance. Copyright © 2010 John Wiley & Sons, Ltd.     

FLEXMG: A new library of multigrid preconditioners for a spectral/finite element incompressible flow solver

A new library called FLEX MG has been developed for a spectral/finite element incompressible flow solver called SFELES. FLEX MG allows the use of various types of iterative solvers preconditioned by algebraic multigrid methods. Two families of algebraic multigrid preconditioners have been implemented, namely smooth aggregation‐type and non‐nested finite element‐type. Unlike pure gridless multigrid, both of these families use the information contained in the initial fine mesh. A hierarchy of coarse meshes is also needed for the non‐nested finite element‐type multigrid so that our approaches can be considered as hybrid. Our aggregation‐type multigrid is smoothed with either a constant or a linear least‐square fitting function, whereas the non‐nested finite element‐type multigrid is already smooth by construction. All these multigrid preconditioners are tested as stand‐alone solvers or coupled with a GMRES method. After analyzing the accuracy of the solutions obtained with our solvers on a typical test case in fluid mechanics, their performance in terms of convergence rate, computational speed and memory consumption is compared with the performance of a direct sparse LU solver as a reference. Finally, the importance of using smooth interpolation operators is also underlined in the study. Copyright © 2010 John Wiley & Sons, Ltd.     

Solvers for large-displacement fluid–structure interaction problems: segregated versus monolithic approaches

We compare the relative performance of monolithic and segregated (partitioned) solvers for large- displacement fluid–structure interaction (FSI) problems within the framework of oomph-lib, the object-oriented multi-physics finite-element library, available as open-source software at . Monolithic solvers are widely acknowledged to be more robust than their segregated counterparts, but are believed to be too expensive for use in large-scale problems. We demonstrate that monolithic solvers are competitive even for problems in which the fluid–solid coupling is weak and, hence, the segregated solvers converge within a moderate number of iterations. The efficient monolithic solution of large-scale FSI problems requires the development of preconditioners for the iterative solution of the linear systems that arise during the solution of the monolithically coupled fluid and solid equations by Newton’s method. We demonstrate that recent improvements to oomph-lib’s FSI preconditioner result in mesh-independent convergence rates under uniform and non-uniform (adaptive) mesh refinement, and explore its performance in a number of two- and three-dimensional test problems involving the interaction of finite-Reynolds-number flows with shell and beam structures, as well as finite-thickness solids.     

Algebraic multigrid methods for dual mortar finite element formulations in contact mechanics

This paper proposes novel strategies to enable multigrid preconditioners within iterative solvers for linear systems arising from contact problems based on mortar finite element formulations. The so‐called dual mortar approach that is exclusively employed here allows for an easy condensation of the discrete Lagrange multipliers. Therefore, it has the advantage over standard mortar methods that linear systems with a saddle‐point structure are avoided, which generally require special preconditioning techniques. However, even with the dual mortar approach, the resulting linear systems turn out to be hard to solve using iterative linear solvers. A basic analysis of the mathematical properties of the linear operators reveals why the naive application of standard iterative solvers shows instabilities and provides new insights of how contact modeling affects the corresponding linear systems. This information is used to develop new strategies that make multigrid methods efficient preconditioners for the class of contact problems based on dual mortar methods. It is worth mentioning that these strategies primarily adapt the input of the multigrid preconditioners in a way that no contact‐specific enhancements are necessary in the multigrid algorithms. This makes the implementation comparably easy. With the proposed method, we are able to solve large contact problems, which is an important step toward the application of dual mortar–based contact formulations in the industry. Numerical results are presented illustrating the performance of the presented algebraic multigrid method.     

A rheological interface model and its space–time finite element formulation for fluid–structure interaction

This contribution discusses extended physical interface models for fluid–structure interaction problems and investigates their phenomenological effects on the behavior of coupled systems by numerical simulation. Besides the various types of friction at the fluid–structure interface the most interesting phenomena are related to effects due to additional interface stiffness and damping. The paper introduces extended models at the fluid–structure interface on the basis of rheological devices (Hooke, Newton, Kelvin, Maxwell, Zener). The interface is decomposed into a Lagrangian layer for the solid‐like part and an Eulerian layer for the fluid‐like part. The mechanical model for fluid–structure interaction is based on the equations of rigid body dynamics for the structural part and the incompressible Navier–Stokes equations for viscous flow. The resulting weighted residual form uses the interface velocity and interface tractions in both layers in addition to the field variables for fluid and structure. The weak formulation of the whole coupled system is discretized using space–time finite elements with a discontinuous Galerkin method for time‐integration leading to a monolithic algebraic system. The deforming fluid domain is taken into account by deformable space–time finite elements and a pseudo‐structure approach for mesh motion. The sensitivity of coupled systems to modification of the interface model and its parameters is investigated by numerical simulation of flow induced vibrations of a spring supported fluid‐immersed cylinder. It is shown that the presented rheological interface model allows to influence flow‐induced vibrations. Copyright © 2010 John Wiley & Sons, Ltd.     

Investigation of fluid–structure interactions using a velocity‐linked P2/P1 finite element method and the generalized‐ α method

A velocity‐linked algorithm for solving unsteady fluid–structure interaction (FSI) problems in a fully coupled manner is developed using the arbitrary Lagrangian–Eulerian method. The P2/P1 finite element is used to spatially discretize the incompressible Navier–Stokes equations and structural equations, and the generalized‐ α method is adopted for temporal discretization. Common velocity variables are employed at the fluid–structure interface for the strong coupling of both equations. Because of the velocity‐linked formulation, kinematic compatibility is automatically satisfied and forcing terms do not need to be calculated explicitly. Both the numerical stability and the convergence characteristics of an iterative solver for the coupled algorithm are investigated by solving the FSI problem of flexible tube flows. It is noteworthy that the generalized‐ α method with small damping is free from unstable velocity fields. However, the convergence characteristics of the coupled system deteriorate greatly for certain Poisson's ratios so that direct solvers are essential for these cases. Furthermore, the proposed method is shown to clearly display the advantage of considering FSI in the simulation of flexible tube flows, while enabling much larger time‐steps than those adopted in some previous studies. This is possible through the strong coupling of the fluid and structural equations by employing common primitive variables. Copyright © 2012 John Wiley & Sons, Ltd.     

The enriched space–time finite element method (EST) for simultaneous solution of fluid–structure interaction

The paper introduces a weighted residual‐based approach for the numerical investigation of the interaction of fluid flow and thin flexible structures. The presented method enables one to treat strongly coupled systems involving large structural motion and deformation of multiple‐flow‐immersed solid objects. The fluid flow is described by the incompressible Navier–Stokes equations. The current configuration of the thin structure of linear elastic material with non‐linear kinematics is mapped to the flow using the zero iso‐contour of an updated level set function. The formulation of fluid, structure and coupling conditions uniformly uses velocities as unknowns. The integration of the weak form is performed on a space–time finite element discretization of the domain. Interfacial constraints of the multi‐field problem are ensured by distributed Lagrange multipliers. The proposed formulation and discretization techniques lead to a monolithic algebraic system, well suited for strongly coupled fluid–structure systems. Embedding a thin structure into a flow results in non‐smooth fields for the fluid. Based on the concept of the extended finite element method, the space–time approximations of fluid pressure and velocity are properly enriched to capture weakly and strongly discontinuous solutions. This leads to the present enriched space–time (EST) method. Numerical examples of fluid–structure interaction show the eligibility of the developed numerical approach in order to describe the behavior of such coupled systems. The test cases demonstrate the application of the proposed technique to problems where mesh moving strategies often fail. Copyright © 2007 John Wiley & Sons, Ltd.     

Fast Computation of Stationary Inviscid Flow Around an Airfoil

The parallel performance of an implicit solver for the Euler equations on a structured grid is discussed. The flow studied is a two-dimensional transonic flow around an airfoil. The spatial discretization involves the MUSCL scheme, a higher-order Total Variation Diminishing scheme. The solver described in this paper is an implicit solver that is based on quasi Newton iteration and approximate factorization to solve the linear system of equations resulting from the Euler Backward scheme. It is shown that the implicit time-stepping method can be used as a smoother to obtain an efficient and stable multigrid process. Also, the solver has good properties for parallelization comparable with explicit time-stepping schemes. To preserve data locality domain decomposition is applied to obtain a parallelizable code. Although the domain decomposition slightly affects the efficiency of the approximate factorization method with respect to the number of time steps required to attain the stationary solution, the results show that this hardly affects the performance for practical purposes. The accuracy with which the linear system of equations is solved is found to be an important parameter. Because the method is equally applicable for the Navier-Stokes equations and in three-dimensions, the presented combination of efficient parallel execution and implicit time-integration provides an interesting perspective for time-dependent problems in computational fluid dynamics.     

Performance of fully coupled algebraic multilevel domain decomposition preconditioners for incompressible flow and transport

This study investigates algebraic multilevel domain decomposition preconditioners of the Schwarz type for solving linear systems associated with Newton–Krylov methods. The key component of the preconditioner is a coarse approximation based on algebraic multigrid ideas to approximate the global behaviour of the linear system. The algebraic multilevel preconditioner is based on an aggressive coarsening graph partitioning of the non‐zero block structure of the Jacobian matrix. The scalability of the preconditioner is presented as well as comparisons with a two‐level Schwarz preconditioner using a geometric coarse grid operator. These comparisons are obtained on large‐scale distributed‐memory parallel machines for systems arising from incompressible flow and transport using a stabilized finite element formulation. The results demonstrate the influence of the smoothers and coarse level solvers for a set of 3D example problems. For preconditioners with more than one level, careful attention needs to be given to the balance of robustness and convergence rate for the smoothers and the cost of applying these methods. For properly chosen parameters, the two‐ and three‐level preconditioners are demonstrated to be scalable to 1024 processors. Copyright © 2006 John Wiley & Sons, Ltd.     

A sub‐grid scale finite element agglomeration multigrid method with application to the Boltzmann transport equation

This article describes a new element agglomeration multigrid method for solving partial differential equations discretised through a sub‐grid scale finite element formulation. The sub‐grid scale discretisation resolves solution variables through their separate coarse and fine scales, and these are mapped between the multigrid levels using a dual set of transfer operators. The sub‐grid scale multigrid method forms coarse linear systems, possessing the same sub‐grid scale structure as the original discretisation, that can be resolved without them being stored in memory. This is necessary for the application of this article in resolving the Boltzmann transport equation as the linear systems become extremely large. The novelty of this article is therefore a matrix‐free multigrid scheme that is integrated within its own sub‐grid scale discretisation using dual transfer operators and applied to the Boltzmann transport equation. The numerical examples presented are designed to show the method's preconditioning capabilities for a Krylov space‐based solver. The problems range in difficulty, geometry and discretisation type, and comparisons made with established methods show this new approach to perform consistently well. Smoothing operators are also analysed and this includes using the generalized minimal residual method. Here, it is shown that an adaptation to the preconditioned Krylov space is necessary for it to work efficiently. Copyright © 2012 John Wiley & Sons, Ltd.     

A matrix-free approach for finite-strain hyperelastic problems using geometric multigrid

This work investigates matrix-free algorithms for problems in quasi-static finite-strain hyperelasticity. Iterative solvers with matrix-free operator evaluation have emerged as an attractive alternative to sparse matrices in the fluid dynamics and wave propagation communities because they significantly reduce the memory traffic, the limiting factor in classical finite element solvers. Specifically, we study different matrix-free realizations of the finite element tangent operator and determine whether generalized methods of incorporating complex constitutive behavior might be feasible. In order to improve the convergence behavior of iterative solvers, we also propose a method by which to construct level tangent operators and employ them to define a geometric multigrid preconditioner. The performance of the matrix-free operator and the geometric multigrid preconditioner is compared to the matrix-based implementation with an algebraic multigrid (AMG) preconditioner on a single node for a representative numerical example of a heterogeneous hyperelastic material in two and three dimensions. We find that matrix-free methods for finite-strain solid mechanics are very promising, outperforming linear matrix-based schemes by two to five times, and that it is possible to develop numerically efficient implementations that are independent of the hyperelastic constitutive law.     

Analytic preconditioners for the electric field integral equation

Since the advent of the fast multipole method, large‐scale electromagnetic scattering problems based on the electric field integral equation (EFIE) formulation are generally solved by a Krylov iterative solver. A well‐known fact is that the dense complex non‐hermitian linear system associated to the EFIE becomes ill‐conditioned especially in the high‐frequency regime. As a consequence, this slows down the convergence rate of Krylov subspace iterative solvers. In this work, a new analytic preconditioner based on the combination of a finite element method with a local absorbing boundary condition is proposed to improve the convergence of the iterative solver for an open boundary. Some numerical tests precise the behaviour of the new preconditioner. Moreover, comparisons are performed with the analytic preconditioner based on the Calderòn's relations for integral equations for several kinds of scatterers. Copyright © 2004 John Wiley & Sons, Ltd.     

Adaptive embedded unstructured grid methods

A simple embedded domain method for node‐based unstructured grid solvers is presented. The key modification of the original, edge‐based solver is to remove all geometry‐parameters (essentially the normals) belonging to edges cut by embedded surface faces. Several techniques to improve the treatment of boundary points close to the immersed surfaces are explored. Alternatively, higher‐order boundary conditions are achieved by duplicating crossed edges and their endpoints. Adaptive mesh refinement based on proximity to or the curvature of the embedded CSD surfaces is used to enhance the accuracy of the solution. User‐defined or automatic deactivation for the regions inside immersed solid bodies is employed to avoid unnecessary work. Several examples are included that show the viability of this approach for inviscid and viscous, compressible and incompressible, steady and unsteady flows, as well as coupled fluid–structure problems. Copyright © 2004 John Wiley & Sons, Ltd.     

A simultaneous solution procedure for strong interactions of generalized Newtonian fluids and viscoelastic solids at large strains

The paper presents a methodology for numerical analyses of coupled systems exhibiting strong interactions of viscoelastic solids and generalized Newtonian fluids. In the monolithic approach, velocity variables are used for both solid and fluid, and the entire set of model equations is discretized with stabilized space–time finite elements. A viscoelastic material model for finite deformations, which is based on the concept of internal variables, describes the stress‐deformation behaviour of the solid. In the generalized Newtonian approach for the fluid, the viscosity depends on the shear strain rate, leading to common non‐Newtonian fluid models like the power‐law. The consideration of non‐linear constitutive equations for solid and fluid documents the capability of the monolithic space–time finite element formulation to deal with complex material models. The methodology is applied to fluid‐conveying cantilevered pipes in order to determine the influence of material non‐linearities on stability characteristics of coupled systems. Copyright © 2005 John Wiley & Sons, Ltd.     

A new parallel sparse direct solver: Presentation and numerical experiments in large‐scale structural mechanics parallel computing

The main purpose of this work is to present a new parallel direct solver: Dissection solver. It is based on LU factorization of the sparse matrix of the linear system and allows to detect automatically and handle properly the zero‐energy modes, which are important when dealing with DDM. A performance evaluation and comparisons with other direct solvers (MUMPS, DSCPACK) are also given for both sequential and parallel computations. Results of numerical experiments with a two‐level parallelization of large‐scale structural analysis problems are also presented: FETI is used for the global problem parallelization and Dissection for the local multithreading. In this framework, the largest problem we have solved is of an elastic solid composed of 400 subdomains running on 400 computation nodes (3200 cores) and containing about 165 millions dof. The computation of one single iteration consumes less than 20 min of CPU time. Several comparisons to MUMPS are given for the numerical computation of large‐scale linear systems on a massively parallel cluster: performances and weaknesses of this new solver are highlighted. Copyright © 2011 John Wiley & Sons, Ltd.     

CMRH method as iterative solver for boundary element acoustic systems

Disceretization of boundary integral equations leads to complex and fully populated linear systems. One inherent drawback of the boundary element method (BEM) is that, the dense linear system has to be constructed and solved for each frequency. For large-scale problems, BEM can be more efficient by improving the construction and solution phases of the linear system. For these problems, the application of common direct solver is inefficient. In this paper, the corresponding linear systems are solved more efficiently than common direct solvers by using the iterative technique called CMRH (Changing Minimal Residual method based on Hessenberg process). In this method, the generation of the basis vectors of the Krylov subspace is based on the Hessenberg process instead of Arnoldi's one that the most known GMRES (Generalized Minimal RESidual) solver uses. Compared to GMRES, the storage requirements are considerably reduced in CMRH.     

A monolithic computational approach to thermo‐structure interaction

In the present work, a monolithic solution approach for thermo‐structure interaction problems motivated by the challenging application of the behaviour of rocket nozzles is proposed. Structural and thermal fields are independently discretised via finite elements. The resulting system of equations is solved via a monolithic thermo‐structure interaction scheme, which is constructed by a block Gauss–Seidel preconditioner in combination with algebraic multigrid methods. The proposed method is tested for four numerical examples, the second Danilovskaya problem, a simplified rocket nozzle configuration, an internally loaded hollow sphere, and a fully three‐dimensional nozzle configuration of a subscale thrust chamber. Good agreement of the numerical results with results from the literature is observed. Furthermore, it is shown that the monolithic solution algorithm can handle the complete range of the parameter spectrum, whereas partitioned algorithms are limited to a certain parameter range only. Moreover, the monolithic algorithm exhibits improved efficiency and robustness compared to partitioned algorithms. Copyright © 2013 John Wiley & Sons, Ltd.     

Time‐decomposed parallel time‐integrators: theory and feasibility studies for fluid,structure, and fluid–structure applications

A methodology for squeezing the most out of massively parallel processors when solving partial differential evolution equations by implicit schemes is presented. Its key components include a preferred implicit time‐integrator, a decomposition of the time‐domain into time‐slices, independent time‐integrations in each time‐slice of the semi‐discrete equations, and Newton‐type iterations on a coarse time‐grid. Hence, this methodology parallelizes the time‐loop of a time‐dependent partial differential equation solver without interfering with its sequential or parallel space‐computations. It is particularly interesting for time‐dependent problems with a few degrees of freedom such as those arising in robotics and protein folding applications, where the opportunities for parallelization over the degrees of freedom are limited. Error and stability analyses of the proposed parallel methodology are performed for first‐ and second‐order hyperbolic problems. Its feasibility and impact on reducing the solution time below what is attainable by methods which address only parallelism in the space‐domain are highlighted for fluid, structure, and coupled fluid–structure model problems. Copyright © 2003 John Wiley & Sons, Ltd.     

Evaluation of three unstructured multigrid methods on 3D finite element problems in solid mechanics

Multigrid has been a popular solver method for finite element and finite difference problems with regular grids for over 20 years. The application of multigrid to unstructured grid problems, in which it is often difficult or impossible for the application to provide coarse grids, is not as well understood. In particular, methods that are designed to require only data that are easily available in most finite element applications (i.e. fine grid data), constructing the grid transfer operators and coarse grid operators internally, are of practical interest. We investigate three unstructured multigrid methods that show promise for challenging problems in 3D elasticity: (1) non‐nested geometric multigrid, (2) smoothed aggregation, and (3) plain aggregation algebraic multigrid. This paper evaluates the effectiveness of these three methods on several unstructured grid problems in 3D elasticity with up to 76 million degrees of freedom. Published in 2002 by John Wiley & Sons, Ltd.