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

  
The full two-grid operator

Let $\hat{M}_I$ and ${M_I}$ denote the two-grid operator and the full two-grid operator, respectively. We will expand ${M_I}$ and then obtain an exact formula for $\Vert { {M}_I \underline{z}_I } \Vert _{K_I}^2$ and eventually for $\mu$.

We start by introducing the abbreviations

$$%%\label{kurz} k' \: = \: n-k \quad , \quad s_k \: = \: \sin^2(k\pi h/2) \;,\; c_k \: = \: \cos^2(k\pi h/2)$$

which yield obviously $\; s_{k'} \:=\: c_k \;$ and $\;c_{k'} \:=\: s_k$. Let $[k,l] := \{ (k,l),(k',l),(k,l'),(k',l') \}$ be an index quadruplet. Let $\;\underline{x}_{[k,l]} := [x_{k,l} , x_{k',l} , x_{k,l'} ,x_{k',l'} ]^T$ be that 4-dimensional subvector of a vector $\underline{x} = \{ x_{k,l} \}_{k,l=\overline{1,n-1}}$ that corresponds to $[k,l]$. Analogously let $X_{[k,l]}$ denote the $4 \! \times \! 4$ submatrix of a (diagonal or block-diagonal) matrix $X$ whose entries relate to $[k,l]$. Let $[l] := \{l,l'\}$ be an index pair. Then $\sum_{[l]}$ and $\sum_{[k,l]}$ shall denote the summation over all index pairs and index quadruplets, respectively.

Let us now derive the expansion of $\hat{M}_I$ and ${M_I}$. The two-grid operator $\hat{M}_I$ can be written as

$$\hat{M}_I \, = \, S_{h} \,\; C_{h} \,\; S_{h} \,= \, \Big(... ...H K_h \Big) \cdot \Big( I_h-\frac{\omega}{4}K_h \Big) \qquad.$$

The indices $h$ and $H$ are related to the fine and coarse grid, respectively. We apply one $\omega$-Jacobi iteration for pre- and post-smoothing. The following notation is used.

The full two-grid technique means that the coarse grid system $K_H \,u_H = r_H$ is solved first before taking the interpolant $u_{k+\frac{1}{2}} = I^h_H \,u_H$ as the initial guess of the subsequent two-grid iteration. Thus we have

$$\begin{eqnarray*} u - u_{k+1} & = & \hat{M}_I \,(u - u_{k+\frac{1}{2}}) = \hat... ...)) = \hat{M}_I \,(I - I_H^h \,K_H^{-1} \,I^H_h \,K_h) (u - u_k) \end{eqnarray*}$$

(since we start with $u_k = 0$). Therefore the error transition operator of the full two-grid operator can be expressed as

$${M}_I = \hat{M}_I \,(I - I_H^h \,K_H^{-1} \,I^H_h \,K_h) = S_h \,C_h \,S_h \cdot C_h \qquad .$$

This operator ${M_I}$ will be expanded with respect to the orthonormal basis

$$%%\label{basisQ} Q := \left\{{ \mu_{k,l} }\right\}_{k,l = \overline{1,n-1}}$$

of the eigenvectors of $K_I$. Let the eigenvectors of an index quadruplet $[k,l]$ be placed in adjacent columns. The analysis of the appropriate operators results in

$$\left.{ \begin{array}{rcl} K_{I} \cdot Q & = & Q \cdot \L... ...dot \Theta \, C \, \Theta \, C \qquad \end{array} } \right\}$$ (8)

The matrix $\Lambda$ occurring in (8) has the form

$$\Lambda = \mbox{diag} \{ \lambda_{k,l} \}_{k,l = \overline{... ...\mbox{diag} \{ s_k + s_l \}_{k,l = \overline{1,n-1}} \qquad .$$

The matrix $\Theta$ represents the $\omega$-Jacobi smoothing and thus expands to

$$\Theta = \mbox{diag} \left\{ \left( 1-\frac{\omega}{4} \lambda_{k,l} \right) \right\} \qquad .$$

The coarse grid correction matrix $C$ has been derived in [16] and [10] to be

    

$$C = \mbox{blockdiag} \{ C_{[k,l]} \}$$

$$\mbox{with} \qquad C_{[k,l]} = I - R \cdot c \; c^{T} \Lambda_{[k,l]}$$ (9)

$$\mbox{and} \quad \; \; \qquad I = \mbox{the } \, 4 \times 4 \, \mbox{ identity matrix} ,$$

$$R := \frac{1}{4(s_{k} c_{k} + s_{l} c_{l})} ,$$ (10)

$$c := \left[{ c_k c_l,\, -s_k c_l, \, -c_k s_l,\, s_k s_l }\right]^T \qquad .$$ (11)

Here $\Lambda_{[k,l]}$ is the corresponding submatrix of $\Lambda$, i.e

$$\Lambda_{[k,l]} = 4 \cdot \mbox{diag} \{ s_k + s_l \, , \, c_k + s_l \, , \, s_k + c_l \, , \, c_k + c_l \} \qquad .$$

Note that for $k=k'$ and/or $l=l'$ the matrix $C_{[k,l]}$ is reduced to the $2 \times 2$ or $1 \times 1$ identity matrix. Additionally the matrix $\Theta C \Theta C$ is block-diagonal and thus the eigen subspace related to the quadruplet $[k,l]$ remains unchanged under the application of the full two-grid operator ${M_I}$.

Let us repeat the Fourier expansion (6) of $\underline{z}_I$:

  

$$\underline{z}_I = \sum\limits_{l=1}^{n-1} \sum\limits_{k=1}^{n-1} \left({\, \frac{-\mu_k(n-1)}{\lambda_{k,l}} \: \alpha_l \,}\right) \:\mu_{k,l} = \sum\limits_{l=1}^{n-1} \sum\limits_{k=1}^{n-1} \beta_{k,l} \mu_{k,l} = Q \cdot \underline{\beta} \qquad \qquad$$

$$<tex2html_comment_mark>101\mbox{with} \qquad \qquad \beta_{k,l} := \frac{-\mu_k(n-1)}{\lambda_{k,l}} \: \alpha_l \, \qquad .$$ (12)

Utilizing the matrix relations (8) we conclude

$$\begin{eqnarray*} {M}_{I} \underline{z}_I & = & {M}_{I} \cdot Q \underline{\bet... ...\cdot \Theta C \Theta C \underline{\beta} , \underline{\beta} ) \end{eqnarray*}$$

since $Q$ is an orthonormal basis. We introduce the new block-diagonal matrix

 

$$%%\label{F_FMG} {F} := C^T \Theta C^T \Theta \cdot \Lambda \cdot \Theta C \Theta C \; = \; \mbox{blockdiag} \{ {F}_{[k,l]} \}$$

$$\mbox{with} \qquad {F}_{[k,l]} = C^T_{[k,l]} \, \Theta_{[k,l]} \, C^T_{[k,l]} \, \Theta_{[k,l]} \c... ...} \, \Theta_{[k,l]} \, C_{[k,l]} \; \in \mbox{$\mathbb{R}$}^{4 \times 4} \qquad$$ (13)

and obtain the intermediate result

$$\Vert { M_I \underline{z}_I } \Vert _{K_I}^2 = ({F} \underl... ...underline{\beta}_{[k,l]} ,\underline{\beta}_{[k,l]} ) \qquad .$$

The substitution (12) of the $\beta_{k,l}$ by the $\alpha_l$ can be written as

 

$$\beta_{k,l} = \frac{-\mu_k(n-1)}{\lambda_{k,l}} \:\alpha_l$$

$$%%\be \label{al2be_matrix} \mbox{or} \qquad \underline{\beta}_{[k,l]} = \Gamma_{[k,l]} \cdot \underline{\alpha}_{[l]}$$

$$\mbox{with} \qquad \Gamma_{[k,l]} = \left[ \begin{array}{cc} - \frac{\displaystyle \mu_k (n-1)}{\disp... ...,l'}} \\ \end{array}\right] \quad \in \quad {\mbox{$\mathbb{R}$}}^{4 \times 2}$$ (14)

and the definition $\underline{\alpha}_{[l]} := [\alpha_l , \alpha_{l'}]^T$. The application of this substitution results in

$$\begin{eqnarray*} \Vert { M_I \underline{z}_I } \Vert _{K_I}^2 & = & ({F} \unde... ...]} \right) \; = \; ({H} \underline{\alpha}, \underline{\alpha}) \end{eqnarray*}$$

with the new matrices

 

$${G}_{[k,l]} := \Gamma_{[k,l]}^T {F}_{[k,l]} \Gamma_{[k,l]} \quad \in \quad {\mbox{$\mathbb{R}$}}^{2 \times 2}$$ (15)

$${H}_{[l]} := \sum\limits_{[k]} {G}_{[k,l]} \quad \in \quad {\mbox{$\mathbb{R}$}}^{2 \times 2}$$

$$\mbox{and} \qquad {H} := \mbox{blockdiag} \left\{ {H}_{[l]} \right\} \qquad .$$

Thus the numerator of $\delta_i$ in (4) is evaluated.

The denominator of $\delta_i$ has been approximated in (5) as

$$\Vert {\underline{u}_C} \Vert _{S_C}^2 \; = \; \left({ S_... ...) \; = \; (D \underline{\alpha}, \underline{\alpha}) \qquad .$$

Here $D_{[l]}$ and $D$ denote the positive definite diagonal matrices

 

$$D_{[l]} = \mbox{diag} \, \left\{ \sqrt{ \lambda_l^2 + 4\lambda_l\: }, \sqrt{ \lambda_{l'}^2 + 4\lambda_{l'}\: } \right\}$$ (16)

$$\mbox{and} \qquad D = \mbox{blockdiag} \, \left\{ D_{[l]} \right\} \qquad .$$

Finally $\delta_i$ can be expressed as

$$\delta_i \; = \; \sup\limits_{\underline{u}_C \in \rm R^{N... ...[l]} \; \varrho\left( D_{[l]}^{-1} {H}_{[l]} \right) \qquad .$$ (17)

since $D^{-1} {H}$ has a $2 \times 2$ block-diagonal form.

This last equation has been too difficult to analyse. It allows, however, an exact numerical evaluation of $\delta_i$ and thus of $\mu =\varrho \, (S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$. Table 1 comprises the the computed values of $\delta_i$ for decreasing $h$ and for three smoothing parameters $\omega$.

 

Table: Calculation of $\delta_i$ for the full two-grid operator

Note that the maximum in (17) always occurs at $l_{max}=1$. The results presented suggest the following

Conjecture 1   Consider the model problem 1 (cf. Figure 1). Suppose the full two-grid operator with bilinear interpolation and $\omega$-Jacobi smoothing is used as ${M}_I$. Then the spectral radius $\mu\,=\,\varrho \,(S_C^{-1} T_C^{\phantom{\!\!\!\!-1}})$ apparently grows like $O(h^{-1})$ as $h \to 0$.

Remark 1   The growth of $\mu = O( h^{-1} )$ is obvious for $\omega = 0.5$ and $\omega = 1.0$. In order to understand the different behaviour for $\omega = 1.5$ we have to look at equation (17). The two diagonal entries of $D_{[1]}^{-1} {H}_{[1]}$ behave differently (in the numerical test). The right lower entry (related to $\underline{u}_C = \mu_{n-1}$) seems to be bounded and dominates the spectral radius if $n \le 256$. The left upper entry however (related to $\underline{u}_C = \mu_1$) grows like $O( h^{-1} )$ and takes over for $n > 256$.

Remark 2   The dependence of $\delta_i$ on the smoothing parameter $\omega$ is shown in Figure 3. Four different mesh sizes $h = 1/n$ are considered.

  

Figure 3: Dependence of $\delta_i$ on $\omega$ for different $h$

Remark 3   For the multigrid method discussed here bilinear interpolation and the transposed restriction is assumed. The common FEM interpolation is not investigated since then (to our knowledge) no useful Fourier analysis of the coarse grid correction matrix $C$ is possible.

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