An Efficient Parallel Algorithm for Extreme Eigenvalues of Sparse Nonsymmetric Matrices

Abstract

Main memory accesses for shared-memory systems or global communications (synchronizations) in message passing systems decrease the computation speed. In this paper, the standard Arnoldi algorithm for approxi mating a small number of eigenvalues, with largest (or smallest) real parts for nonsymmetric large sparse ma trices, is restructured so that only one synchronization point is required; that is, one global communication in a message passing distributed-memory machine or one global memory sweep in a shared-memory ma chine per each iteration is required. We also introduce an s-step Arnoldi method for finding a few eigenvalues of nonsymmetric large sparse matrices. This method generates reduction matrices that are similar to those generated by the standard method. One iteration of the s-step Arnoldi algorithm corresponds to s itera tions of the standard Arnoldi algorithm. The s-step method has improved data locality, minimized global communication, and superior parallel properties. These algorithms are implemented on a 64-node NCUBE/7 Hypercube and a CRAY-2, and performance results are presented.

Get full access to this article

View all access options for this article.

References

Aykanat, C. , Ozguner, F. , Ercal, F. , and Sadayappan, P. 1988. Iterative algorithms for solution of large sparse systems of linear equations on Hypercubes. IEEE Trans. Comput. 37 (12):1554-1568.

Chronopoulos, A.T. , and Gear, C.W. 1989a. S-step iterative methods for symmetric linear systems . J. Comput. Appl. Math. 25:153-168.

Chronopoulos, A.T. , and Gear, C.W. 1989b. On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy . Parallel Comput. 11:37-52.

Dave, A.K. , and Duff, I.S. 1987. Sparse matrix calculations on the CRAY-2. Parallel Comput. 5:55-64.

Dongarra, J.J. , and Sorensen, D.C. 1986. Linear algebra on high-performance computer. Conf. Parallel Computing 1985 proceed. M. Feilmeier et al. eds. Elsevier Pub . 1986.

Golub, G.H. , and Van Loan, C.F. 1989. MATRIX Computations. Baltimore : Johns Hopkins University Press, pp. 219-225.

Gustafson, J.L. , Montry, G.R. , and Benner, R.E. 1988. Development of parallel methods for a 1024-processor hypercube . SIAM J. Sci. Statist. Comput. 9(4).

Kim, S.K. , and Chronopoulos, A.T. 1991. A class of Lanczos algorithms implemented on parallel computers. Parallel Comput. 17. Meurant , G. 1987. Multitasking the conjugate gradient method on the CRAY X-MP/48 . Parallel Comput. 5:267-280.

McBryan, O.A. , and van de Velde, E.F. 1987. Matrix and vector operations on hypercube parallel processors. Parallel Comput. 5:117-125.

10.

Ni, L.M. , King, C.T. , and Prins, P. 1987. Parallel algorithm design considerations for hypercube multiprocessors. Proc. of the 1987 International Conf. on Parallel Processing.

11.

Ranka, S. , Won, Y. , and Sahni, S. 1988. Programming the NCUBE Hypercube. Tech. Rep. CSci No. 88-13. Minneapolis: University of Minnesota.

12.

Ruhe, A. 1982. The two sided Arnoldi algorithm for nonsymmetric eigenvalue problems. Springer-Verlag Lecture Notes in Math . 973:104-120.

13.

Saad, Y. 1980. Variation on the Arnoldi's method for computing eigenelements of large unsymmetric matrices. Linear Algebra Appl. 34:269-295.

14.

Saad, Y. 1984. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Math. Comp. 42:567-588.

15.

Saad, Y. 1985. Partial eigensolutions of large nonsymmetric matrices. Research Report YALUE/ DCS/RR-397.

16.

Saylor, P.E. 1988. Leapfrog variants of iterative methods for linear algebraic equations. J. Comput. Appl. Math. 24:169-193.

17.

Wilkinson, J.H. 1965. The algebraic eigenvalue problem. New York: Oxford University Press.