A fast and robust iterative solver for nonlinear contact problems using a primal‐dual active set strategy and algebraic multigrid

For extending the usability of implicit FE codes for large‐scale forming simulations, the computation time has to be decreased dramatically. In principle this can be achieved by using iterative solvers. In order to facilitate the use of this kind of solvers, one needs a contact algorithm which does not deteriorate the condition number of the system matrix and therefore does not slow down the convergence of iterative solvers like penalty formulations do. Additionally, an algorithm is desirable which does not blow up the size of the system matrix like methods using standard Lagrange multipliers. The work detailed in this paper shows that a contact algorithm based on a primal‐dual active set strategy provides these advantages and therefore is highly efficient with respect to computation time in combination with fast iterative solvers, especially algebraic multigrid methods. Copyright © 2006 John Wiley & Sons, Ltd.     

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.     

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.     

Incorporation of linear multipoint constraints in substructure based iterative solvers. Part 1: a numerically scalable algorithm

We consider the iterative solution by a class of substructuring methods of the large-scale systems of equations arising from the finite element discretization of structural models with an arbitrary set of linear multipoint constraints. We present a methodology for generalizing to such problems numerically scalable substructure based iterative solvers, without interfering with their formulations and their well-established local and global preconditioners. We apply this methodology to the FETI method, and show that the resulting algorithm is numerically scalable with respect to both the substructure and problem sizes. © 1998 John Wiley & Sons, Ltd.     

A monolithic geometric multigrid solver for fluid‐structure interactions in ALE formulation

We present a monolithic geometric multigrid solver for fluid‐structure interaction problems in Arbitrary Lagrangian Eulerian coordinates. The coupled dynamics of an incompressible fluid with nonlinear hyperelastic solids gives rise to very large and ill‐conditioned systems of algebraic equations. Direct solvers usually are out of question because of memory limitations, and standard coupled iterative solvers are seriously affected by the bad condition number of the system matrices. The use of partitioned preconditioners in Krylov subspace iterations is an option, but the convergence will be limited by the outer partitioning. Our proposed solver is based on a Newton linearization of the fully monolithic system of equations, discretized by a Galerkin finite element method. Approximation of the linearized systems is based on a monolithic generalized minimal residual method iteration, preconditioned by a geometric multigrid solver. The special character of fluid‐structure interactions is accounted for by a partitioned scheme within the multigrid smoother only. Here, fluid and solid field are segregated as Dirichlet–Neumann coupling. We demonstrate the efficiency of the multigrid iteration by analyzing 2d and 3d benchmark problems. While 2d problems are well manageable with available direct solvers, challenging 3d problems highly benefit from the resulting multigrid solver. Copyright © 2015 John Wiley & Sons, Ltd.     

Robust and efficient domain decomposition preconditioners for adaptive hp finite element approximations of linear elasticity with and without discontinuous coefficients

Adaptive finite element methods (FEM) generate linear equation systems that require dynamic and irregular patterns of storage, access, and computation, making their parallelization difficult. Additional difficulties are generated for problems in which the coefficients of the governing partial differential equations have large discontinuities. We describe in this paper the development of a set of iterative substructuring based solvers and domain decomposition preconditioners with an algebraic coarse‐grid component that address these difficulties for adaptive hp approximations of linear elasticity with both homogeneous and inhomogeneous material properties. Our solvers are robust and efficient and place no restrictions on the mesh or partitioning. Copyright © 2003 John Wiley & Sons, Ltd.     

A finite deformation mortar contact formulation using a primal–dual active set strategy

In recent years, nonconforming domain decomposition techniques and, in particular, the mortar method have become popular in developing new contact algorithms. Here, we present an approach for 2D frictionless multibody contact based on a mortar formulation and using a primal–dual active set strategy for contact constraint enforcement. We consider linear and higher‐order (quadratic) interpolations throughout this work. So‐called dual Lagrange multipliers are introduced for the contact pressure but can be eliminated from the global system of equations by static condensation, thus avoiding an increase in system size. For this type of contact formulation, we provide a full linearization of both contact forces and normal (non‐penetration) and tangential (frictionless sliding) contact constraints in the finite deformation frame. The necessity of such a linearization in order to obtain a consistent Newton scheme is demonstrated. By further interpreting the active set search as a semi‐smooth Newton method, contact nonlinearity and geometrical and material nonlinearity can be resolved within one single iterative scheme. This yields a robust and highly efficient algorithm for frictionless finite deformation contact problems. Numerical examples illustrate the efficiency of our method and the high quality of results. Copyright © 2009 John Wiley & Sons, Ltd.     

ITERATIVE METHODS IN SOLVING NAVIER–STOKES EQUATIONS BY THE BOUNDARY ELEMENT METHOD

The solution of Navier–Stokes equations of time-dependent incompressible viscous fluid flow in planar geometry by the Boundary Domain Integral Method (BDIM) is discussed. The introduction of a subdomain technique to fluid flow problems is considered and improved in order to maintain the stability of BDIM. To avoid problems with flow kinematics computation in the sudomain mesh, a segmentation technique is proposed which combines the original BDIM with its subdomain variant and preserves its numerical stability. In order to reduce the computational cost of BDIM, which greatly depends on the solution of systems of linear equations, iterative methods are used. Conjugate gradient methods, conjugate gradients squared and an improved version of the biconjugate gradient method BiCGSTAB, together with the generalized minimal residual method, are used as iterative solvers. Different types of preconditioning, from simple Jacobi to incomplete LU factorization, are carried out and the performance of chosen iterative methods and preconditioners are reported. Test examples include backward facing step flow and flow through tubular heat exchangers. Test computation results show that BDIM is an accurate approximation technique which, together with the subdomain technique and powerful iterative solvers, can exhibit some significant savings in storage and CPU time requirements.     

A comparison of FE–BE coupling schemes for large‐scale problems with fluid–structure interaction

To predict the sound radiation of structures, both a structural problem and an acoustic problem have to be solved. In case of thin structures and dense fluids, a strong coupling scheme between the two problems is essential, since the feedback of the acoustic pressure onto the structure is not negligible. In this paper, the structural part is modeled with the finite element (FE) method. An interface to a commercial FE package is set up to import the structural matrices. The exterior acoustic problem is efficiently modeled with the Galerkin boundary element (BE) method. To overcome the well‐known drawback of fully populated system matrices, the fast multipole method is applied. Different coupling formulations are investigated. They are either based on the Burton–Miller approach or use a mortar coupling scheme. For all cases, iterative solvers with different preconditioners are used. The efficiency with respect to their memory consumption and computation time is compared for a simple model problem. At the end of the paper, a more complex structure is simulated. Copyright © 2008 John Wiley & Sons, Ltd.     

Efficient preconditioners for boundary element matrices based on grey‐box algebraic multigrid methods

This paper is concerned with the iterative solution of the boundary element equations arising from standard Galerkin boundary element discretizations of first‐kind boundary integral operators of positive and negative order. We construct efficient preconditioners on the basis of so‐called grey‐box algebraic multigrid methods that are well adapted to the treatment of boundary element matrices. In particular, the coarsening is based on an auxiliary matrix that represents the underlying topology in a certain sense. This auxiliary matrix is additionally used for the construction of the smoothers and the transfer operators. Finally, we present the results of some numerical studies that show the efficiency of the proposed algebraic multigrid preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

A dual mortar approach for 3D finite deformation contact with consistent linearization

In this paper, an approach for three‐dimensional frictionless contact based on a dual mortar formulation and using a primal–dual active set strategy for direct constraint enforcement is presented. We focus on linear shape functions, but briefly address higher order interpolation as well. The study builds on previous work by the authors for two‐dimensional problems. First and foremost, the ideas of a consistently linearized dual mortar scheme and of an interpretation of the active set search as a semi‐smooth Newton method are extended to the 3D case. This allows for solving all types of nonlinearities (i.e. geometrical, material and contact) within one single Newton scheme. Owing to the dual Lagrange multiplier approach employed, this advantage is not accompanied by an undesirable increase in system size as the Lagrange multipliers can be condensed from the global system of equations. Moreover, it is pointed out that the presented method does not make use of any regularization of contact constraints. Numerical examples illustrate the efficiency of our method and the high quality of results in 3D finite deformation contact analysis. Copyright © 2010 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.     

Iterative solvers for 3D linear and nonlinear elasticity problems: Displacement and mixed formulations

We present new iterative solvers for large‐scale linear algebraic systems arising from the finite element discretization of the elasticity equations. We focus on the numerical solution of 3D elasticity problems discretized by quadratic tetrahedral finite elements and we show that second‐order accuracy can be obtained at very small overcost with respect to first‐order (linear) elements. Different Krylov subspace methods are tested on various meshes including elements with small aspect ratio. We first construct a hierarchical preconditioner for the displacement formulation specifically designed for quadratic discretizations. We then develop efficient tools for preconditioning the 2 × 2 block symmetric indefinite linear system arising from mixed (displacement‐pressure) formulations. Finally, we present some numerical results to illustrate the potential of the proposed methods. Copyright © 2010 John Wiley & Sons, Ltd.     

A mortar method for energy‐momentum conserving schemes in frictionless dynamic contact problems

In the present work the mortar method is applied to planar large deformation contact problems without friction. In particular, the proposed form of the mortar contact constraints is invariant under translations and rotations. These invariance properties lay the foundation for the design of energy‐momentum time‐stepping schemes for contact–impact problems. The iterative solution procedure is embedded into an active set algorithm. Lagrange multipliers are used to enforce the mortar contact constraints. The solution of generalized saddle point systems is circumvented by applying the discrete null space method. Numerical examples demonstrate the robustness and enhanced numerical stability of the newly developed energy‐momentum scheme. Copyright © 2008 John Wiley & Sons, Ltd.     

Hybrid domain decomposition algorithms for compressible and almost incompressible elasticity

Overlapping Schwarz methods are considered for mixed finite element approximations of linear elasticity, with discontinuous pressure spaces, as well as for compressible elasticity approximated by standard conforming finite elements. The coarse components of the preconditioners are based on spaces, with a number of degrees of freedom per subdomain which are uniformly bounded, which are similar to those previously developed for scalar elliptic problems and domain decomposition methods of iterative substructuring type, i.e. methods based on nonoverlapping decompositions of the domain. The local components of the new preconditioners are based on solvers on a set of overlapping subdomains. In the current study, the dimension of the coarse spaces is smaller than in recently developed algorithms; in the compressible case all independent face degrees of freedom have been eliminated while in the almost incompressible case five out of six are not needed. In many cases, this will result in a reduction of the dimension of the coarse space by about one half compared with that of the algorithm previously considered. In addition, in spite of using overlapping subdomains to define the local components of the preconditioner, values of the residual and the approximate solution need only to be retained on the interface between the subdomains in the iteration of the new hybrid Schwarz algorithm. The use of discontinuous pressures makes it possible to work exclusively with symmetric, positive‐definite problems and the standard preconditioned conjugate gradient method. Bounds are established for the condition number of the preconditioned operators. The bound for the almost incompressible case grows in proportion to the square of the logarithm of the number of degrees of freedom of individual subdomains and the third power of the relative overlap between the overlapping subdomains, and it is independent of the Poisson ratio as well as jumps in the Lamé parameters across the interface between the subdomains. Numerical results illustrate the findings. Copyright © 2009 John Wiley & Sons, Ltd.     

Efficient numerical methods for the large‐scale,parallel solution of elastoplastic contact problems

Quasi‐static elastoplastic contact problems are ubiquitous in many industrial processes and other contexts, and their numerical simulation is consequently of great interest in accurately describing and optimizing production processes. The key component in these simulations is the solution of a single load step of a time iteration. From a mathematical perspective, the problems to be solved in each time step are characterized by the difficulties of variational inequalities for both the plastic behavior and the contact problem. Computationally, they also often lead to very large problems. In this paper, we present and evaluate a complete set of methods that are (1) designed to work well together and (2) allow for the efficient solution of such problems. In particular, we use adaptive finite element meshes with linear and quadratic elements, a Newton linearization of the plasticity, active set methods for the contact problem, and multigrid‐preconditioned linear solvers. Through a sequence of numerical experiments, we show the performance of these methods. This includes highly accurate solutions of a three‐dimensional benchmark problem and scaling our methods in parallel to 1024 cores and more than a billion unknowns. Copyright © 2015 John Wiley & Sons, Ltd.     

Parallel block-preconditioned monolithic solvers for fluid-structure interaction problems

In this work, we consider the solution of fluid-structure interaction (FSI) problems using a monolithic approach for the coupling between fluid and solid subproblems. The coupling of both equations is realized by means of the arbitrary Lagrangian-Eulerian framework and a nonlinear harmonic mesh motion model. Monolithic approaches require the solution of large ill-conditioned linear systems of algebraic equations at every Newton step. Direct solvers tend to use too much memory even for a relatively small number of degrees of freedom and, in addition, exhibit superlinear growth in arithmetic complexity. Thus, iterative solvers are the only viable option. To ensure convergence of iterative methods within a reasonable amount of iterations, good and, at the same time, cheap preconditioners have to be developed. We study physics-based block preconditioners, which are derived from the block-LDU factorization of the FSI Jacobian, and their performance on distributed memory parallel computers in terms of two- and three-dimensional test cases permitting large deformations.     

A multiscale large time increment/FAS algorithm with time‐space model reduction for frictional contact problems

A multiscale strategy using model reduction for frictional contact computation is presented. This new approach aims to improve computation time of finite element simulations involving frictional contact between linear and elastic bodies. This strategy is based on a combination between the LATIN (LArge Time INcrement) method and the FAS multigrid solver. The LATIN method is an iterative solver operating on the whole time‐space domain. Applying an a posteriori analysis on solutions of different frictional contact problems shows a great potential as far as reducibility for frictional contact problems is concerned. Time‐space vectors forming the so‐called reduced basis depict particular scales of the problem. It becomes easy to make analogies with multigrid method to take full advantage of multiscale information. Copyright © 2013 John Wiley & Sons, Ltd.     

An algebraic multigrid approach to solve extended finite element method based fracture problems

This article proposes an algebraic multigrid (AMG) approach to solve linear systems arising from applications where strong discontinuities are modeled by the extended finite element method. The application of AMG methods promises optimal scalability for solving large linear systems. However, the straightforward (or ‘black‐box’) use of existing AMG techniques for extended finite element method problems is often problematic. In this paper, we highlight the reasons for this behavior and propose a relatively simple adaptation that allows one to leverage existing AMG software mostly unchanged. Numerical tests demonstrate that optimal iterative convergence rates can be attained that are comparable with AMG convergence rates associated with linear systems for standard finite element approximations without discontinuities. Published 2012. This article is a US Government work and is in the public domain in the USA.