Hybrid -cycle algebraic multilevel preconditioners

Author:
P. S. Vassilevski

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 of steps. After each 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.

**[1]**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****[2]**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**, https://doi.org/10.1090/S0025-5718-1983-0679442-3**[3]**O. Axelsson and P. S. Vassilevski,*Algebraic multilevel preconditioning methods. I*, Numer. Math.**56**(1989), no. 2-3, 157–177. MR**1018299**, https://doi.org/10.1007/BF01409783**[4]**O. Axelsson and P. S. Vassilevski,*Algebraic multilevel preconditioning methods. II*, SIAM J. Numer. Anal.**27**(1990), no. 6, 1569–1590. MR**1080339**, https://doi.org/10.1137/0727092**[5]**R. Bank and T. Dupont,*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.**[6]**Randolph E. Bank, Todd F. Dupont, and Harry Yserentant,*The hierarchical basis multigrid method*, Numer. Math.**52**(1988), no. 4, 427–458. MR**932709**, https://doi.org/10.1007/BF01462238**[7]**Dietrich Braess,*The contraction number of a multigrid method for solving the Poisson equation*, Numer. Math.**37**(1981), no. 3, 387–404. MR**627112**, https://doi.org/10.1007/BF01400317**[8]**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****[9]**R. Chandra,*Conjugate gradient methods for partial differential equations*, Research Report No. 119, Department of Computer Science, Yale University, 1978.**[10]**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.**[11]**P. Grisvard,*Elliptic problems in nonsmooth domains*, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR**775683****[12]**Yu. A. Kuznetsov,*Algebraic multigrid domain decomposition methods*, Soviet J. Numer. Anal. Math. Modelling**4**(1989), no. 5, 351–379. MR**1026910****[13]**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****[14]**Beresford N. Parlett,*The symmetric eigenvalue problem*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. MR**570116****[15]**P. S. Vassilevski,*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.**[16]**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****[17]**P. S. Vassilevski,*Hybrid V-cycle algebraic multilevel preconditioners*, C. R. Acad. Bulgare Sci.**43**(1990), no. 8, 23–26. MR**1081408****[18]**Harry Yserentant,*On the multilevel splitting of finite element spaces*, Numer. Math.**49**(1986), no. 4, 379–412. MR**853662**, https://doi.org/10.1007/BF01389538

Harry Yserentant,*Erratum: “On the multilevel splitting of finite element spaces”*, Numer. Math.**50**(1986), no. 1, 123. MR**864309**, https://doi.org/10.1007/BF01389672

Retrieve articles in *Mathematics of Computation*
with MSC:
65F35,
65N30

Retrieve articles in all journals with MSC: 65F35, 65N30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1992-1122081-6

Keywords:
Multilevel methods,
hybrid *V*-cycle recursion,
approximate factorization,
polynomial acceleration,
finite elements,
optimal-order preconditioners

Article copyright:
© Copyright 1992
American Mathematical Society