A two‐level nonoverlapping Schwarz algorithm for the Stokes problem without primal pressure unknowns

A two‐level nonoverlapping Schwarz algorithm is developed for the Stokes problem. The main feature of the algorithm is that a mixed problem with both velocity and pressure unknowns is solved with a balancing domain decomposition by constraints (BDDC)‐type preconditioner, which consists of solving local Stokes problems and one global coarse problem related to only primal velocity unknowns. Our preconditioner allows to use a smaller set of primal velocity unknowns than other BDDC preconditioners without much concern on certain flux conditions on the subdomain boundaries and the inf–sup stability of the coarse problem. In the two‐dimensional case, velocity unknowns at subdomain corners are selected as the primal unknowns. In addition to them, averages of each velocity component across common faces are employed as the primal unknowns for the three‐dimensional case. By using its close connection to the Dual–primal finite element tearing and interconnecting (FETI‐DP algorithm) (SIAM J Sci Comput 2010; 32 : 3301–3322; SIAM J Numer Anal 2010; 47 : 4142–4162], it is shown that the resulting matrix of our algorithm has the same eigenvalues as the FETI‐DP algorithm except zero and one. The maximum eigenvalue is determined by H/h, the number of elements across each subdomains, and the minimum eigenvalue is bounded below by a constant, which does not depend on any mesh parameters. Convergence of the method is analyzed and numerical results are included. Copyright © 2011 John Wiley & Sons, Ltd.     

A unified dual‐primal finite element tearing and interconnecting approach for incompressible Stokes equations

A unified framework of dual‐primal finite element tearing and interconnecting (FETI‐DP) algorithms is proposed for solving the system of linear equations arising from the mixed finite element approximation of incompressible Stokes equations. A distinctive feature of this framework is that it allows using both continuous and discontinuous pressures in the algorithm, whereas previous FETI‐DP methods only apply to discontinuous pressures. A preconditioned conjugate gradient method is used in the algorithm with either a lumped or a Dirichlet preconditioner, and scalable convergence rates are proved. This framework is also used to describe several previously developed FETI‐DP algorithms and greatly simplifies their analysis. Numerical experiments of solving a two‐dimensional incompressible Stokes problem demonstrate the performances of the discussed FETI‐DP algorithms represented under the same framework.Copyright © 2012 John Wiley & Sons, Ltd.     

FETI‐DP: a dual–primal unified FETI method—part I: A faster alternative to the two‐level FETI method

The FETI method and its two‐level extension (FETI‐2) are two numerically scalable domain decomposition methods with Lagrange multipliers for the iterative solution of second‐order solid mechanics and fourth‐order beam, plate and shell structural problems, respectively.The FETI‐2 method distinguishes itself from the basic or one‐level FETI method by a second set of Lagrange multipliers that are introduced at the subdomain cross‐points to enforce at each iteration the exact continuity of a subset of the displacement field at these specific locations. In this paper, we present a dual–primal formulation of the FETI‐2 concept that eliminates the need for that second set of Lagrange multipliers, and unifies all previously developed one‐level and two‐level FETI algorithms into a single dual–primal FETI‐DP method. We show that this new FETI‐DP method is numerically scalable for both second‐order and fourth‐order problems. We also show that it is more robust and more computationally efficient than existing FETI solvers, particularly when the number of subdomains and/or processors is very large. Copyright © 2001 John Wiley & Sons, Ltd.     

Inexact FETI‐DP methods

Inexact FETI‐DP domain decomposition methods are considered. Preconditioners based on formulations of FETI‐DP as a saddle point problem are used which allow for an inexact solution of the coarse problem. A positive definite reformulation of the preconditioned saddle point problem, which also allows for approximate solvers, is considered as well. In the formulation that iterates on the original FETI‐DP saddle point system, it is also possible to solve the local Neumann subdomain problems inexactly. Given good approximate solvers for the local and coarse problems, convergence bounds of the same quality as for the standard FETI‐DP methods are obtained. Numerical experiments which compare the convergence of the inexact methods with that of standard FETI‐DP are shown for 2D and 3D elasticity using GMRES and CG as Krylov space methods. Based on parallel computations, a comparison of one variant of the inexact FETI‐DP algorithms and the standard FETI‐DP method is carried out and similar parallel performance is achieved. Parallel scalability of the inexact variant is also demonstrated. It is shown that for a very large number of subdomains and a very large coarse problem, the inexact method can be superior. Copyright © 2006 John Wiley & Sons, Ltd.     

A dual‐primal FETI method for solving a class of fluid–structure interaction problems in the frequency domain

The dual‐primal finite element tearing and interconnecting method (FETI‐DP) is extended to systems of linear equations arising from a finite element discretization for a class of fluid–structure interaction problems in the frequency domain. A preconditioned generalized minimal residual method is used to solve the linear equations for the Lagrange multipliers introduced on the subdomain boundaries to enforce continuity of the solution. The coupling between the fluid and the structure on the fluid–structure interface requires an appropriate choice of coarse level degrees of freedom in the FETI‐DP algorithm to achieve fast convergence. Several choices are proposed and tested by numerical experiments on three‐dimensional fluid–structure interaction problems in the mid‐frequency regime that demonstrate the greatly improved performance of the proposed algorithm over the standard FETI‐DP method. Copyright © 2011 John Wiley & Sons, Ltd.     

A fast implementation of the FETI‐DP method: FETI‐DP‐RBS‐LNA and applications on large scale problems with localized non‐linearities

As parallel and distributed computing gradually becomes the computing standard for large scale problems, the domain decomposition method (DD) has received growing attention since it provides a natural basis for splitting a large problem into many small problems, which can be submitted to individual computing nodes and processed in a parallel fashion. This approach not only provides a method to solve large scale problems that are not solvable on a single computer by using direct sparse solvers but also gives a flexible solution to deal with large scale problems with localized non‐linearities. When some parts of the structure are modified, only the corresponding subdomains and the interface equation that connects all the subdomains need to be recomputed. In this paper, the dual–primal finite element tearing and interconnecting method (FETI‐DP) is carefully investigated, and a reduced back‐substitution (RBS) algorithm is proposed to accelerate the time‐consuming preconditioned conjugate gradient (PCG) iterations involved in the interface problems. Linear–non‐linear analysis (LNA) is also adopted for large scale problems with localized non‐linearities based on subdomain linear–non‐linear identification criteria. This combined approach is named as the FETI‐DP‐RBS‐LNA algorithm and demonstrated on the mechanical analyses of a welding problem. Serial CPU costs of this algorithm are measured at each solution stage and compared with that from the IBM Watson direct sparse solver and the FETI‐DP method. The results demonstrate the effectiveness of the proposed computational approach for simulating welding problems, which is representative of a large class of three‐dimensional large scale problems with localized non‐linearities. Copyright © 2005 John Wiley & Sons, Ltd.     

The derived-vector space framework and four general purposes massively parallel DDM algorithms

Ideally, DDMs seek what we call the DDM-paradigm: “constructing the global solution by solving local problems, exclusively”. To achieve it, it is essential to disconnect the subdomain-problems. In FETI-DP such disconnection is achieved by formulating the method in a product function-space that contains discontinuous functions. However, FETI-DP uses an indirect formulation based on Lagrange-multipliers. BDDC uses instead a more direct formulation, but does not work directly in a space of discontinuous functions, either. Another fact difficult to overcome is: at present competitive algorithms need to incorporate constraints that prevent full disconnection of the subdomains. This paper is devoted to explain a direct (primal) approach to DDMs in which all the numerical work is done in a product-space (the derived-vector space), which supplies a unified setting for non-overlapping DDMs and can be used to formulate and discuss in a general and systematic manner the theory of DDMs for non-symmetric problems. Furthermore, in this realm four general-purposes preconditioned algorithms with constraints applicable to non-symmetric matrices, which achieve the DDM-paradigm, have been obtained. Two of them have been identified as DVS-versions of BDDC and FETI-DP. The uniformity of the matrix-formulas expressing such algorithms should be highlighted.     

A simple explicit–implicit finite element tearing and interconnecting transient analysis algorithm

A simple explicit–implicit finite element tearing and interconnecting (FETI) algorithm (AFETI‐EI algorithm) is presented for partitioned transient analysis of linear structural systems. The present algorithm employs two decompositions. First, the total system is partitioned via spatial or domain decomposition to obtain the governing equations of motions for each partitioned domain. Second, for each partitioned subsystem, the governing equations are modally decomposed into the rigid‐body and deformational equations. The resulting rigid‐body equations are integrated by an explicit integrator, for its stability is not affected by step‐size restriction on account of zero‐frequency contents (ω = 0). The modally decomposed partitioned deformation equations of motion are integrated by an unconditionally stable implicit integration algorithm. It is shown that the present AFETI‐EI algorithm exhibits unconditional stability and that the resulting interface problem possesses the same solution matrix profile as the basic FETI static problems. The present simple dynamic algorithm, as expected, falls short of the performance of the FETI‐DP but offers a similar performance of implicit two‐level FETI‐D algorithm with a much cheaper coarse solver; hence, its simplicity may offer relatively easy means for conducting parallel analysis of both static and dynamic problems by employing the same basic scalable FETI solver, especially for research‐mode numerical experiments. Copyright © 2011 John Wiley & Sons, Ltd.     

A FETI‐DP method for the parallel iterative solution of indefinite and complex‐valued solid and shell vibration problems

The dual‐primal finite element tearing and interconnecting (FETI‐DP) domain decomposition method (DDM) is extended to address the iterative solution of a class of indefinite problems of the form ( K ?σ² M ) u = f , and a class of complex problems of the form ( K ?σ² M +iσ D ) u = f , where K , M , and D are three real symmetric matrices arising from the finite element discretization of solid and shell dynamic problems, i is the imaginary complex number, and σ is a real positive number. A key component of this extension is a new coarse problem based on the free‐space solutions of Navier's equations of motion. These solutions are waves, and therefore the resulting DDM is reminiscent of the FETI‐H method. For this reason, it is named here the FETI‐DPH method. For a practically large σ range, FETI‐DPH is shown numerically to be scalable with respect to all of the problem size, substructure size, and number of substructures. The CPU performance of this iterative solver is illustrated on a 40‐processor computing system with the parallel solution, for various σ ranges, of several large‐scale, indefinite, or complex‐valued systems of equations associated with shifted eigenvalue and forced frequency response structural dynamics problems. Copyright © 2005 John Wiley & Sons, Ltd.     

Three‐level BDDC in two dimensions

Balancing Domain Decomposition by Constraints (BDDC) methods are non‐overlapping iterative substructuring domain decomposition methods for the solution of large sparse linear algebraic systems arising from discretization of elliptic boundary value problems. They are similar to the balancing Neumann–Neumann algorithm. However, in BDDC methods, a small number of continuity constraints are enforced across the interface, and these constraints form a new coarse, global component. An important advantage of using such constraints is that the Schur complements that arise in the computation will all be strictly positive definite. The matrix of the coarse problem is generated and factored by direct solvers at the beginning of the computation. However, this problem can ultimately become a bottleneck, if the number of subdomains is very large. In this paper, two three‐level BDDC methods are introduced for solving the coarse problem approximately in two‐dimensional space, while still maintaining a good convergence rate. Estimates of the condition numbers are provided for the two three‐level BDDC methods and numerical experiments are also discussed. Copyright © 2006 John Wiley & Sons, Ltd.     

Extended preconditioners for the FETI method applied to constrained problems

An efficient and simple approach for handling linear multipoint constraints in a class of substructure‐based solvers, namely the finite element tearing and interconnecting (FETI) method, is proposed. Previously, it was argued that multipoint constraints should be handled in FETI by adding a second level iteration on a coarse grid such that the FETI iterates satisfy the multipoint constraints exactly. The procedure presented here does not require an additional coarse grid but instead takes account of the multipoint constraints in the preconditioning step. The preconditioning strategy is shown to be mechanically consistent and to incur only a small additional computational cost. This strategy is simpler and computationally less expensive than the two‐level FETI procedure. Its numerical scalability even for highly heterogeneous problems is demonstrated in several test examples. Copyright © 2002 John Wiley & Sons, Ltd.     

A domain decomposition method for discontinuous Galerkin discretizations of Helmholtz problems with plane waves and Lagrange multipliers

A nonoverlapping domain decomposition (DD) method is proposed for the iterative solution of systems of equations arising from the discretization of Helmholtz problems by the discontinuous enrichment method. This discretization method is a discontinuous Galerkin finite element method with plane wave basis functions for approximating locally the solution and dual Lagrange multipliers for weakly enforcing its continuity over the element interfaces. The primal subdomain degrees of freedom are eliminated by local static condensations to obtain an algebraic system of equations formulated in terms of the interface Lagrange multipliers only. As in the FETI‐H and FETI‐DPH DD methods for continuous Galerkin discretizations, this system of Lagrange multipliers is iteratively solved by a Krylov method equipped with both a local preconditioner based on subdomain data, and a global one using a coarse space. Numerical experiments performed for two‐ and three‐dimensional acoustic scattering problems suggest that the proposed DD‐based iterative solver is scalable with respect to both the size of the global problem and the number of subdomains. Copyright © 2009 John Wiley & Sons, Ltd.     

Enhanced balancing Neumann–Neumann preconditioning in computational fluid and solid mechanics

In this work, we propose an enhanced implementation of balancing Neumann–Neumann (BNN) preconditioning together with a detailed numerical comparison against the balancing domain decomposition by constraints (BDDC) preconditioner. As model problems, we consider the Poisson and linear elasticity problems. On one hand, we propose a novel way to deal with singular matrices and pseudo‐inverses appearing in local solvers. It is based on a kernel identification strategy that allows us to efficiently compute the action of the pseudo‐inverse via local indefinite solvers. We further show how, identifying a minimum set of degrees of freedom to be fixed, an equivalent definite system can be solved instead, even in the elastic case. On the other hand, we propose a simple implementation of the algorithm that reduces the number of Dirichlet solvers to only one per iteration, leading to similar computational cost as additive methods. After these improvements of the BNN preconditioned conjugate gradient algorithm, we compare its performance against that of the BDDC preconditioners on a pair of large‐scale distributed‐memory platforms. The enhanced BNN method is a competitive preconditioner for three‐dimensional Poisson and elasticity problems and outperforms the BDDC method in many cases. Copyright © 2013 John Wiley & Sons, Ltd.     

Theoretical comparison of the FETI and algebraically partitioned FETI methods,and performance comparisons with a direct sparse solver

In this paper, we prove that the Algebraic A‐FETI method corresponds to one particular instance of the original one‐level FETI method. We also report on performance comparisons on an Origin 2000 between the one‐ and two‐level FETI methods and an optimized sparse solver, for two industrial applications: the stress analysis of a thin shell structure, and that of a three‐dimensional structure modelled by solid elements. These comparisons suggest that for topologically two‐dimensional problems, sparse solvers are effective when the number of processors is relatively small. They also suggest that for three‐dimensional applications, scalable domain decomposition methods such as FETI deliver a superior performance on both sequential and parallel hardware configurations. Copyright © 1999 John Wiley & Sons, Ltd.     

A unified framework for accelerating the convergence of iterative substructuring methods with Lagrange multipliers

The FETI algorithms are a family of numerically scalable substructuring methods with Lagrange multipliers that have been designed for solving iteratively large-scale systems of equations arising from the finite element discretization of structural engineering, solid mechanics, and structural dynamics problems. In this paper, we present a unified framework that simplifies the interpretation of several of the previously presented FETI concepts. This framework has enabled the improvement of the robustness and performance of the transient FETI method, and the design of a new family of coarse operators for iterative substructuring algorithms with Lagrange multipliers. We report on both of these new developments, discuss their impact on the iterative solution of large-scale finite element systems of equations by the FETI method, and illustrate them with a few static and dynamic structural analyses on an IBM SP2 parallel processor. © 1998 John Wiley & Sons, Ltd.     

Scalable TFETI algorithm for the solution of multibody contact problems of elasticity

A Total FETI (TFETI)‐based domain decomposition algorithm with preconditioning by a natural coarse grid of the rigid body motions is adapted to the solution of multibody contact problems of elasticity in 2D and 3D and proved to be scalable. The algorithm finds an approximate solution at the cost asymptotically proportional to the number of variables provided the ratio of the decomposition parameter and the discretization parameter is bounded. The analysis is based on the classical results by Farhat, Mandel, and Roux on scalability of FETI with a natural coarse grid for linear problems and on our development of optimal quadratic programming algorithms for bound and equality constrained problems. The algorithm preserves parallel scalability of the classical FETI method. Both theoretical results and numerical experiments indicate a high efficiency of our algorithm. In addition, its performance is illustrated on a real‐world problem of analysis of the ball bearing. Copyright © 2009 John Wiley & Sons, Ltd.     

The nsBETI method: an extension of the FETI method to non‐symmetrical BEM‐FEM coupled problems

The finite element tearing and interconnecting (FETI) method is recognized as an effective domain decomposition tool to achieve scalability in the solution of partitioned second‐order elasticity problems. In the boundary element tearing and interconnecting (BETI) method, a direct extension of the FETI algorithm to the BEM, the symmetric Galerkin BEM formulation, is used to obtain symmetric system matrices, making possible to apply the same FETI conjugate gradient solver. In this work, we propose a new BETI variant labeled nsBETI that allows to couple substructures modeled with the FEM and/or non‐symmetrical BEM formulations. The method connects non‐matching BEM and FEM subdomains using localized Lagrange multipliers and solves the associated non‐symmetrical flexibility equations with a Bi‐CGstab iterative algorithm. Scalability issues of nsBETI in BEM–BEM and combined BEM–FEM coupled problems are also investigated. Copyright © 2012 John Wiley & Sons, Ltd.     

Simultaneous FETI and block FETI: Robust domain decomposition with multiple search directions

Domain decomposition methods often exhibit very poor performance when applied to engineering problems with large heterogeneities. In particular, for heterogeneities along domain interfaces, the iterative techniques to solve the interface problem are lacking an efficient preconditioner. Recently, a robust approach, named finite element tearing and interconnection (FETI)–generalized eigenvalues in the overlaps (Geneo), was proposed where troublesome modes are precomputed and deflated from the interface problem. The cost of the FETI–Geneo is, however, high. We propose in this paper techniques that share similar ideas with FETI–Geneo but where no preprocessing is needed and that can be easily and efficiently implemented as an alternative to standard domain decomposition methods. In the block iterative approaches presented in this paper, the search space at every iteration on the interface problem contains as many directions as there are domains in the decomposition. Those search directions originate either from the domain‐wise preconditioner (in the simultaneous FETI method) or from the block structure of the right‐hand side of the interface problem (block FETI). We show on two‐dimensional structural examples that both methods are robust and provide good convergence in the presence of high heterogeneities, even when the interface is jagged or when the domains have a bad aspect ratio. The simultaneous FETI was also efficiently implemented in an optimized parallel code and exhibited excellent performance compared with the regular FETI method. Copyright © 2015 John Wiley & Sons, Ltd.     

On the formulation of closest‐point projection algorithms in elastoplasticity—part II: Globally convergent schemes

This paper presents the formulation of numerical algorithms for the solution of the closest‐point projection equations that appear in typical implementations of return mapping algorithms in elastoplasticity. The main motivation behind this work is to avoid the poor global convergence properties of a straight application of a Newton scheme in the solution of these equations, the so‐called Newton‐CPPM. The mathematical structure behind the closest‐point projection equations identified in Part I of this work delineates clearly different strategies for the successful solution of these equations. In particular, primal and dual closest‐point projection algorithms are proposed, in non‐augmented and augmented Lagrangian versions for the imposition of the consistency condition. The primal algorithms involve a direct solution of the original closest‐point projection equations, whereas the dual schemes involve a two‐level structure by which the original system of equations is staggered, with the imposition of the consistency condition driving alone the iterative process. Newton schemes in combination with appropriate line search strategies are considered, resulting in the desired asymptotically quadratic local rate of convergence and the sought global convergence character of the iterative schemes. These properties, together with the computational performance of the different schemes, are evaluated through representative numerical examples involving different models of finite‐strain plasticity. In particular, the avoidance of the large regions of no convergence in the trial state observed in the standard Newton‐CPPM is clearly illustrated. Copyright © 2001 John Wiley & Sons, Ltd.