Parallel Eigenvalue Reordering in Real Schur Forms
2009 (English)In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 21, no 9, 1225-1250 p.Article in journal (Refereed) Published
A parallel algorithm for reordering the eigenvalues in the real Schur form of a matrix is presented and discussed. Our novel approach adopts computational windows and delays multiple outside-window updates until each window has been completely reordered locally. By using multiple concurrent windows the parallel algorithm has a high level of concurrency, and most work is level 3 BLAS operations. The presented algorithm is also extended to the generalized real Schur form. Experimental results for ScaLAPACK-style Fortran 77 implementations on a Linux cluster confirm the efficiency and scalability of our algorithms in terms of more than 16 times of parallel speedup using 64 processors for large-scale problems. Even on a single processor our implementation is demonstrated to perform significantly better compared with the state-of-the-art serial implementation.
Place, publisher, year, edition, pages
2009. Vol. 21, no 9, 1225-1250 p.
parallel algorithms;eigenvalue problems;invariant subspaces, direct reordering, Sylvester matrix equations, condition number estimates
Computer Science Software Engineering
IdentifiersURN: urn:nbn:se:umu:diva-24699DOI: 10.1002/cpe.1386OAI: oai:DiVA.org:umu-24699DiVA: diva2:227207