FETI-1 Introduction

FETI-1 or simply FETI (Finite Element Tearing & Interconnecting) is a DDM method introduced by Farhat et al. (1991). It is the first implementation of a family of FETI methods, which use Lagrange multipliers to describe the forces between the subdomains and define the interface problem in terms of those. The Lagrange multipliers are dual quantities (e.g. forces in elasticity problems, while displacements are primal), these methods are often called dual. Later, other dual DDMs were developed as simpler and in many cases more efficient, alternatives.

Before continuing to the theory presented next, it is recommended to read the general DDM chapter. For a more detailed description of FETI-1, see the original publication.

FETI-1 Theory

Lagrange multipliers & dual DOFs

Lagrange multipliers

In FETI-1 method, the domain is divided into disconnected subdomains as in the above figure and the continuity between them is retained by enforcing equal displacements for instances of the same boundary DOF (degree of freedom). E.g. if subdomains s=1,2 share the same boundary dof k:

$\begin{bmatrix} 1 & -1 \end{bmatrix} \cdot \begin{bmatrix} u_k^{(1)} \\ u_k^{(2)} \end{bmatrix} = 0$

By gathering the 1, -1 and 0 coefficients in a signed boolean matrix B^s for all boundary DOFs of a subdomain s, we get series of continuity equations:

$\sum_{s=1}^{N_s} \mathbf{B}^s \cdot \mathbf{u}^s = \mathbf{0}$

To solve the initial linear system in the presence of these constraints, we apply Lagrange multipliers at boundary DOFs. These are dual quantities and can be viewed as forces, while displacements are primal quantities. The resulting linear system is written as:

$\begin{bmatrix} \mathbf{K}^e & (\mathbf{B}^e)^{T} \\ \mathbf{B}^e & \mathbf{0} \end{bmatrix} \cdot \begin{bmatrix} \mathbf{u}^e \\ \mathbf{\lambda} \end{bmatrix} = \begin{bmatrix} \mathbf{f}^e \\ \mathbf{0} \end{bmatrix}$

where the superscript ^e denotes a matrix/vector where each subdomain matrix/vector contribution (with superscript ^s) is placed one after the other, without any overlap.

Floating subdomains

A subdomain of FETI-1 can be “floating”, meaning there are not enough constrained DOFs and its stiffness matrix K^s is singular. To overcome this, we use a generalized inverse (K^s)^* and a normalized basis for its nullspace R^s, which corresponds to the rigid body motions of the floating subdomain.

$\left( \mathbf{K}^{s} \right)^{+} = \begin{bmatrix} \left( \mathbf{K}_{11}^{s} \right)^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{bmatrix}$

$\mathbf{R}^{s} = \begin{bmatrix} \left( \mathbf{K}_{11}^{s} \right)^{-1} \cdot \mathbf{K}_{12}^s \\ \mathbf{I} \end{bmatrix}$

where the subscripts 1/2 denote linearly independent/dependent rows and columns, respectively. If the subdomain has sufficient constraints then R^s is empty and (K^s)^* = (K^s)^-1.

Interface problem

The interface problem of FETI-1 is as follows:

$\begin{bmatrix} \mathbf{F}_{I} & -\mathbf{G}_{I} \\ -\mathbf{G}_{I}^{T} & \mathbf{0} \end{bmatrix} \cdot \begin{bmatrix} \mathbf{\lambda} \\ \mathbf{a} \end{bmatrix} = \begin{bmatrix} \mathbf{d} \\ -\mathbf{e} \end{bmatrix}$

where a expresses linear combinations of the normalized rigid body motions in R, F_I is the flexibility matrix, G aggregates the rigid body motions, d are the displacements due to applied forces (boundary conditions and loading) and e is the work of rigid body motions due to these applied forces:

$\mathbf{F}_{I} = \sum_{s = 1}^{N_{s}} \mathbf{F}_{I}^{s} = \sum_{s = 1}^{N_{s}} \mathbf{B}^{s} \cdot (\mathbf{K}^{s})^{+} \cdot (\mathbf{B}^{s})^{T}$

$\mathbf{d} = \sum_{s = 1}^{d_{s}} \mathbf{F}_{I}^{s} = \sum_{s = 1}^{N_{s}} \mathbf{B}^{s} \cdot (\mathbf{K}^{s})^{+} \cdot \mathbf{f}^{s}$

$\mathbf{G}_{I} = \begin{bmatrix} \mathbf{B}^{(1)} \cdot \mathbf{R}^{(1)} & \mathbf{B}^{(2)} \cdot \mathbf{R}^{(2)} & \cdots & \mathbf{B}^{(N_s)} \cdot \mathbf{R}^{(N_s)} \end{bmatrix}$

The linear system written above is not symmetric positive definite. To solve it using the preconditioned conjugate gradient (PCG) method, we must project it into another space using a projection matrix P and then solve the final linear system of the interface problem:

$\mathbf{P}^{T}\mathbf{F}_{I}\mathbf{P}\mathbf{\bar{\lambda}} = \mathbf{P}^{T} (\mathbf{d} - \mathbf{F}_{I}\mathbf{P}\mathbf{\lambda_{0}})$

where

$\mathbf{P} = \mathbf{I} - \mathbf{G}_{I}(\mathbf{G}_{I}^{T}\mathbf{G}_{I})^{-1}\mathbf{G}_{I}^{T}$

$\mathbf{\lambda}_{0} = \mathbf{G}_{I} (\mathbf{G}_{I}^{T}\mathbf{G}_{I})^{-1}\mathbf{e}$

$\mathbf{\lambda} = \mathbf{\lambda}_{0} + \mathbf{P} \bar{\mathbf{\lambda}}$

$\mathbf{a} = (\mathbf{G}_{I}^{T}\mathbf{G}_{I})^{-1} \mathbf{G}_{I}^{T} (\mathbf{F}_I\mathbf{\lambda} - \mathbf{d})$

Finally we calculate the displacements depending on if the subdomain is floating or not:

$\mathbf{u}^{s} = (\mathbf{K}^{s})^{+} (\mathbf{f}^{s} - (\mathbf{B}^{s})^{T} \mathbf{\lambda}) + \mathbf{R}^{s}\mathbf{a}^{s}$

$\mathbf{u}^{s} = (\mathbf{K}^{s})^{-1} (\mathbf{f}^{s} - (\mathbf{B}^{s})^{T} \mathbf{\lambda})$

Coarse problem

The coarse problem of FETI-1 is expressed in the linear system $\mathbf{G}_{I}^{T} \mathbf{G}_{I} \cdot \mathbf{x} = \mathbf{y}$ contained in the interface problem system above. It helps speed up convergence by globally distributing the error at each PCG iteration.

Preconditioning

FETI-1 uses a standard preconditioner to speed up the convergence of PCG when solving the interface problem. The idea is to approximate the inverse of the flexibility matrix, which is defined for the boundary DOFs. The most common preconditioners used are Dirichlet and lumped.

Dirichlet preconditioner

Dirichlet preconditioner is defined as:

$\mathbf{F}_{I}^{-1} = \sum_{s = 1}^{N_{s}} \mathbf{B}_{pb}^{s} \mathbf{S}^{s} (\mathbf{B}_{pb}^{s})^{T}$

where S^s is the Schur complement of internal dofs

$\mathbf{S}^{s} = \mathbf{K}_{bb}^{s} - (\mathbf{K}_{ib}^{s})^{T}(\mathbf{K}_{ii}^{s})^{-1}\mathbf{K}_{ib}^{s}$

$\mathbf{B}_{pb}^{s}$ are sparse matrices that perform mapping (like B^s) and scaling. E.g. for a homogeneous stiffness distribution among subdomains:

$\mathbf{B}_{pb}^{s} = \mathbf{B}_{b}^{s}(\mathbf{M}_{b}^{s})^{-1}$

where $\mathbf{B}_{b}^{s}$ are the columns of $\mathbf{B}^{s}$ corresponding to boundary DOFs (boundary remainder in FETI-DP) and $\mathbf{M}_{b}$ is a diagonal matrix whose diagonal entries are the multiplicity of the corresponding DOFs, i.e. how many subdomains have instances of the DOFs.

Lumped preconditioner

Lumped preconditioner is defined as:

$\mathbf{F}_{I}^{-1} = \sum_{s = 1}^{N_{s}} \mathbf{B}_{pb}^{s} \mathbf{K}_{bb}^{s} (\mathbf{B}_{pb}^{s})^{T}$

In general, lumped preconditioners are faster to compute and implement, but does not speed up the convergence of PCG as much as Dirichlet.

Diagonal Dirichlet preconditioner

Diagonal Dirichlet preconditioner is defined as:

$\mathbf{F}_{I}^{-1} = \sum_{s = 1}^{N_{s}} \mathbf{B}_{pb}^{s} \mathbf{\hat{S}}^{s} (\mathbf{B}_{pb}^{s})^{T}$

where $\mathbf{\hat{S}}^{s}$ is an approximation of the Schur complement of internal dofs.

$\mathbf{\hat{S}}^{s} = \mathbf{K}_{bb}^{s} - (\mathbf{K}_{ib}^{s})^{T}(\mathbf{D}_{ii}^{s})^{-1}\mathbf{K}_{ib}^{s}$

where $\mathbf{D}_{ii}^{s}$ is the diagonal of $\mathbf{K}_{ii}^{s}$ .

In general, the computational cost of computing and implementing a diagonal Dirichlet preconditioner, as well as the resulting reduction of PCG iterations falls between that of Dirichlet and lumped preconditioner.

FETI-1 Remarks

FETI-1 is an efficient DDM that exhibits good scalability, namely the iterations required to converge do not increase as the number of subdomains increases. This makes it applicable to large scale simulations run on computing systems with a lot of networked computers. Its disadvantages are caused by the existence of floating subdomains, the processing of which is difficult and very sensitive to accuracy loss. Floating subdomains and rigid body motions also cause problems when FETI-1 is applied to dynamic problems.

Solvers

Linear algebra solvers for the solution of spatially and temporally discretized computational mechanics problems.