Parallel multilevel preconditioners

Bramble, James H.; Pasciak, Joseph E.; Xu, Jinchao

doi:10.1090/S0025-5718-1990-1023042-6

Parallel multilevel preconditioners
HTML articles powered by AMS MathViewer

by James H. Bramble, Joseph E. Pasciak and Jinchao Xu PDF

Math. Comp. 55 (1990), 1-22 Request permission

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.

References

Randolph E. Bank and Todd Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), no. 153, 35–51. MR 595040, DOI 10.1090/S0025-5718-1981-0595040-2
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
Garrett Birkhoff and Arthur Schoenstadt (eds.), Elliptic problem solvers. II, Academic Press, Inc., Orlando, FL, 1984. MR 764219, DOI 10.1137/1.9781611970869
James H. Bramble and Joseph E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), no. 180, 311–329. MR 906174, DOI 10.1090/S0025-5718-1987-0906174-X
J. H. Bramble, J. E. Pasciak, and A. H. Schatz, The construction of preconditioners for elliptic problems by substructuring. I, Math. Comp. 47 (1986), no. 175, 103–134. MR 842125, DOI 10.1090/S0025-5718-1986-0842125-3
J. H. Bramble, J. E. Pasciak, and A. H. Schatz, The construction of preconditioners for elliptic problems by substructuring. II, Math. Comp. 49 (1987), no. 179, 1–16. MR 890250, DOI 10.1090/S0025-5718-1987-0890250-4
James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz, The construction of preconditioners for elliptic problems by substructuring. III, Math. Comp. 51 (1988), no. 184, 415–430. MR 935071, DOI 10.1090/S0025-5718-1988-0935071-X
James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz, The construction of preconditioners for elliptic problems by substructuring. IV, Math. Comp. 53 (1989), no. 187, 1–24. MR 970699, DOI 10.1090/S0025-5718-1989-0970699-3
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms, Math. Comp. 56 (1991), no. 193, 1–34. MR 1052086, DOI 10.1090/S0025-5718-1991-1052086-4

A multilevel preconditioner for domain decomposition boundary systems

P. Concus, G. H. Golub, and G. Meurant, Block preconditioning for the conjugate gradient method, SIAM J. Sci. Statist. Comput. 6 (1985), no. 1, 220–252. MR 773293, DOI 10.1137/0906018
Todd Dupont, Richard P. Kendall, and H. H. Rachford Jr., An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal. 5 (1968), 559–573. MR 235748, DOI 10.1137/0705045
Roland Glowinski, Gene H. Golub, Gérard A. Meurant, and Jacques Périaux (eds.), First International Symposium on Domain Decomposition Methods for Partial Differential Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1988. MR 972509

Multi-grid methods and applications

S. F. McCormick, Multigrid methods for variational problems: further results, SIAM J. Numer. Anal. 21 (1984), no. 2, 255–263. MR 736329, DOI 10.1137/0721018
S. F. McCormick, Multigrid methods for variational problems: general theory for the $V$-cycle, SIAM J. Numer. Anal. 22 (1985), no. 4, 634–643. MR 795945, DOI 10.1137/0722039
J. Mandel, S. McCormick, and R. Bank, Variational multigrid theory, Multigrid methods, Frontiers Appl. Math., vol. 3, SIAM, Philadelphia, PA, 1987, pp. 131–177. MR 972757
J. A. Meijerink and H. A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric $M$-matrix, Math. Comp. 31 (1977), no. 137, 148–162. MR 438681, DOI 10.1090/S0025-5718-1977-0438681-4

Theory of multilevel methods

On the multi-level splitting of finite element spaces

49