Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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, 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.
  • 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, 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.
  • 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, 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.
  • 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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F35, 65N30
  • Retrieve articles in all journals with MSC: 65F35, 65N30
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