Parallel multilevel preconditioners

Authors:
James H. Bramble, Joseph E. Pasciak and Jinchao Xu

Journal:
Math. Comp. **55** (1990), 1-22

MSC:
Primary 65N30; Secondary 65F10

DOI:
https://doi.org/10.1090/S0025-5718-1990-1023042-6

MathSciNet review:
1023042

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we provide techniques for the development and analysis of parallel multilevel preconditioners for the discrete systems which arise in numerical approximation of symmetric elliptic boundary value problems. These preconditioners are defined as a sum of independent operators on a sequence of nested subspaces of the full approximation space. On a parallel computer, the evaluation of these operators and hence of the preconditioner on a given function can be computed concurrently.

We shall study this new technique for developing preconditioners first in an abstract setting, next by considering applications to second-order elliptic problems, and finally by providing numerically computed condition numbers for the resulting preconditioned systems. The abstract theory gives estimates on the condition number in terms of three assumptions. These assumptions can be verified for quasi-uniform as well as refined meshes in any number of dimensions. Numerical results for the condition number of the preconditioned systems are provided for the new algorithms and compared with other well-known multilevel approaches.

**[1]**R. E. Bank and T. Dupont,*An optimal order process for solving finite element equations*, Math. Comp.**36**(1981), 35-51. MR**595040 (82b:65113)****[2]**R. E. Bank, T. F. Dupont, and H. Yserentant,*The hierarchical basis multigrid method*, Numer. Math.**52**(1988), 427-458. MR**932709 (89b:65247)****[3]**G. Birkhoff and A. Schoenstadt, eds.,*Elliptic problem solvers*II, Academic Press, New York, 1984. MR**764219 (85g:65007)****[4]**J. H. Bramble and J. E. Pasciak,*New convergence estimates for multigrid algorithms*, Math. Comp.**49**(1987), 311-329. MR**906174 (89b:65234)****[5]**J. H. Bramble, J. E. Pasciak, and A. H. Schatz,*The construction of preconditioners for elliptic problems by substructuring*, I, Math. Comp.**47**(1986), 103-134. MR**842125 (87m:65174)****[6]**J. H. Bramble, J. E. Pasciak, and A. H. Schatz,*The construction of preconditioners for elliptic problems by substructuring*, II, Math. Comp.**49**(1987), 1-16. MR**890250 (88j:65248)****[7]**J. H. Bramble, J. E. Pasciak, and A. H. Schatz,*The construction of preconditioners for elliptic problems by substructuring*, III, Math. Comp.**51**(1988), 415-430. MR**935071 (89e:65118)****[8]**J. H. Bramble, J. E. Pasciak, and A. H. Schatz,*The construction of preconditioners for elliptic problems by substructuring*, IV, Math. Comp.**53**(1989), 1-24. MR**970699 (89m:65098)****[9]**J. H. Bramble, J. E. Pasciak, and J. Xu,*The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms*, Math. Comp.**56**(1991), (to appear). MR**1052086 (91h:65159)****[10]**J. H. Bramble, J. E. Pasciak, and J. Xu,*A multilevel preconditioner for domain decomposition boundary systems*, (in preparation).**[11]**P. Concus, G. H. Golub, and G. Meurant,*Block preconditioning for the conjugate gradient method*, SIAM J. Sci. Statist. Comput.**6**(1985), 220-252. MR**773293 (87c:65035a)****[12]**T. Dupont, R. P. Kendall, and H. H. Rachford,*An approximate factorization procedure for solving self-adjoint elliptic difference equations*, SIAM J. Numer. Anal.**5**(1968), 559-573. MR**0235748 (38:4051)****[13]**R. Glowinski, G. H. Golub, G. A. Meurant, and J. Périaux, eds., Proc. 1st Internat. Conf. on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1988. MR**972509 (89f:65005)****[14]**W. Hackbusch,*Multi-grid methods and applications*, Springer-Verlag, New York, 1985.**[15]**S. F. McCormick,*Multigrid methods for variational problems*:*Further results*, SIAM J. Numer. Anal.**21**(1984), 255-263. MR**736329 (85h:65115)****[16]**S. F. McCormick,*Multigrid methods for variational problems*:*General theory for the V-cycle*, SIAM J. Numer. Anal.**22**(1985), 634-643. MR**795945 (86m:65030)****[17]**J. Mandel, S. F. McCormick and R. Bank,*Variational multigrid theory*, Multigrid Methods (S. F. McCormick, ed.), SIAM, Philadelphia, PA, 1987, pp. 131-177. MR**972757****[18]**J. A. Meyerink and H. A. van der Vorst,*Iterative methods for the solution of linear systems of which the coefficient matrix is a symmetric M-matrix*, Math. Comp.**31**(1977), 148-162. MR**0438681 (55:11589)****[19]**J. Xu,*Theory of multilevel methods*, thesis, Cornell Univ., 1988.**[20]**H. Yserentant,*On the multi-level splitting of finite element spaces*, Numer. Math.**49**(1986), 379-412.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1990-1023042-6

Article copyright:
© Copyright 1990
American Mathematical Society