| Title:
|
Experiments with Krylov subspace methods on a massively parallel computer (English) |
| Author:
|
Hanke, Martin |
| Author:
|
Hochbruck, Marlis |
| Author:
|
Niethammer, Wilhelm |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
38 |
| Issue:
|
6 |
| Year:
|
1993 |
| Pages:
|
440-451 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
massively parallel computers |
| Keyword:
|
iterative methods |
| Keyword:
|
nonsymmetric linear systems |
| Keyword:
|
Krylov subspace methods |
| Keyword:
|
preconditionings |
| Keyword:
|
parallel computation |
| Keyword:
|
Krylov subspace iterative methods |
| Keyword:
|
conjugate gradient type methods |
| Keyword:
|
BiCGStab |
| Keyword:
|
semiiterative methods |
| Keyword:
|
GMRES-Richardson method |
| Keyword:
|
successive overrelaxation |
| Keyword:
|
red-black ordering |
| MSC:
|
65F10 |
| MSC:
|
65W05 |
| MSC:
|
65Y05 |
| idZBL:
|
Zbl 0810.65030 |
| idMR:
|
MR1241447 |
| DOI:
|
10.21136/AM.1993.104566 |
| . |
| Date available:
|
2008-05-20T18:46:27Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/104566 |
| . |
| Reference:
|
[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. |
| Reference:
|
[2] M. Eiermann: On semiiterative methods generated by Faber polynomials.Numer. Math. 56 (1989), 139-156. Zbl 0678.65020, MR 1018298, 10.1007/BF01409782 |
| Reference:
|
[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. MR 0812617, 10.1007/BF01389454 |
| Reference:
|
[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. Zbl 0546.65010, MR 0736337, 10.1137/0721026 |
| Reference:
|
[5] R. W. Freund G. H. Golub, and N. M. Nachtigal: Iterative solution of linear systems.Acta Numerica 1 (1992), 57-100. MR 1165723, 10.1017/S0962492900002245 |
| Reference:
|
[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. MR 1201315, 10.1137/0914009 |
| Reference:
|
[7] R. W. Freund, N. M. Nachtigal: QMR: a quasi-minimal residual method for non-Hermitian linear systems.Numer. Math. 60 (1991), 315-339. Zbl 0754.65034, MR 1137197, 10.1007/BF01385726 |
| Reference:
|
[8] M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems.J. Res. Nat. Bur. Standards 49 (1952), 409-436. Zbl 0048.09901, MR 0060307, 10.6028/jres.049.044 |
| Reference:
|
[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. MR 0042791, 10.6028/jres.045.026 |
| Reference:
|
[10] T. A. Manteuffel: The Tchebychev iteration for nonsymmetric linear systems.Numer. Math. 28 (1977), 307-327. Zbl 0361.65024, MR 0474739, 10.1007/BF01389971 |
| Reference:
|
[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. MR 1168080, 10.1137/0613050 |
| Reference:
|
[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. Zbl 0657.65050, MR 1022970 |
| Reference:
|
[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. Zbl 0487.65018, MR 0703121, 10.1007/BF01390212 |
| Reference:
|
[14] J. M. Ortega: Introduction to Parallel and Vector Solution of Linear Systems.Plenum Press, New York, London, 1988. Zbl 0669.65017, MR 1106195 |
| Reference:
|
[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. Zbl 0599.65018, MR 0848568, 10.1137/0907058 |
| Reference:
|
[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. Zbl 0636.65025, MR 0928443, 10.1007/BF01934703 |
| Reference:
|
[17] G. Starke, R. S. Varga: A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations.Numer. Math. 64 (1993), 213-240. Zbl 0795.65015, MR 1199286, 10.1007/BF01388688 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0761.65023, MR 1149111, 10.1137/0913035 |
| Reference:
|
[20] R. S. Varga: Matrix Iterative Analysis.Prentice Hall, Englewood Cliffs, New Jersey, 1962. MR 0158502 |
| . |
