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 approximating a small number of eigenvalues, with largest (or smallest) real parts for nonsymmetric large sparse matrices, 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 machine 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 iterations 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

, Ozguner

, Ercal

, and Sadayappan

1988. Iterative algorithms for solution of large sparse systems of linear equations on Hypercubes. IEEE Tram. 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. Feilmeier

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

1987. Multitasking the conjugate gradient method on the CRAY X-MP/48. Parallel Comput. 5:267-280.

10.

McBryan

O. A.

, and van de Velde

E. F.

1987. Matrix and vector operations on hypercube parallel processors. Parallel Comput. 5:117-125.

11.

L. M.

, King

C. T.

, and Prins

1987. Parallel algorithm design considerations for hypercube multiprocessors. Proc. of the 1987 International Conf. on Parallel Processing.

12.

Ranka

, Won

, and Sahni

1988. Programming the NCUBE Hypercube. Tech. Rep. CSci No. 88-13. Minneapolis: University of Minnesota.

13.

Ruhe

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

14.

Saad

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

15.

Saad

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

16.

Saad

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

17.

Saylor

P. E.

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

18.

Wilkinson

J. H.

1965. The algebraic eigenvalue problem. New York: Oxford University Press.