| Автор | Kim, S.K. |
| Автор | Chronopoulos, A.T. |
| Дата выпуска | 1992 |
| dc.description | 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. |
| Издатель | Sage Publications |
| Название | An Efficient Parallel Algorithm for Extreme Eigenvalues of Sparse Nonsymmetric Matrices |
| Тип | Journal Article |
| DOI | 10.1177/109434209200600411 |
| Print ISSN | 1094-3420 |
| Журнал | International Journal of High Performance Computing Applications |
| Том | 6 |
| Первая страница | 407 |
| Последняя страница | 420 |
| Аффилиация | Kim, S.K., DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF MINNESOTA MINNEAPOLIS, MINNESOTA 55455 |
| Аффилиация | Chronopoulos, A.T., DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF MINNESOTA MINNEAPOLIS, MINNESOTA 55455 |
| Выпуск | 4 |
| Библиографическая ссылка | 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 Computing1985 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. |
| Библиографическая ссылка | 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. |
| Библиографическая ссылка | Ranka, S., Won, Y., and Sahni, S.1988. Programming the NCUBE Hypercube. Tech. Rep. CSci No. 88-13. Minneapolis: University of Minnesota. |
| Библиографическая ссылка | Ruhe, A.1982. The two sided Arnoldi algorithm for nonsymmetric eigenvalue problems. Springer-VerlagLecture Notes in Math . 973:104-120. |
| Библиографическая ссылка | Saad, Y.1980. Variation on the Arnoldi's method for computing eigenelements of large unsymmetric matrices. Linear Algebra Appl.34:269-295. |
| Библиографическая ссылка | Saad, Y.1984. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Math. Comp.42:567-588. |
| Библиографическая ссылка | Saad, Y.1985. Partial eigensolutions of large nonsymmetric matrices. Research Report YALUE/ DCS/RR-397. |
| Библиографическая ссылка | Saylor, P.E.1988. Leapfrog variants of iterative methods for linear algebraic equations. J. Comput. Appl. Math.24:169-193. |
| Библиографическая ссылка | Wilkinson, J.H.1965. The algebraic eigenvalue problem. New York: Oxford University Press. |
