Hybrid cycle algebraic multilevel preconditioners
Author:
P. S. Vassilevski
Journal:
Math. Comp. 58 (1992), 489512
MSC:
Primary 65F35; Secondary 65N30
MathSciNet review:
1122081
Fulltext 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 secondorder self adjoint elliptic boundary value problems. The stiffness matrix at a given discretization level is partitioned into a natural hierarchical twolevel twobytwo 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 Vcycle preconditioner thus derived is shown to be of optimal order of complexity for 2D and 3D 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 3D) of elements from the coarsest triangulation. In addition, an adaptive implementation of our hybrid Vcycle preconditioners is proposed, and its practical behavior is demonstrated on a number of test problems.
 [1]
O.
Axelsson, On multigrid methods of the twolevel type,
Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960,
Springer, BerlinNew York, 1982, pp. 352–367. MR 685778
(84c:65139)
 [2]
O.
Axelsson and I.
Gustafsson, Preconditioning and twolevel
multigrid methods of arbitrary degree of approximation, Math. Comp. 40 (1983), no. 161, 219–242. MR 679442
(84i:65104), http://dx.doi.org/10.1090/S00255718198306794423
 [3]
O.
Axelsson and P.
S. Vassilevski, Algebraic multilevel preconditioning methods.
I, Numer. Math. 56 (1989), no. 23,
157–177. MR 1018299
(91c:65023), http://dx.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
(92b:65035), http://dx.doi.org/10.1137/0727092
 [5]
R. Bank and T. Dupont, Analysis of a twolevel scheme for solving finite element equations, Report CNA159, 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
(89b:65247), http://dx.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
(82h:65073), http://dx.doi.org/10.1007/BF01400317
 [8]
Dietrich
Braess, The convergence rate of a multigrid method with
GaussSeidel relaxation for the Poisson equation, Multigrid methods
(Cologne, 1981) Lecture Notes in Math., vol. 960, Springer,
BerlinNew York, 1982, pp. 368–386. MR 685779
(84c:65141)
 [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. 309332.
 [11]
P.
Grisvard, Elliptic problems in nonsmooth domains, Monographs
and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing
Program), Boston, MA, 1985. MR 775683
(86m:35044)
 [12]
Yu.
A. Kuznetsov, Algebraic multigrid domain decomposition
methods, Soviet J. Numer. Anal. Math. Modelling 4
(1989), no. 5, 351–379. MR 1026910
(90j:65140)
 [13]
J.F.
Maitre and F.
Musy, The contraction number of a class of twolevel methods;\ an
exact evaluation for some finite element subspaces and model problems,
Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960,
Springer, BerlinNew York, 1982, pp. 535–544. MR 685787
(84g:65153)
 [14]
Beresford
N. Parlett, The symmetric eigenvalue problem, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1980. PrenticeHall Series in Computational
Mathematics. MR
570116 (81j:65063)
 [15]
P. S. Vassilevski, Nearly optimal iterative methods for solving finite element elliptic equations based on the multilevel splitting of the matrix, Report #198909, 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 (91m:65279)
 [17]
P.
S. Vassilevski, Hybrid Vcycle algebraic multilevel
preconditioners, C. R. Acad. Bulgare Sci. 43 (1990),
no. 8, 23–26. MR 1081408
(92c:65060)
 [18]
Harry
Yserentant, On the multilevel splitting of finite element
spaces, Numer. Math. 49 (1986), no. 4,
379–412. MR
853662 (88d:65068a), http://dx.doi.org/10.1007/BF01389538
 [1]
 O. Axelsson, On multigrid methods of the twolevel type, Multigrid Methods (W. Hackbusch and U. Trottenberg, eds.) (Proceedings, KölnPorz 1981), Lecture Notes in Math., vol. 960, Springer, 1982, pp. 352367. MR 685778 (84c:65139)
 [2]
 O. Axelsson and I. Gustafsson, Preconditioning and twolevel multigrid methods of arbitrary degree of approximations, Math. Comp. 40 (1983), 219242. MR 679442 (84i:65104)
 [3]
 O. Axelsson and P. S. Vassilevski, Algebraic multilevel preconditioning methods. I, Numer. Math. 56 (1989), 157177. MR 1018299 (91c:65023)
 [4]
 , Algebraic multilevel preconditioning methods. II, SIAM J. Numer. Anal. 27 (1990), 15691590. MR 1080339 (92b:65035)
 [5]
 R. Bank and T. Dupont, Analysis of a twolevel scheme for solving finite element equations, Report CNA159, Center for Numerical Analysis, The University of Texas at Austin, 1980.
 [6]
 R. Bank, T. Dupont, and H. Yserentant, The hierarchical basis multigrid method, Numer. Math. 52 (1988), 427458. MR 932709 (89b:65247)
 [7]
 D. Braess, The contraction number of a multigrid method for solving the Poisson equation, Numer. Math. 37 (1981), 387404. MR 627112 (82h:65073)
 [8]
 , The convergence rate of a multigrid method with GaussSeidel relaxation for the Poisson equation, Multigrid Methods (W. Hackbusch and U. Trottenberg, eds.) (Proceedings, KölnPorz 1981), Lecture Notes in Math., vol. 960, Springer, 1982, pp. 368386. MR 685779 (84c:65141)
 [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. 309332.
 [11]
 P. Grisvard, Elliptic problems in nonsmooth domains, Pitman, BostonLondonMelbourne, 1985. MR 775683 (86m:35044)
 [12]
 Yu. A. Kuznetsov, Algebraic multigrid domain decomposition methods, Soviet J. Numer. Anal. Math. Modelling 4 (1989), 351380. MR 1026910 (90j:65140)
 [13]
 J. F. Maitre and F. Musy, The contraction number of a class of twolevel methods; an exact evaluation for some finite element subspaces and model problems, Multigrid Methods (W. Hackbusch and U. Trottenberg, eds.) (Proceedings, KölnPorz 1981), Lecture Notes in Math., vol. 960, Springer, 1982, pp. 535544. MR 685787 (84g:65153)
 [14]
 B. N. Parlett, The symmetric eigenvalue problem, PrenticeHall, Englewood Cliffs, NJ, 1980. MR 570116 (81j:65063)
 [15]
 P. S. Vassilevski, Nearly optimal iterative methods for solving finite element elliptic equations based on the multilevel splitting of the matrix, Report #198909, Institute for Scientific Computation, University of Wyoming, Laramie.
 [16]
 , Algebraic multilevel preconditioners for elliptic problems with condensation of the finite element matrix, C. R. Acad. Bulgare Sci. 43 (1990), no. 6, 2528. MR 1076662 (91m:65279)
 [17]
 , Hybrid Vcycle algebraic multilevel preconditioners, C. R. Acad. Bulgare Sci. 43 (1990), no. 8, 2326. MR 1081408 (92c:65060)
 [18]
 H. Yserentant, On the multilevel splitting of finite element spaces, Numer. Math. 49 (1986), 379412. MR 853662 (88d:65068a)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F35,
65N30
Retrieve articles in all journals
with MSC:
65F35,
65N30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199211220816
PII:
S 00255718(1992)11220816
Keywords:
Multilevel methods,
hybrid Vcycle recursion,
approximate factorization,
polynomial acceleration,
finite elements,
optimalorder preconditioners
Article copyright:
© Copyright 1992
American Mathematical Society
