FETI-DP Introduction

FETI-DP (Dual-Primal FETI) is a DDM DDM method introduced by Farhat et al. (2003), as a simpler and in many cases more efficient, alternative to FETI-1. FETI-DP is based on a dual-primary formulation of the problem to be solved. The main difference between the FETI-DP method and FETI-1 is that in FETI-DP, in every iteration of the PCG method, the compatibility of displacements is imposed to a small subset of primal corner DOFs, while the compatibility of displacements of the remaining boundary DOFs is only achieved after convergence.

Before continuing to the theory presented next, it is recommended to read the chapters on general DDMs and FETI-1. For a more detailed description of FETI-DP, see the original publication.

FETI-DP Theory

Primal & dual DOFs

Lagrange corner_nodes

For a given mesh partition, we define its corners as the set of nodes located at the beginning and end of each edge of each subdomain, as illustrated in the figure above. Using this definition in 2D problems, the set of corner nodes will include all crosspoints, namely nodes belonging to more than two subdomains.

The freedom degrees (DOFs) associated with these corner nodes will be called corner or primal DOFs and designated with the subscript c. The other DOFs of each subdomain will be called remainder DOFs and designated the subscript r. E.g. if we denote by K^s, u^s andf^s the stiffness matrix, displacement vector and force vector of vector of subdomain s respectively, these quantities are then decomposed based on the DOFs:

$\mathbf{u}^s = \begin{bmatrix} \mathbf{u}^s_c \\ \mathbf{u}^s_r\end{bmatrix}$

$\mathbf{K}^s = \begin{bmatrix} \mathbf{K}^s_{cc} & \mathbf{K}^s_{cr}\\ \left( \mathbf{K}^s_{cr} \right)^T & \mathbf{K}^s_{rr} \end{bmatrix}$

$\mathbf{f}^s = \begin{bmatrix} \mathbf{f}^s_c \\ \mathbf{f}^s_r\end{bmatrix}$

We further decompose remainder DOFs into internal DOFs, which are associated with nodes that belong to only one subdomain and are designated by the subscript i, and boundary-remainder DOFs, which are associated with nodes that belong to more than one subdomains without being corners and are designated by the subscript b. E.g.

$\mathbf{u}^s_r = \begin{bmatrix} \mathbf{u}^s_b \\ \mathbf{u}^s_i\end{bmatrix}$

$\mathbf{K}^s_{rr} = \begin{bmatrix} \mathbf{K}^s_{bb} & \mathbf{K}^s_{bi}\\ \left( \mathbf{K}^s_{bi} \right)^T & \mathbf{K}^s_{ii} \end{bmatrix}$

$\mathbf{f}^s_r = \begin{bmatrix} \mathbf{f}^s_b \\ \mathbf{f}^s_i\end{bmatrix}$

We gather the displacements corresponding to all corner dofs of the whole domain in a vector $u_c$ of length N_c and define the mapping between global $\mathbf{\bar{u}}_c$ and subdomain $\mathbf{u}^s_c$ as boolean matrices $\mathbf{B}^s_c$ that have 0/1 entries and dimensions $\left(N_c^s \times N_c \right)$ , where $N_c^s$ and $N_c$ are the number of corner DOFs of subdomain s and the whole domain, respectively.

$\mathbf{B}_c^s \mathbf{u}_c = \mathbf{u}_c^s$

As in FETI-1, the continuity between the otherwise diconnected subdomains is retained by enforcing equal displacements for instances of the same boundary DOF in different subdomains. 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$

These continuity equations are gathered into signed boolean matrices $\mathbf{B}_r^{s}$ which have 0, 1, -1 entries and dimensions $\left(N_{\lambda} \times N_r^s \right)$ , where $N_{\lambda}$ is the number of continuity equations of the whole domain and $N_r^s$ the number of subdomain’s s remainder dofs:

$\sum_{s = 1}^{N_{s}} \mathbf{B}_r^{s} \mathbf{u}_r^{s} = \mathbf{0}$

Lagrange multipliers

To solve the initial equilibrium equations K u = f in the presence of these constraints, we apply Lagrange multipliers λ at boundary DOFs, as illustrated in the figure above. These are dual quantities and can be viewed as forces, while displacements are primal quantities. It should be clarified that no Lagrange multipliers are applied at corner dofs. The equilibrium equations can then be written as:

$\mathbf{K}_{rr}^s u_r^s + \mathbf{K}_{rc}^s \mathbf{B}_c^s \mathbf{u}_c + (\mathbf{B}_r^s)^T \mathbf{\lambda} = \mathbf{f}_r^s$

$\sum_{s = 1}^{N_{s}} (\mathbf{B}_c^s)^T (\mathbf{K}_{rc}^s)^T \mathbf{u}_r^s + \sum_{s = 1}^{N_{s}} (\mathbf{B}_c^s)^T (\mathbf{K}_{cc}^s)^T \mathbf{B}_c^s \mathbf{u}_c^s = \sum_{s = 1}^{N_{s}} (\mathbf{B}_c^s)^T \mathbf{f}_c^s$

Interface problem

With an appropriate selection of corner nodes $\mathbf{K}_{rr}^s$ is an invertible matrix, meaning that the floating subdomains of the original FETI method are avoided in FETI-DP. We can then consider each subdomain as a superelement that has the subdomain’s corners as nodes. The stiffness and applied forces of this superelement are obtained by perform static condensation of the remainder DOFs. Then we assemble the resulting matrices/vectors into global ones, exactly as we would do with individual elements in FEM.

$\mathbf{K}_{cc}^{*} = \sum_{s = 1}^{N_{s}} (\mathbf{B}_{c}^{s})^{T} \left( \mathbf{K}_{cc}^s-(\mathbf{K}_{rc}^{s})^{T}(\mathbf{K}_{rr}^{s})^{-1} \mathbf{K}_{rc}^{s} \right) \mathbf{B}_{c}^{s}$

$\mathbf{f}_{c}^{*} = \sum_{s = 1}^{N_{s}} (\mathbf{B}_{c}^{s})^{T} \left( \mathbf{f}_{c}^s - (\mathbf{K}_{rc}^{s})^{T}(\mathbf{K}_{rr}^{s})^{-1}\mathbf{f}_{r}^{s} \right)$

Since $\mathbf{K}_{rr}^s$ is positive definite, its Schur complement is also positive definite. Assembling these Schur complements into $\bm{K}_{cc}^*$ also results in a positive definite matrix. We also set the following quantities:

$\mathbf{F}_{Irr} = \sum_{s = 1}^{N_{s}}\mathbf{B}_{r}^{s}(\mathbf{K}_{rr}^{s})^{-1}(\mathbf{B}_{r}^{s})^{T}$

$\mathbf{F}_{Irc} = \sum_{s = 1}^{N_{s}}\mathbf{B}_{r}^{s}(\mathbf{K}_{rr}^{s})^{-1}\mathbf{K}_{rc}^{s}\mathbf{B}_{c}^{s}$

$\mathbf{d}_{r} = \sum_{s = 1}^{N_{s}}\mathbf{B}_{r}^{s}(\mathbf{K}_{rr}^{s})^{-1}\mathbf{f}_{r}^{s}$

Note that $\mathbf{F}_{Irr}$ is essentially the inverse of the original stiffness matrix of the whole domain, limited to boundary DOFs, hence a flexibility matrix. Furthermore $\mathbf{d}_{r}$ expresses the displacements, due to loading, along boundary dofs of the subdomains, as if they were not connected to each other.

After some algebraic manipulation the equilibrium equation can be written as:

$\begin{bmatrix} \mathbf{F}_{Irr} & \mathbf{F}_{Irc} \\ \left(\mathbf{F}_{Irc}\right)^T & -\mathbf{K}_{cc}^* \end{bmatrix} \cdot \begin{bmatrix} \mathbf{\lambda} \\ \mathbf{u}_c \end{bmatrix} = \begin{bmatrix} \mathbf{d}_r \\ -\mathbf{f}_c^s \end{bmatrix}$

By decoupling the corner DOFs from the Lagrange multipliers, the linear system of the FETI-DP interface problem is obtained:

$\left( \mathbf{F}_{Irr} + \mathbf{F}_{Irc} (\mathbf{K}_{cc}^*)^{-1} (\mathbf{F}_{Irc})^T \right) \cdot \mathbf{\lambda} = \mathbf{d}_r - \mathbf{F}_{Irc} (\mathbf{K}_{cc})^{-1} \mathbf{f}_c^*$

The matrix of the linear system above is positive definite, therefore the interface problem can be solved using the Preconditioned Conjugate Gradient method (PCG). After solving it for the Lagrange multipliers λ, the displacements at corner and remainder DOFs can be calculated by

$\mathbf{u}_{c} = \left( \mathbf{K}_{cc}^* \right)^{-1} \left( \mathbf{f}_{c}^{*} + (\mathbf{F}_{Irc})^T \mathbf{\lambda} \right)$

$\mathbf{u}_{r}^{s} =(\mathbf{K}_{rr}^s)^{-1}(\mathbf{f}_r^s - \left(\mathbf{B}_r^s)^T \mathbf{\lambda} - \mathbf{K}_{rc}^s \mathbf{B}_c^s \mathbf{u}_c \right)$

Coarse problem

During the solution of the interface problem, at each matrix-vector multiplication:

$\mathbf{F}_{Irr} + \mathbf{F}_{Irc} (\mathbf{K}_{cc}^*)^{-1} (\mathbf{F}_{Irc})^{T}$$

performed in PCG, we need to solve the linear system

$\mathbf{K}_{cc}^* \cdot $\mathbf{x} = $\mathbf{y}$$ .

This linear system expresses the coarse problem of FETI-DP: a much smaller auxilliary problem involving only corner DOFs, that speeds up convergence by coupling the subdomain computations and globally propagating the error at each PCG iteration.

Preconditioning

FETI-DP uses the same preconditioners as FETI-1 to speed up the convergence of PCG when solving the interface problem. The only difference is that boundary corner DOFs are not taken into account in the preconditiones, since in FETI-DP they are not part of the interface problem. Therefore all matrices with the index b refer to the boundary-remainder DOFs, instead of all boundary DOFs. For more details, see FETI-1 preconditioners

FETI-DP Remarks

FETI-DP 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. By using a set of primal (corner) DOFs, it avoids the floating subdomains of FETI-1 and all their problems, therefore it is much simpler to comprehend and implement. Furthermore, it is often more efficient than FETI-1.

Solvers

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