Article
Full entry |
PDF
(16.3 MB)
Feedback
PDF
(16.3 MB)
Feedback
Keywords:
massively parallel computers; iterative methods; nonsymmetric linear systems; Krylov subspace methods; preconditionings; parallel computation; Krylov subspace iterative methods; conjugate gradient type methods; BiCGStab; semiiterative methods; GMRES-Richardson method; successive overrelaxation; red-black ordering
massively parallel computers; iterative methods; nonsymmetric linear systems; Krylov subspace methods; preconditionings; parallel computation; Krylov subspace iterative methods; conjugate gradient type methods; BiCGStab; semiiterative methods; GMRES-Richardson method; successive overrelaxation; red-black ordering
Summary:
In this note, we compare some Krylov subspace iterative methods on the MASPAR, a massively parallel computer with 16K processors. In particular, we apply these methods to solve large sparse nonsymmetric linear systems arising from elliptic partial differential equations. The methods under consideration include conjugate gradient type methods, semiiterative methods, and a hybrid variant. Our numerical results show that, on the MASPAR, one should compare iterative methods rather on the basis of total computing time than on the basis of number of iterations required to achieve a given accuracy. Our limited numerical experiments here suggest that, in terms of total computing time, semiiterative and hybrid methods are very attractive for such MASPAR implementations.
References:
[1] D. Baxter J. Saltz M. Schultz S. Eisenstat, and K. Crowley: An experimental study of methods for parallel preconditioned Krylov methods. Tech. Rep. RR-629, Department of Computer Science, Yale University, 1988.
[2] M. Eiermann: On semiiterative methods generated by Faber polynomials. Numer. Math. 56 (1989), 139-156. DOI 10.1007/BF01409782 | MR 1018298 | Zbl 0678.65020
[3] M. Eiermann W. Niethammer, and R. S. Varga: A study of semiiterative methods for nonsymmetric systems of linear equations. Numer. Math. 47 (1985), 505-533. DOI 10.1007/BF01389454 | MR 0812617
[4] V. Faber, T. Manteuffel: Necessary and sufficient conditions for the existence of a conjugate gradient method. SIAM J. Numer. Anal. 21 (1984), 352-362. DOI 10.1137/0721026 | MR 0736337 | Zbl 0546.65010
[5] R. W. Freund G. H. Golub, and N. M. Nachtigal: Iterative solution of linear systems. Acta Numerica 1 (1992), 57-100. DOI 10.1017/S0962492900002245 | MR 1165723
[6] R. W. Freund M. H. Gutknecht, and N. M. Nachtigal: An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Statist. Comput. 14 (1993), 137-158. DOI 10.1137/0914009 | MR 1201315
[7] R. W. Freund, N. M. Nachtigal: QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60 (1991), 315-339. DOI 10.1007/BF01385726 | MR 1137197 | Zbl 0754.65034
[8] M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards 49 (1952), 409-436. DOI 10.6028/jres.049.044 | MR 0060307 | Zbl 0048.09901
[9] C. Lanczos: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Standards 45 (1950), 255-282. DOI 10.6028/jres.045.026 | MR 0042791
[10] T. A. Manteuffel: The Tchebychev iteration for nonsymmetric linear systems. Numer. Math. 28 (1977), 307-327. DOI 10.1007/BF01389971 | MR 0474739 | Zbl 0361.65024
[11] N. M. Nachtigal L. Reichel, L. N. Trefethen: A hybrid GMRES algorithm for nonsymmetric linear systems. SIAM J. Matrix Anal. Appl. 13 (1992), 796-825. DOI 10.1137/0613050 | MR 1168080
[12] W. Niethammer: Iterative solution of non-symmetric systems of linear equations. In: Numerical Mathematics, Singapore 1988 (R. P. Agarwal, Y. M. Chow and S. J. Wilson, eds.), Birkhäuser, Basel, 1988, pp. 381-390. MR 1022970 | Zbl 0657.65050
[13] W. Niethammer, R. S. Varga: The analysis of k-step iterative methods for linear systems from summability theory. Numer. Math. 41 (1983), 177-206. DOI 10.1007/BF01390212 | MR 0703121 | Zbl 0487.65018
[14] J. M. Ortega: Introduction to Parallel and Vector Solution of Linear Systems. Plenum Press, New York, London, 1988. MR 1106195 | Zbl 0669.65017
[15] Y. Saad, M. H. Schultz: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7 (1986), 856-869. DOI 10.1137/0907058 | MR 0848568 | Zbl 0599.65018
[16] D. C. Smolarski, P. E. Saylor: An optimum iterative method for solving any linear system with a square matrix. BIT 28 (1988), 163-178. DOI 10.1007/BF01934703 | MR 0928443 | Zbl 0636.65025
[17] G. Starke, R. S. Varga: A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations. Numer. Math. 64 (1993), 213-240. DOI 10.1007/BF01388688 | MR 1199286 | Zbl 0795.65015
[18] C. Tong: The preconditioned conjugate gradient method on the Connection Machine. In: Proceedings of the Conference on Scientific Applications of the Connection Machine (H. Simon, ed.), World Scientific, Singapore, New Jersey, London, Hong Kong, 1989, pp. 188-213. Zbl 0725.65033
[19] H. A. Van der Vorst: Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 13 (1992), 631-644. DOI 10.1137/0913035 | MR 1149111 | Zbl 0761.65023
[20] R. S. Varga: Matrix Iterative Analysis. Prentice Hall, Englewood Cliffs, New Jersey, 1962. MR 0158502
Search
Partner of
