Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
next up previous
Next: Test example : Axis Up: Numerical examples Previous: Test environment

Computational costs

Let $ {\cal C}_S$, $ {\cal C}_R$ and $ {\cal C}_C$ be the normalized work counts for the multiscale smoothing, residual restriction and correction steps within the equivalent multigrid implementation of our standard multiscale cycles. If we replace $ {T}_{k-1}$ by $ \breve{S}_{k-1}$ for $ k>1$ we will obtain the corresponding work counts $ {\cal C}_{S,imp}$, $ {\cal C}_{R,imp}$ for the improved multiscale cycles. Then, in the case of geometric multiscale decompositions ( $ N_k\leq{N_{k-1}}/{4}$) and coarsest scale $ l$, we have the following standard cost estimates for multigrid-like implementations of our proposed cycles [21]: where $ {\cal C}_{std}:=2{\cal C}_S+{\cal C}_R+{\cal C}_C$ and $ {\cal C}_{imp}:=2{\cal C}_{S,imp}+{\cal C}_{R,imp}+{\cal C}_C$. From the representation
$\displaystyle \breve{S}_{k-1}$ $\displaystyle =$ $\displaystyle T_{k-1}-C_{k-1}\breve{A}_{k-1}^{-1}B_{k-1}$  
  $\displaystyle =$ $\displaystyle T_{k-1}-(P^{k-2}_{k-1,{\cal S}})^tT_{k-2}Q^{k-2}_{k-1,{\cal V}}\breve{A}_{k-1}^{-1}
(Q^{k-2}_{k-1,{\cal S}})^tT_{k-2}P^{k-2}_{k-1,{\cal V}}$  

one sees that the application of $ \breve{S}_{k-1}$ within the improved cycles is at least by a factor of nine more expensive than the application of $ T_{k-1}$ alone. Here, we use 9-point stencils and consider only the costs for the application of $ T_{k-1}$ and $ T_{k-2}$. Hence, the improved versions are more expensive than a standard multiscale W-cycle.

Regarding the costs for our AMG-based multiscale cycles there are unfortunately no predictive cost analyses available. Therefore, we define as grid and non-standard operator complexities (adapted to an AMG-based non-standard form) the two numbers

$\displaystyle {\cal C}^g: =\frac{\sum_{k=0}^{l}\mbox{\rm dim}({\cal V}_k)}{\mbo...
...1}^{l}\big[\mbox{\rm nnz}(A_k)+\mbox{\rm nnz}(T_k)\big]}{\mbox{\rm nnz}(T_0)},

where nnz$ (M)$ denotes the number of nonzero entries of a matrix $ M$. Grid complexity $ C^g$ gives an accurate measure of the total storage required for the residual and correction vectors with respect to the different scales. Non-standard operator complexity $ C_{ns}^o$ indicates the total storage space necessary for the blocks of the non-standard form as well as for the fine-grid operator that are used within the multiscale cycles. It generalizes the well known AMG operator complexity [10]. Furthermore, $ C_{ns}^o$ gives a measure of the work involved in the solve phase in the case of multiscale V(1,1)-cycles. Here, we assume that the costs for the detail correction (essentially ILU(0)($ A_k$)) and for the computation of the residuals are proportional to the number of nonzero entries of the corresponding blocks of the non-standard form.
next up previous
Next: Test example : Axis Up: Numerical examples Previous: Test environment
Frank Kiefer