×

Parallelizing preconditioned conjugate gradient algorithms. (English) Zbl 0798.65040

Summary: Various iterative methods for solving the linear systems associated with finite element approximations to selfadjoint elliptic differential operators are compared based on their performance on serial and parallel machines. The methods studied are all preconditioned conjugate gradient methods, differing only in the choice of preconditioner. The preconditioners considered arise from diagonal scaling, incomplete Cholesky decomposition, hierarchical basis functions and an additive Schwarz domain decomposition technique. The hierarchical basis function idea is shown to be especially effective for 2-D problems on both serial and parallel architectures. For 3-D problems, the additive Schwarz method appears promising.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations

Software:

LINPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bank, R.; Dupont, T.; Yserentant, H., preprint SC-87-2 (April 1987), Konrad-Zuse-Zentrum for Informationstechnik Berlin
[2] W. Berke, A Structured Environment for Parallel Fortran, Ultracomputer Systems Software Note, in preparation.; W. Berke, A Structured Environment for Parallel Fortran, Ultracomputer Systems Software Note, in preparation.
[3] Concus, P.; Golub, G. H.; O’Leary, D. P., (Bunch, J. R.; Rose, Sparse Matrix Computations (1976), Academic Press: Academic Press New York), 309
[4] Dongarra, J. J.; Moler, C. B.; Bunch, J. R.; Stewart, G. W., LINPACK User’s Guide (1979), SIAM: SIAM Philadelphia · Zbl 0476.68025
[5] Dryja, M.; Widlund, O., Ultracomputer Note #131, (Computer Science Technical Report #339 (December 1987), Courant Institute)
[6] Gottlieb, A., Ultracomputer Note #100 (July 1986), Courant Institute
[7] Greenbaum, A., Ultracomputer Note #99 (April 1986), Courant Institute
[8] Hestenes, M.; Stiefel, E., J. Res. NBS, 49, 409 (1952)
[9] Kershaw, D. S., J. Comput. Phys., 26, 43 (1978)
[10] Keyes, D. E.; Gropp, W. D., SIAM J. Sci. Stat. Comput., 8, s166 (1987)
[11] Meijerink, J. A.; van der Vorst, H. A., Math. Comput., 148 (1977)
[12] Sameh, S. H.; Brent, R. P., SIAM J. Numer. Anal., 14, 1101 (1979)
[13] van der Sluis, A., Numer. Math., 14, 14 (1969)
[14] Widlund, O., (Technical Report #260 (November 1986), Courant Institute)
[15] (Proc. First. Intern. Conf. on Domain Decomposition Methods. Proc. First. Intern. Conf. on Domain Decomposition Methods, Paris (1987)), to appear in
[16] Yserentant, H., Numer. Math., 49, 379 (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.