Robustness of Algebraic Multilevel Methods

S. Margenov CLPP, Bulgarian Academy of Sciences, Acad. G. Bontchev Str., Bl.25A, 1113 Sofia, Bulgaria

Abstract

The AMLI method was proposed by Axelsson and Vassilevski who proved its optimality with respect to both convergence rate and arithmetic operations per iteration for problems with discontinuous coefficients independently of the regularity of the elliptic problem. We study the robustness of the AMLI methods in two more complicated cases: (a) elliptic problems with possible strong anisotropy; (b) 2D elasticity problems including the almost incompressible case, i.e. when the Poisson ratio ν ∈ (0, \frac{1}{2}) is near to the limit value of \frac{1}{2}. The basic result by Axelsson and Vassilevski says that the PCG iteration method defined by the AMLI preconditioner is of optimal order if

\frac{1}{\sqrt{1 − γ^{2}}} < β < ρ.  (∗)

Here N_{k} is the number of the nodal unknowns, corresponding to the triangulation τ_{k}; ρ = \frac{N_{k+1}}{N_{k}} stands for the mesh refinement ratio; and γ is the constant in the strengthened C.B.S. inequality, corresponding to the nested FEM spaces V_{k+1} and V_{k}. The constant γ plays a key role in the convergence analysis of the iterative methods. Three variants of the AMLI method are considered: (a)UR AMLI - (U)niform (R)efinement AMLI; (b)PS AMLI - (P)ure (S)emicoarsening AMLI; (c)BS AMLI - (B)alanced (S)emicoarsening AMLI. New estimates of γ in all of these cases are proved, uniformly on the ratio of anisotropy as well as on the Poisson ratio. These results guarantee, that the AMLI algorithm would be optimal, if we would be able to precondition efficiently the blocks A_{11}^{(k)} of the matrix at the discretization level k, corresponding to the new nodes added at refinement level k. Unfortunately the condition number of A_{11}^{(k)} deteriorates with the ratio of anisotropy as well as with the Poisson ratio. Our new results can be summarized as follows: UR AMLI Algorithm: An optimal order AMLI algorithm in the uniform refinement case is proposed for the anisotropic problem. The preconditioner of the block A_{11}^{(k)} is constructed following the so–called strategy of preserving the links along the dominated anisotropy. Unfortunately we do not know a similar winning strategy for the elasticity problem, for which the estimate γ^{2} < \frac{3}{4} uniformly on ν is proved. PS AMLI Algorithm: The optimality of the pure semicoarsening AMLI is proved uniformly on the ratio of anisotropy with parameters ρ = 4 and β = 3. In this case the constant in the strengthened C.B.S. inequality is bounded by γ^{2} < \frac{6}{7}. We have shown also, that lim_{ν→ \frac{1}{2}} \frac{1}{1−γ^{2}} = ρ^{2}, i.e., there does not exist PS AMLI algorithm for the almost incompressible elasticity problem, satisfying the optimality conditions (*). BS AMLI Algorithm: We have proved the optimality of the balanced semicoarsening AMLI algorithm for the elasticity problem with parameters ρ = 2 and β_{k} = 3^{(k+1) mod 2} (here the degree of the accelerating polynomial is varying). The constant in the strengthened C.B.S. inequality is estimated by γ^{2} < \frac{6}{7}, uniformly on ν. The performed numerical tests confirm the theoretical estimates.