Next: Test example : Axis Up: Numerical examples Previous: Test environment

## Computational costs

Let , and 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 by for we will obtain the corresponding work counts , for the improved multiscale cycles. Then, in the case of geometric multiscale decompositions ( ) and coarsest scale , we have the following standard cost estimates for multigrid-like implementations of our proposed cycles [21]:
• Standard multiscale V(1,1)-cycle: ,
• Improved multiscale V(1,1)-cycle: ,
• Standard multiscale W(1,1)-cycle: ,
where and . From the representation

one sees that the application of within the improved cycles is at least by a factor of nine more expensive than the application of alone. Here, we use 9-point stencils and consider only the costs for the application of and . 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

where nnz denotes the number of nonzero entries of a matrix . Grid complexity 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 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, 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)()) 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: Test example : Axis Up: Numerical examples Previous: Test environment
Frank Kiefer
2001-10-25