×

zbMATH — the first resource for mathematics

Solution of large linear sparse systems by parallel iterative methods. (Résolution de grands systèmes linéaires creux par méthodes itératives parallèles.) (French) Zbl 0791.65015
In the conjugate gradient method, the parameters of the method have to be recomputed in every iteration step. The authors investigate conjugate gradient like methods which are obtained by using constant parameters. Such methods are much better suited for parallel execution. They show that the second order Richardson method relates to conjugate gradients in a similar fashion as does the first order Richardson method to the method of steepest descent. That means, by choosing optimal constant parameters, the rate of convergence is the same. Numerical experiments on the connection machine confirm the faster execution time for the Richardson method on parallel machines.
Reviewer: W.Gander (Zürich)

MSC:
65F10 Iterative numerical methods for linear systems
65Y05 Parallel numerical computation
Software:
LINPACK
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] S. F. ASHBY, T. A. MANTEUFFEL, P. E. SAYLOR, 1990, A Taxonomy For Conjugate Gradient Methods, Siam J. Numer. Anal., 27. Zbl0723.65018 MR1080338 · Zbl 0723.65018 · doi:10.1137/0727091
[2] J. Y. BLANC, 1991, Contribution du parallélisme à la résolution d’un problème de répartition de charge dans les réseaux électriques, Thèse de l’institut polytechnique de Grenoble.
[3] P. CONCUS, G. GOLUB, D. P. O’LEARY, 1984, A Generalized Conjugate Gradient for the Numerical Solution of Elliptic Partial Differential Equations, in Numerical Analysis, série SIAM. Zbl0595.65110 · Zbl 0595.65110
[4] D. DELESALLE, D. TRYSTRAM, D. WENZEK, 1990, Tout ce que vous voulez savoir sur la Connection Machine, Rapport de Recherche LMC-IMAG.
[5] L. DESBAT, 1990, Critères de Choix des Paramètres de Régularisation : Application à la déconvolution, Thèse de l’université Joseph Fourier, Annexe B : Gradient Conjugué et parallélisme.
[6] J. DEMMEL, J. J. DONGARRA, J. DUCROZ, A. GREENBAUM, S. J. HAMMARLING, D. C. SORENSEN, 1988, A project for developing a Linear Algebra Library for high-performance computer, Aspect of computation on asynchronous parallel processors, M. Wright.
[7] J. J. DONGARRA, I. S. DUFF, D. C. SORENSEN, H. A. VAN DER VORST, 1991, Solving Linear Systems on Vector and Shared Memory Computers, Siam. Zbl0770.65009 MR1084164 · Zbl 0770.65009
[8] J. J. DONGARRA, C. B. MOLER, J. R. BUNCH, G. W. STEWART, 1979, LINPACK user’s guide, Siam philadelphia. Zbl0476.68025 · Zbl 0476.68025
[9] M. J. FLYNN, 1972, Some computer organisations and their effectiveness, IEEE Trans. on Computers C-21, 9. Zbl0241.68020 · Zbl 0241.68020 · doi:10.1109/TC.1972.5009071
[10] G. FOX et al., 1988, Solving problems on concurrent processors : General techniques and regular problems (vol. I), Prentice-Hall.
[11] G. H. GOLUB, G. MEURANT, 1983, Résolution numérique des grands systèmes linéaires, Eyrolles Paris, collection CEA/EDF. Zbl0646.65022 MR756627 · Zbl 0646.65022
[12] G. H. GOLUB, R. S. VARGA, 1961, Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second other Richardson iterative methods, Part I et Part II, Numerische Mathematik. Zbl0099.10903 · Zbl 0099.10903 · doi:10.1007/BF01386013 · eudml:131486
[13] G. H. GOLUB, C. F. VAN LOAN, 1989, Matrix Computation, Second edition, Johns Hopkins. Zbl0733.65016 MR1002570 · Zbl 0733.65016
[14] J. GUSTAFSSON, G. LINDSKOG, 1986, A preconditioning technique based on element matrix factorisations, Comp. Meth. Appl. Mech. Engng., 55. Zbl0576.65022 MR844907 · Zbl 0576.65022 · doi:10.1016/0045-7825(86)90053-8
[15] A. L. HAGEMAN and D. M. YOUNG, 1981, Applied Iterative Methods, Academic Press. Zbl0459.65014 MR630192 · Zbl 0459.65014
[16] G. L. HENNIGANet al., 1989, A proposed domain decomposition technique for finite element on FPS T-serie, Proceedings of 4th Conf. Hypercube.
[17] M. HESTENES, E. STIEFEL, 1952, Methods of Conjugate Gradient for Solving Linear Systems, Journal Res. Nat. Bur. Stan., vol. 49. Zbl0048.09901 MR60307 · Zbl 0048.09901
[18] K. HWANG, F. A. BRIGGS, 1984, Computer Architecture and Parallel Processing, McGraw-Hill. Zbl0534.68006 · Zbl 0534.68006
[19] O. G. JOHNSON, C. A. MICCHELLI and G. PAUL, 1983, Polynomial Preconditionnings for Conjugate Gradient Calculations, SIAM J. Numer. Anal., vol. 20, pp. 362-376. Zbl0563.65020 MR694525 · Zbl 0563.65020 · doi:10.1137/0720025
[20] P. LASCAUX, R. THEODOR, 1987, Calcul matriciel appliqué à l’art de l’ingénieur, Masson. Zbl0601.65017 MR883208 · Zbl 0601.65017
[21] P. LAURENT-GENGOUX, D. TRYSTRAM, 1988, Parallel conjugate gradient algorithm with local decomposition, Rapport de recherche TIM3-IMAG.
[22] O. A. McBRYAN, 1989, Connection Machine Application Performance, Boulder Research report. Zbl0960.68527 · Zbl 0960.68527
[23] THINKING MACHINE CORPORATION, 1991, Connection Machine CM-200 Serie, Technical Summary.
[24] Y. SAAD, 1983Practical use of polynomial preconditionings for the conjugate gradient method, Yale Research report YALEU/DCS/RR-282. Zbl0601.65019 · Zbl 0601.65019 · doi:10.1137/0906059
[25] J. SALTZ, S. PETITON, H. BERRYMAN and A. RIFKIN, 1991, Performance effects of irregular communications patterns on massively parallel multiprocessors, NASA Contracter Report 187514.
[26] C. TONG, 1989, The Preconditioned Conjugate Gradient Method on the Connection Machine. Int. Jour. of Hight Speed Comp., vol. 1. Zbl0725.65033 · Zbl 0725.65033 · doi:10.1142/S0129053389000147
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.