Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
maximize
next up previous
Next: Concluding remarks Up: Numerical examples Previous: Test example : Dependence

Test example $ T^{\delta }$: Circular convection


Table 7: Example $ T^{\delta }$: Standard multiscale V(1,1)-cycle, average error reduction $ \varrho _{it,1}$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8      0.02          0.03          0.14          0.06          0.02          0.01          0.01          0.01     
16      0.08          0.09          0.18          0.23          0.16          0.14          0.17          0.16     
32      0.17          0.17          0.26          0.30          0.28          0.22          0.24          0.25     
64      0.21          0.30          0.46          0.52          0.37          0.33          0.29          0.28     
128      0.35          0.33          0.43          0.46          0.46          0.32          0.40          0.37     
256      0.37          0.42          0.51          0.46          0.52          0.43          0.43          0.49     
512      0.45          0.41          0.53          0.51          0.59          0.51          0.46          0.60     
1024      0.48          0.52          0.57          0.61          0.59          0.63          0.61          0.66     
$ P^{k}_{k+1,{\cal V}}$ AMG( $ 0.1,0.35,0.0$) $ Q^{k}_{k+1,{\cal V}}$ hierarchical filter
$ P^{k}_{k+1,{\cal S}}$ $ P^{k}_{k+1,{\cal V}}$ $ Q^{k}_{k+1,{\cal S}}$ hierarchical filter


Table 8: Example $ T^{\delta }$: Standard multiscale V(1,1)-cycle, average error reduction $ \varrho _{it,1}$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8      0.03          0.04          0.06          0.03          0.01          0.01          0.01          0.01     
16      0.07          0.07          0.08          0.07          0.10          0.05          0.05          0.05     
32      0.10          0.09          0.10          0.12          0.09          0.10          0.10          0.10     
64      0.11          0.09          0.10          0.18          0.11          0.10          0.10          0.11     
128      0.10          0.10          0.12          0.16          0.14          0.11          0.13          0.12     
256      0.13          0.11          0.13          0.15          0.16          0.14          0.14          0.12     
512      0.12          0.13          0.12          0.14          0.18          0.18          0.14          0.14     
1024      0.13          0.12          0.11          0.25          0.32          0.25          0.17          0.22     
$ P^{k}_{k+1,{\cal V}}$ AMG( $ 0.1,0.35,0.0$) $ Q^{k}_{k+1,{\cal V}}$ $ [(T_{k-1,(i,j)})_{*}]_{0.125}$
$ P^{k}_{k+1,{\cal S}}$ $ P^{k}_{k+1,{\cal V}}$ $ Q^{k}_{k+1,{\cal S}}$ hierarchical filter


Table 9: Example $ T^{\delta }$: Standard multiscale V(1,1)-cycle, average error reduction $ \varrho _{it,1}$. Table 9: Example $ T^{\delta }$: Multigrid V(1,1)-cycle by AMG( $ 0.1,0.35,0.0$), average error reduction $ \varrho _{it,1}$,
standard prolongation, pointwise Gauß-Seidel smoother based on the fine to coarse ordering of the unknowns,
stopping criterion: Reduction of the $ l_2$-norm of the corresponding residuals below $ 10^{-10}$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8      0.04          0.04          0.02          0.02          0.00          0.00          0.00          0.00     
16      0.05          0.05          0.04          0.05          0.03          0.03          0.03          0.03     
32      0.08          0.07          0.06          0.09          0.05          0.04          0.04          0.04     
64      0.09          0.09          0.09          0.12          0.06          0.11          0.05          0.05     
128      0.12          0.11          0.11          0.25          0.09          0.08          0.08          0.07     
256      0.14          0.14          0.07          0.16          0.12          0.09          0.10          0.10     
512      0.15          0.15          0.09          0.22          0.21          0.10          0.10          0.11     
1024      0.16          0.17          0.11          0.18          0.38          0.14          0.13          0.12     




Error norms w.r.t. standard multiscale V(1,1)-cycles, different fine grid sizes h0, b=106;
AMG-based hierarchical decomposition (left) and stabilized decomposition (right).


Table 10: Example $ T^{\delta }$: Non-standard operator complexity $ {\cal C}^o_{ns}$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8      2.93          2.94          3.44          3.18          3.18          3.18          3.18          3.18     
16      3.37          3.36          5.38          4.37          4.18          4.17          4.17          4.17     
32      3.77          3.78          7.12          5.51          5.12          5.29          5.23          5.23     
64      4.11          4.03          5.20          8.88          5.52          5.64          5.62          5.60     
128      4.17          4.17          5.05          10.87          6.33          6.20          6.20          6.22     
256      4.34          4.32          4.57          11.81          7.59          6.68          6.66          6.66     
512      4.35          4.44          4.44          9.78          10.54          7.19          7.13          7.15     
1024      4.38          4.41          4.33          6.58          12.15          7.47          7.60          7.83     
$ P^{k}_{k+1,{\cal V}}$ AMG( $ 0.1,0.35,0.0$) $ Q^{k}_{k+1,{\cal V}}$ hierarchical filter
$ P^{k}_{k+1,{\cal S}}$ $ P^{k}_{k+1,{\cal V}}$ $ Q^{k}_{k+1,{\cal S}}$ hierarchical filter


Table 11: Example $ T^{\delta }$: Non-standard operator complexity $ {\cal C}^o_{ns}$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8      3.94          3.95          4.11          3.72          3.72          3.72          3.72          3.72     
16      4.94          4.92          6.51          5.09          4.93          4.91          4.91          4.91     
32      5.66          5.67          8.66          6.53          5.98          6.16          6.11          6.11     
64      6.22          6.15          7.09          10.24          6.56          6.62          6.62          6.61     
128      6.48          6.46          7.14          12.62          7.43          7.24          7.23          7.24     
256      6.73          6.70          6.80          13.80          8.84          7.76          7.76          7.74     
512      6.79          6.86          6.80          11.91          12.11          8.31          8.24          8.25     
1024      6.84          6.87          6.76          8.77          14.04          8.65          8.73          8.94     
$ P^{k}_{k+1,{\cal V}}$ AMG( $ 0.1,0.35,0.0$) $ Q^{k}_{k+1,{\cal V}}$ $ [(T_{k-1,(i,j)})_{*}]_{0.125}$
$ P^{k}_{k+1,{\cal S}}$ $ P^{k}_{k+1,{\cal V}}$ $ Q^{k}_{k+1,{\cal S}}$ hierarchical filter


Table 12: Example $ T^{\delta }$: Grid complexity $ {\cal C}^g$ and number of scales $ l$ produced by AMG $ (0.1,0.35,0.0)$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8      1.88          1.94          2.20          2.22          2.22          2.22          2.22          2.22     
16      1.73          1.74          2.13          2.25          2.26          2.26          2.26          2.26     
32      1.70          1.71          2.02          2.22          2.39          2.36          2.36          2.36     
64      1.69          1.69          1.81          2.22          2.25          2.31          2.32          2.32     
128      1.68          1.68          1.74          2.17          2.30          2.34          2.37          2.37     
256      1.67          1.67          1.69          2.07          2.26          2.32          2.32          2.34     
512      1.67          1.67          1.67          1.90          2.20          2.33          2.33          2.32     
1024      1.67          1.67          1.67          1.75          2.15          2.29          2.32          2.34     
$ P^{k}_{k+1,{\cal V}}$ AMG( $ 0.1,0.35,0.0$) $ Q^{k}_{k+1,{\cal V}}$ $ [(T_{k-1,(i,j)})_{*}]_{0.125}$
$ P^{k}_{k+1,{\cal S}}$ $ P^{k}_{k+1,{\cal V}}$ $ Q^{k}_{k+1,{\cal S}}$ hierarchical filter


Table 13: Example $ T^{\delta }$: Number of scales $ l$ produced by AMG $ (0.1,0.35,0.0)$.
$ h_0^{-1}\backslash\;b$      0.0          $ 10^1$          $ 10^2$          $ 10^3$          $ 10^4$          $ 10^5$          $ 10^6$          $ 10^8$     
8     5          6          6          6          6          6          6          6     
16     6          6          9          8          8          8          8          8     
32     7          8          9          11          11          10          10          10     
64     8          9          13          14          12          13          12          12     
128     9          11          15          16          16          15          16          15     
256     10          11          15          19          17          17          16          18     
512     11          12          16          22          19          21          21          22     
1024     13          13          17          23          23          23          23          24     
$ P^{k}_{k+1,{\cal V}}$ AMG( $ 0.1,0.35,0.0$) $ Q^{k}_{k+1,{\cal V}}$ $ [(T_{k-1,(i,j)})_{*}]_{0.125}$
$ P^{k}_{k+1,{\cal S}}$ $ P^{k}_{k+1,{\cal V}}$ $ Q^{k}_{k+1,{\cal S}}$ hierarchical filter

For the challenging problem $ T^{\delta }$ of a circular convection none of our multiscale solvers works satisfactory on the basis of the geometric multiscale decompositions. Therefore, we switch to solvers based on algebraic multiscale decompositions (c.f. report, Section 4). Due to the algebraic selection of the coarse-grid points we only apply multiscale V(1,1)-cycles to obtain iteration schemes that can still be implemented with linear complexity. In all experiments we use the same prolongations for the transformation matrices $ P^{k}_{k+1,{\cal V}}$ and $ P^{k}_{k+1,{\cal S}}$ which result from AMG with parameters ( $ \alpha,\beta,\gamma_P$). The decompositions on the trial and test side are chosen hierarchically or wavelet-like and the detail corrections are always computed via incomplete factorizations of the resulting blocks $ A_k$ ($ k=1,...,l$).

Table 7 shows the average error reduction rates from standard multiscale V(1,1)-cycles based on a hierarchical decomposition of both the trial and test side resulting from AMG( $ 0.1,0.35,0.0$). From the first column we see that the method is not independent of the fine-grid mesh size. This is typical for HBMG-like methods. The overall convergence behavior of the method is neither optimal nor robust. Of course, using the cycle only as a preconditioner for a Krylov subspace method may soften the dependence on $ h_0$ [31].

Table 8 shows the benefits of the wavelet-like stabilization as described in Section 4 in a striking way. Here, only the transformations $ Q^{k}_{k+1,{\cal V}}$ have been changed where we used $ \gamma_Q=0.125$ as cut-off parameter. By this choice we obtain an AMGlet decomposition of the trial space that leads to an overall robust convergence behavior. For $ h_0\leq{1}/{512}$ the average error reduction rates stay below $ 0.2$ uniformly w.r.t. $ b$. For $ h_0={1}/{1024}$ we observe a slight growth and a maximal rate of $ 0.32$ when $ b=10^4$. Note however that also the ordinary AMG algorithm seems to ``feel'' the difficulty. This can be seen from Table 9, which shows the average error reduction rates for an ordinary multigrid V(1,1)-cycle based on AMG( $ 0.1,0.35,0.0$) and a pointwise Gauß-Seidel smoother. Here, we obtain $ \varrho_{it,1}=0.38$ for the corresponding problem. It is clear that our method can not do essentially better than ordinary AMG. The stabilizing effect of the AMGlet approach is also evident from Figure 1 which shows the error norms from iterations by the purely hierarchical (left) and the stabilized method (right) for different fine-grid sizes $ h_0$ with $ b=10^6$. The choice of the complement bases has no influence on the AMG coarsening process. Hence, AMG produces for both kinds of decompositions the same number of scales and one obtains the same grid complexities. They behave quite reasonable which can be observed from Tables 12, 13. The non-standard operator complexities are in the lower convective range about 56% higher for the AMGlet decomposition of the trial space compared to those which result from the hierarchical decompositions on both sides. This can be seen from the comparison of the last three rows of Tables 10 and 11. For $ b > 10^3$ the difference is much smaller, i.e. only about 16%. If we compare this with the respective error reduction rates, the AMGlet decomposition - although expensive - will be preferable. However, it is not completely clear from Table 10 that the solver is indeed robust.



Left picture: The first five coarse grids selected by AMG(0.1,0.35,0.0) (coarser grids correspond to thicker points, h0=1/128, b=106;
right picture: AMGlet generated by our stabilization of the AMG-based hierarchical basis on the trial side, same parameters.

On the left of Figure 2 the hierarchy of grids is displayed which is produced by AMG( $ 0.1,0.35,0.0$) after five coarsening steps for the case $ b=10^6$ and mesh size $ h_0=1/128$ of the fine grid. Finally, it is interesting to take a look at the complementary basis functions which are implicitly generated by our approach. For the same parameters as above an AMGlet is shown on the right of Figure 1. Apparently the AMGlet follows the convective flow and takes positive and negative values as a wavelet should.


next up previous
Next: Concluding remarks Up: Numerical examples Previous: Test example : Dependence
Frank Kiefer
2001-10-25