The behavior of conjugate gradient algorithms on a multivector processor with a hierarchical memory. (English) Zbl 0738.65027
Summary: An analysis of some of the tradeoffs involved in the design and efficient implementation of conjugate gradient-based algorithms for a multivector processor with a two-level memory hierarchy is presented and supplemented by experimental results obtained on an Alliant FX/8. The algorithms considered consist of the classical conjugate gradient method, preconditioning techniques that are well suited for parallel computers such as polynomial preconditioners and several versions of the incomplete Cholesky preconditioners as well as the reduced system approach. For linear systems arising from the 5-point finite difference discretization of second order self-adjoint elliptic partial differential equations, the analysis shows that conjugate gradient methods do not perform as well as algorithms for dense matrix computations on the considered architecture due to lack of data locality. By using the reduced system approach, however, a significant decrease in time could be obtained.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65Y05 | Parallel numerical computation |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 35J25 | Boundary value problems for second-order elliptic equations |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
Keywords:
multivector processor; Alliant FX/8; conjugate gradient method; preconditioning; parallel computers; incomplete Cholesky preconditioners; finite difference; reduced system; well-structured sparseReferences:
| [1] | Axelsson, O., A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT, 166-187 (1985) · Zbl 0566.65017 |
| [2] | Buchberger, B.; Emelyneko, G., Methods of inverting tridiagonal matrices, USSR Comput. Math. & Math. Phys., 13, 10-20 (1973) · Zbl 0281.65023 |
| [3] | Concus, P.; Golub, G. H.; Meurant, G., Block preconditioning for the conjugate gradient method, SIAM J. Sci. Stat. Comput., 6, 220-252 (1985) · Zbl 0556.65022 |
| [4] | Ipsen, I.; Saad, Y., The impact of parallel architectures on the solution of eigenvalue problems, Research Report YALEU/DCS/RR-444 (1985), Yale University |
| [5] | Jalby, W.; Meier, U.; Hwang, K.; Jacobs, S. M.; Swartzlander, E. E., Optimizing matrix operations on a parallel multiprocessor with a two-level memory hierarchy, Proceedings of the 1986 International Conference on Parallel Processing, ICPP (1986), IEEE: IEEE Washington, D.C |
| [6] | Jalby, W.; Meier, U.; Sameh, A., The behavior of conjugate gradient methods on a multivector processor with a memory hierarchy, CSRD-Report 607 (1987), University of Illinois: University of Illinois Urbana-Champaign |
| [7] | Johnson, O. G.; Micchelli, C. A.; Paul, G., Polynomial preconditioners for conjugate gradient calculations, SIAM J. Numer. Anal., 20, 362-376 (1983) · Zbl 0563.65020 |
| [8] | Kamath, C.; Sameh, A., The preconditioned conjugate gradient algorithm on a multiprocessor, Technical Memorandum ANL/MCS-TM-28 (1984), Argonne National Laboratory |
| [9] | Meurant, G., The block preconditioned conjugate gradient method on vector computers, BIT, 24, 623-633 (1984) · Zbl 0556.65023 |
| [10] | Meurant, G., Numerical experiments for the preconditioned conjugate gradient method on the Cray X/MP/2, Technical Report LBL-18023 (1984), Lawrence Berkely Laboratory, University of California |
| [11] | Saad, Y., Practical use of polynomial preconditionings for the conjugate gradient method, SIAM J. Sci. Stat. Comput., 6, 865-881 (1985) · Zbl 0601.65019 |
| [12] | van der Vorst, H., A vectorizable variant of some ICCG methods, SIAM J. Sci. Stat. Comput., 3, 350-356 (1982) · Zbl 0484.65018 |
| [13] | van der Vorst, H., The performance of Fortran implementations for preconditioned conjugate gradients on vector computers, Parallel Computing, 3, 49-58 (1986) · Zbl 0608.65021 |
| [14] | van der Vorst, H., (M)ICCG for 2d problems on vectorcomputers, Technical Report (1986), Data Processing Center, Kyoto University: Data Processing Center, Kyoto University Japan · Zbl 0664.65028 |
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.
