HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-980724-A

  
The Domain Decomposition Preconditioner

For the domain decomposition method (FE substructure technique) let the domain $\Omega$ be subdivided into $\, p \,$ non-overlapping subdomains $\Omega_i$. The coupling boundary $\Gamma_C$ is defined as $\; \Gamma_C := \bigcup\limits_{i=1}^p \partial\Omega_i \setminus \Gamma_D \;$ with $\Gamma_D$ being the Dirichlet boundary. The index `C' always refers to nodes on that coupling boundary $\Gamma_C$ whereas the index `I' relates to nodes inside the subdomains $\Omega_i$. Figure 1 may serve as an example.

For the finite element method used here we utilize the basis $\Phi = \{ \varphi_1 , \varphi_2 \ldots \varphi_N \}$ consisting of the common piecewise linear ansatz functions $\varphi_i$ over the internal nodes of the triangulation. Let the numbering be such that all ansatz functions related to $\Gamma_C$ come first, followed by those related to the inner nodes of $\Omega_1$, $\Omega_2$ ... With this special ordering the resulting system of linear equations can be written in block form

$$\left( \begin{array}[c]{cc} {K_C} & {K_{CI}} \\ {K_{IC}} &... ...rline{f}_C} \\ {\underline{f}_I} \end{array} \right) \qquad .$$

The basis transformation of the FE basis $\Phi$ to the approximate discrete harmonic basis $\widetilde{\Psi}$ is given by

$$\widetilde{\Psi} := \Phi * \left( \begin{array}[c]{cc} {I... ...\ {-B_I^{-1}K_{IC}} & {I_I} \\ \end{array} \right) \qquad .$$

The Additive Schwarz Method (ASM) corresponding to the splitting of the finite element space into the subspaces span $\left\{ \Phi * ( I_C \, , \, -B_I^{-1}K_{IC} )^T \right\}$ and span $\left\{ \Phi * ( O \, , \, I_I )^T \right\}$ yields the preconditioner (cf. [12,13,23])

$$D = \left( \begin{array}[c]{cc} {I_C} & {K_{CI}B_I^{-T}} \... ...\\ {B_I^{-1}K_{IC}} & {I_I} \\ \end{array} \right) \qquad .$$

The matrices $B_I$, $\, S_C := K_C-K_{CI}K_I^{-1}K_{IC} \,$, $\; T_C := K_{CI}(K_I^{-1}-B_I^{-T})K_I(K_I^{-1}-B_I^{-1})K_{IC} \;$, and $S_C + T_C$ are referred to as the basis transformation, the Schur complement, the perturbation of the Schur complement, and the modified Schur complement, respectively.

Finally the matrices $S_C + T_C$ and $K_I$ are replaced by symmetric, positive definite and spectrally equivalent matrices $C_C$ and $C_I$, i.e.

$$\underline{\gamma}_C \, C_C \:\le\: S_C+T_C \:\le\: \overl... ..., C_I \:\le\: K_I \:\le\: \overline{\gamma}_I \, C_I \qquad .$$

It has been shown in [12,13] that the resulting preconditioner

$$C := \left( \begin{array}[c]{cc} {I_C} & {K_{CI}B_I^{-T}} ... ..._C} & {O} \\ {B_I^{-1}K_{IC}} & {I_I} \\ \end{array} \right)$$ (1)

is spectrally equivalent to $K$ with the spectral condition number estimate

$$\left({ \underline{\gamma} \;/\; \overline{\gamma} }\right)... ...} }\right) \left({ \: \sqrt{\mu} + \sqrt{1+\mu} \: }\right)^2$$ (2)

Here $\; \mu := \varrho \, (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$ is the spectral radius of $S_C^{-1} T_C^{\phantom{\!\!\!\!-1}}$, and $\;\underline{\gamma} := \min \{ \underline{\gamma}_C,\underline{\gamma}_I \}$ and $\; \overline{\gamma} := \max \{ \overline{\gamma}_C,\overline{\gamma}_I \}$.

In our examples the three components $C_I$, $C_C$ and $B_I$ of this preconditioner $C$ are chosen as follows:

• $C_I$ is defined by a suitable symmetric multigrid method yielding $h$-independent constants $\underline{\gamma}_I$ and $\overline{\gamma}_I = 1$ (cf. [17]).

• For $C_C$ the classical Dryja preconditioner (cf. [5]) is used in the model problem 1 giving $h$-independent constants $\underline{\gamma}_C$ and $\overline{\gamma}_C$ as well. In example 2, the BPS preconditioner [2] is applied resulting in a relatively slowly growing ratio $\overline{\gamma}_C / \underline{\gamma}_C = O( \ln^2 h^{-1})$ as $h \to 0$.

• $B_I$ is implicitly defined by the iteration operator $\overline{M}_I$ of some iteration method, i.e.
  

  $$B_I = K_I \, \Bigl( { I_I - \overline{M}_I \,} \Bigr)^{-1} \qquad .$$ (3)

  
  
  For model problem 1 and for several operators $\overline{M}_I$ the behaviour of the spectral radius $\mu = \varrho (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$ as $h \to 0$ is as follows:
  • The two-grid operator (i.e. multigrid with two grids) led to $\; \mu = O(h^{-1})$ on numerical examples (cf. Haase [10]).

  • The application of one multigrid step resulted in a growing $\; \mu = \varrho \, (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$ as $h \to 0$ on numerical tests [10]. Theoretically the growth is at most $O(h^{-1}) \,$ [12]. However, $O(\ln h^{-1})$ multigrid steps ensure a bounded $\mu$.

  • Haase, Langer, Meyer, and Nepomnyaschikh [14] construct the initial guess of the multigrid iteration by means of a hierarchical extension procedure. This gives $\; \mu = \varrho \, (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}}) = O( \ln h^{-1})$, or equivalently, $O(\ln \ln h^{-1} )$ multigrid steps imply a bounded $\mu$.

    Haase [11] improved the extension technique and showed that $O( \ln \ln h^{-1})$ smoothing steps yield a bounded $\mu$.

    Recently Nepomnyaschikh [21] proposed a BPX-like extension operator resulting in a bounded $\mu$ without multigrid improvement.

  • Haase [10] applied suitable frequency filter methods yielding an apparently bounded $\mu$ in numerical experiments.

These theoretical and numerical results indicate that the spectral condition number $\kappa(C^{-1}K)$ depends heavily on $\; \mu = \varrho \, (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$ and thus on $\, T_C = K_{CI}(K_I^{-1}-B_I^{-T})K_I(K_I^{-1}-B_I^{-1})K_{IC}$. Hence the improvement of $\kappa(C^{-1}K)$ has to be achieved via the basis transformation $B_I$.

To our knowledge the use of the full multigrid technique for the definition of the basis transformation $B_I$ has not been investigated theoretically. The analysis of this method is a major aim of this paper. We try to find out as to whether the $h$-dependence of $\; \mu = \varrho \, (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$, as it occurs by applying only one multigrid step, can be overcome.

HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-980724-A