## Hybrid $V$-cycle algebraic multilevel preconditioners

HTML articles powered by AMS MathViewer

- by P. S. Vassilevski PDF
- Math. Comp.
**58**(1992), 489-512 Request permission

## Abstract:

We consider an algebraic derivation of multilevel preconditioners which are based on a sequence of finite element stiffness matrices. They correspond to a sequence of triangulations obtained by successive refinement and the associated finite element discretizations of second-order self adjoint elliptic boundary value problems. The stiffness matrix at a given discretization level is partitioned into a natural hierarchical two-level two-by-two block form. Then it is factored into block triangular factors. The resulting Schur complement is then replaced (approximated) by the stiffness matrix on the preceding (coarser) level. This process is repeated successively for a fixed number ${k_0} \geq 1$ of steps. After each ${k_0}$ steps, the preconditioner so derived is corrected by a certain polynomial approximation, a properly scaled and shifted Chebyshev matrix polynomial which involves the preconditioner and the stiffness matrix at the considered level. The hybrid*V*-cycle preconditioner thus derived is shown to be of optimal order of complexity for 2-D and 3-D problem domains. The relative condition number of the preconditioner is bounded uniformly with respect to the number of levels and with respect to possible jumps of the coefficients of the considered elliptic bilinear form as long as they occur only across edges (faces in 3-D) of elements from the coarsest triangulation. In addition, an adaptive implementation of our hybrid

*V*-cycle preconditioners is proposed, and its practical behavior is demonstrated on a number of test problems.

## References

- O. Axelsson,
*On multigrid methods of the two-level type*, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 352–367. MR**685778** - O. Axelsson and I. Gustafsson,
*Preconditioning and two-level multigrid methods of arbitrary degree of approximation*, Math. Comp.**40**(1983), no. 161, 219–242. MR**679442**, DOI 10.1090/S0025-5718-1983-0679442-3 - O. Axelsson and P. S. Vassilevski,
*Algebraic multilevel preconditioning methods. I*, Numer. Math.**56**(1989), no. 2-3, 157–177. MR**1018299**, DOI 10.1007/BF01409783 - O. Axelsson and P. S. Vassilevski,
*Algebraic multilevel preconditioning methods. II*, SIAM J. Numer. Anal.**27**(1990), no. 6, 1569–1590. MR**1080339**, DOI 10.1137/0727092
R. Bank and T. Dupont, - Randolph E. Bank, Todd F. Dupont, and Harry Yserentant,
*The hierarchical basis multigrid method*, Numer. Math.**52**(1988), no. 4, 427–458. MR**932709**, DOI 10.1007/BF01462238 - Dietrich Braess,
*The contraction number of a multigrid method for solving the Poisson equation*, Numer. Math.**37**(1981), no. 3, 387–404. MR**627112**, DOI 10.1007/BF01400317 - Dietrich Braess,
*The convergence rate of a multigrid method with Gauss-Seidel relaxation for the Poisson equation*, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 368–386. MR**685779**
R. Chandra, - P. Grisvard,
*Elliptic problems in nonsmooth domains*, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR**775683** - Yu. A. Kuznetsov,
*Algebraic multigrid domain decomposition methods*, Soviet J. Numer. Anal. Math. Modelling**4**(1989), no. 5, 351–379. MR**1026910** - J.-F. Maitre and F. Musy,
*The contraction number of a class of two-level methods; an exact evaluation for some finite element subspaces and model problems*, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 535–544. MR**685787** - Beresford N. Parlett,
*The symmetric eigenvalue problem*, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR**570116**
P. S. Vassilevski, - P. S. Vassilevski,
*Algebraic multilevel preconditioners for elliptic problems with condensation of the finite element stiffness matrix*, C. R. Acad. Bulgare Sci.**43**(1990), no. 6, 25–28. MR**1076662** - P. S. Vassilevski,
*Hybrid V-cycle algebraic multilevel preconditioners*, C. R. Acad. Bulgare Sci.**43**(1990), no. 8, 23–26. MR**1081408** - Harry Yserentant,
*On the multilevel splitting of finite element spaces*, Numer. Math.**49**(1986), no. 4, 379–412. MR**853662**, DOI 10.1007/BF01389538

*Analysis of a two-level scheme for solving finite element equations*, Report CNA-159, Center for Numerical Analysis, The University of Texas at Austin, 1980.

*Conjugate gradient methods for partial differential equations*, Research Report No. 119, Department of Computer Science, Yale University, 1978. P. Concus, G. H. Golub, and D. P. O’Leary,

*A generalized conjugate gradient method for the numerical solution of elliptic PDEs*, Sparse Matrix Computations (J. R. Bunch and D. J. Rose, eds.), Academic Press, New York, 1976, pp. 309-332.

*Nearly optimal iterative methods for solving finite element elliptic equations based on the multilevel splitting of the matrix*, Report #1989-09, Institute for Scientific Computation, University of Wyoming, Laramie.

## Additional Information

- © Copyright 1992 American Mathematical Society
- Journal: Math. Comp.
**58**(1992), 489-512 - MSC: Primary 65F35; Secondary 65N30
- DOI: https://doi.org/10.1090/S0025-5718-1992-1122081-6
- MathSciNet review: 1122081