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.     

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.     

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.     

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.     

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.     

Multi‐time‐step and two‐scale domain decomposition method for non‐linear structural dynamics

In this paper we propose a method to improve the means of taking into account the specific time‐scale and space‐scale characteristics in time‐dependent non‐linear problems. This method enables the use of arbitrary time steps in each subdomain: these can be coupled by prescribing continuous velocities at the interfaces, which are modelled using a dual Schur formulation. For certain subdomains, in space, we adopt a two‐scale resolution technique inspired by the multigrid methods in order to obtain the part of the solution related to small variation lengths on a refined scale and the part corresponding to large variation lengths on a coarse scale. For non‐linear problems, we propose an algorithm with a single iteration level to deal with both the non‐linear equilibrium and the two space scales thanks to a two‐grid method in which the relaxation steps are performed using a non‐linear, preconditioned conjugate gradient algorithm. Finally, we present an example which demonstrates the feasibility of the method. Copyright © 2003 John Wiley & Sons, Ltd.     

FETI‐DP,BDDC, and block Cholesky methods

The FETI‐DP and BDDC algorithms are reformulated using Block Cholesky factorizations, an approach which can provide a useful framework for the design of domain decomposition algorithms for solving symmetric positive definite linear system of equations. Instead of introducing Lagrange multipliers to enforce the coarse level, primal continuity constraints in these algorithms, a change of variables is used such that each primal constraint corresponds to an explicit degree of freedom. With the new formulation of these algorithms, a simplified proof is provided that the spectra of a pair of FETI‐DP and BDDC algorithms, with the same set of primal constraints, are essentially the same. Numerical experiments for a two‐dimensional Laplace's equation also confirm this result. Copyright © 2005 John Wiley & Sons, Ltd.     

Domain decomposition methods for parallel solution of shape sensitivity analysis problems

This paper presents the implementation of advanced domain decomposition techniques for parallel solution of large‐scale shape sensitivity analysis problems. The methods presented in this study are based on the FETI method proposed by Farhat and Roux which is a dual domain decomposition implementation. Two variants of the basic FETI method have been implemented in this study: (i) FETI‐1 where the rigid‐body modes of the floating subdomains are computed explicitly. (ii) FETI‐2 where the local problem at each subdomain is solved by the PCG method and the rigid‐body modes are computed explicitly. A two‐level iterative method is proposed particularly tailored to solve re‐analysis type of problems, where the dual domain decomposition method is incorporated in the preconditioning step of a subdomain global PCG implementation. The superiority of this two‐level iterative solver is demonstrated with a number of numerical tests in serial as well as in parallel computing environments. Copyright © 1999 John Wiley & Sons, Ltd.     

A FETI‐based domain decomposition technique for time‐dependent first‐order systems based on a DAE approach

We present a novel partitioned coupling algorithm to solve first‐order time‐dependent non‐linear problems (e.g. transient heat conduction). The spatial domain is partitioned into a set of totally disconnected subdomains. The continuity conditions at the interface are modeled using a dual Schur formulation where the Lagrange multipliers represent the interface fluxes (or the reaction forces) that are required to maintain the continuity conditions. The interface equations along with the subdomain equations lead to a system of differential algebraic equations (DAEs). For the resulting equations a numerical algorithm is developed, which includes choosing appropriate constraint stabilization techniques. The algorithm first solves for the interface Lagrange multipliers, which are subsequently used to advance the solution in the subdomains. The proposed coupling algorithm enables arbitrary numeric schemes to be coupled with different time steps (i.e. it allows subcycling) in each subdomain. This implies that existing software and numerical techniques can be used to solve each subdomain separately. The coupling algorithm can also be applied to multiple subdomains and is suitable for parallel computers. We present examples showing the feasibility of the proposed coupling algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

Multi‐time‐step explicit–implicit method for non‐linear structural dynamics

We present a method with domain decomposition to solve time‐dependent non‐linear problems. This method enables arbitrary numeric schemes of the Newmark family to be coupled with different time steps in each subdomain: this coupling is achieved by prescribing continuity of velocities at the interface. We are more specifically interested in the coupling of implicit/explicit numeric schemes taking into account material and geometric non‐linearities. The interfaces are modelled using a dual Schur formulation where the Lagrange multipliers represent the interfacial forces. Unlike the continuous formulation, the discretized formulation of the dynamic problem is unable to verify simultaneously the continuity of displacements, velocities and accelerations at the interfaces. We show that, within the framework of the Newmark family of numeric schemes, continuity of velocities at the interfaces enables the definition of an algorithm which is stable for all cases envisaged. To prove this stability, we use an energy method, i.e. a global method over the whole time interval, in order to verify the algorithms properties. Then, we propose to extend this to non‐linear situations in the following cases: implicit linear/explicit non‐linear, explicit non‐linear/explicit non‐linear and implicit non‐linear/explicit non‐linear. Finally, we present some examples showing the feasibility of the method. Copyright © 2001 John Wiley & Sons, Ltd.     

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

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

A parallel computational method in steady power‐law creep

A new approach to parallelization of materially non‐linear problems in solid mechanics is developed. It is based on approximating generalized models of subdomains. The procedure does not retain the same substructuring technique used in a linear version. The convergence proof of the single‐ and multilevel‐domain decomposition algorithms uses the principle of minimum potential energy dissipation and investigated properties of the substructural models. The high efficiency of the approach introduced is shown through the study of several examples. The method developed in this paper for steady creep can be used without modification to solve non‐linear elasticity problems and, at active loading, plasticity problems for bodies of the power‐law strain–stress diagrams. Copyright © 2001 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.     

Numerical solution of non‐linear Klein–Gordon equations by variational iteration method

In this paper, numerical solution of non‐linear Klein–Gordon equations with power law non‐linearities are obtained by the new application of He's variational iteration method. Numerical illustrations that include non‐linear Klein–Gordon equations and non‐linear partial differential equations are investigated to show the pertinent features of the technique. Copyright © 2006 John Wiley & Sons, Ltd.     

Efficient non‐linear model reduction via a least‐squares Petrov–Galerkin projection and compressive tensor approximations

A Petrov–Galerkin projection method is proposed for reducing the dimension of a discrete non‐linear static or dynamic computational model in view of enabling its processing in real time. The right reduced‐order basis is chosen to be invariant and is constructed using the Proper Orthogonal Decomposition method. The left reduced‐order basis is selected to minimize the two‐norm of the residual arising at each Newton iteration. Thus, this basis is iteration‐dependent, enables capturing of non‐linearities, and leads to the globally convergent Gauss–Newton method. To avoid the significant computational cost of assembling the reduced‐order operators, the residual and action of the Jacobian on the right reduced‐order basis are each approximated by the product of an invariant, large‐scale matrix, and an iteration‐dependent, smaller one. The invariant matrix is computed using a data compression procedure that meets proposed consistency requirements. The iteration‐dependent matrix is computed to enable the least‐squares reconstruction of some entries of the approximated quantities. The results obtained for the solution of a turbulent flow problem and several non‐linear structural dynamics problems highlight the merit of the proposed consistency requirements. They also demonstrate the potential of this method to significantly reduce the computational cost associated with high‐dimensional non‐linear models while retaining their accuracy. Copyright © 2010 John Wiley & Sons, Ltd.     

A parallel hp‐FEM infrastructure for three‐dimensional structural acoustics

This paper describes a parallel three‐dimensional numerical infrastructure for the solution of a wide range of time‐harmonic problems in structural acoustics and vibration. High accuracy and rate of error‐convergence, in the mid‐frequency regime,is achieved by the use of hp‐finite and infinite element approximations. The infrastructure supports parallel computation in both single and multi‐frequency settings. Multi‐frequency solves utilize concurrent factoring of the frequency‐dependent linear algebraic systems and are naturally scalable. Scalability of large‐scale single‐frequency problems is realized by using FETI‐DP—an iterative domain‐decomposition scheme. Numerical examples are presented to cover applications in vibratory response of fluid‐filled elastic structures as well as radiation and scattering from elastic structures submerged in an infinite acoustic medium. We demonstrate both the numerical accuracy as well as parallel scalability of the infrastructure in terms of problem parameters that include wavenumber and number of frequencies, polynomial degree of finite/infinite element approximations as well as the number of processors. Scalability and accuracy is evaluated for both single and multiple frequency sweeps on four high‐performance parallel computing platforms: SGI Altix, SGI Origin, IBM p690 SP and Linux‐cluster. Results show good performance on shared as well as distributed‐memory architecture. Copyright © 2006 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.