article

MR3-SMP: A symmetric tridiagonal eigensolver for multi-core architectures

Authors:

P. BientinesiAuthors Info & Claims

Parallel Computing, Volume 37, Issue 12

Pages 795 - 805

https://doi.org/10.1016/j.parco.2011.10.001

Published: 01 December 2011 Publication History

Abstract

The computation of eigenvalues and eigenvectors of symmetric tridiagonal matrices arises frequently in applications; often as one of the steps in the solution of Hermitian and symmetric eigenproblems. While several accurate and efficient methods for the tridiagonal eigenproblem exist, their corresponding implementations usually target uni-processors or large distributed memory systems. Our new eigensolver MR^3-SMP is instead specifically designed for multi-core and many-core general purpose processors, which today have effectively replaced uni-processors. We show that in most cases MR^3-SMP is faster and achieves better speedups than state-of-the-art eigensolvers for uni-processors and distributed-memory systems.

References

[1]

Bai, Z., Demmel, J., Dongarra, J., Ruhe, A. and van der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems - A Practical Guide. 2000. SIAM, Philadelphia.

[2]

Dhillon, I. and Parlett, B., Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. Linear Algebra Appl. v387. 1-28.

[3]

Dhillon, I. and Parlett, B., Orthogonal eigenvectors and relative gaps. SIAM J. Matrix Anal. Appl. v25. 858-899.

[4]

Demmel, J., Marques, O., Parlett, B. and Voemel, C., Performance and accuracy of LAPACK's symmetric tridiagonal eigensolvers. SIAM J. Sci. Comput. v30. 1508-1526.

[5]

Anderson, E., Bai, Z., Bishof, C., Demmel, J., Dongarra, J., Croz, J.D., Greenbaum, A., Hammarling, S., McKenney, A. and Sorensen, D., LAPACK Users' Guide. 1999. third ed. SIAM, Philadelphia.

[6]

Dhillon, I., Parlett, B. and Voemel, C., The design and implementation of the MRRR algorithm. ACM Trans. Math. Software. v32. 533-560.

Digital Library

[7]

Bientinesi, P., Dhillon, I. and van de Geijn, R., A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations. SIAM J. Sci. Comput. v21. 43-66.

[8]

Blackford, L.S., Choi, J., Cleary, A., D'Azevedo, E., Demmel, J., Dhillon, I.S., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D. and Whaley, R.C., ScaLAPACK Users' Guide. 1997. SIAM, Philadelphia.

[9]

Voemel, C., ScaLAPACK's MRRR algorithm. ACM Trans. Math. Software. v37.

[10]

Dongarra, J., Cruz, J.D., Duff, I. and Hammarling, S., A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Software. v16. 1-17.

Digital Library

[11]

Agullo, E., Demmel, J., Dongarra, J., Hadri, B., Kurzak, J., Langou, J., Ltaief, H., Luszczek, P. and Tomov, S., Numerical linear algebra on emerging architectures: The PLASMA and MAGMA projects. J. Phys.: Conf. Ser. v180.

[12]

Zee, F.G.V., Bientinesi, P., Low, T.M. and van de Geijn, R.A., Scalable parallelization of FLAME code via the workqueuing model. ACM Trans. Math. Software. v34. 10:1-10:29.

Digital Library

[13]

Quintana-Ortı¿, G., Quintana-Ortı¿, E.S., van de Geijn, R.A., Zee, F.G.V. and Chan, E., Programming matrix algorithms-by-blocks for thread-level parallelism. ACM Trans. Math. Software. v36.

[14]

C. Lessig, P. Bientinesi, On parallelizing the MRRR algorithm for data-parallel coprocessors, in: 8th Intern. Conf. on Parallel Proc. and Applied Math., PPAM, 2009.

[15]

Wilkinson, J., The calculation of the eigenvectors of codiagonal matrices. Comput. J. v1. 90-96.

[16]

J. Francis, The QR transform - a unitary analogue to the LR transformation, Part I and II, Comput. J. 4 (1961/1962).

[17]

Kublanovskaya, V., On some algorithms for the solution of the complete eigenvalue problem. Zh. Vych. Mat. v1. 555-572.

[18]

Cuppen, J., A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. v36. 177-195.

[19]

Gu, M. and Eisenstat, S.C., A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem. SIAM J. Matrix Anal. Appl. v16. 172-191.

[20]

Tisseur, F., Dongarra, J. and Dongarra, J., Parallelizing the divide and conquer algorithm for the symmetric tridiagonal eigenvalue problem on distributed memory architectures. SIAM J. Sci. Comput. v20. 2223-2236.

[21]

Lo, S.-S., Philippe, B. and Sameh, A., A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problem. SIAM J. Sci. Stat. Comput. v8. 155-165.

Digital Library

[22]

Ipsen, L.C.F. and Jessup, E.R., Solving the symmetric tridiagonal eigenvalues problem on the hypercube. SIAM J. Sci. Stat. Comput. v11. 203-229.

[23]

Parlett, B. and Dhillon, I., Relatively robust representations of symmetric tridiagonals. Linear Algebra Appl. v309. 121-151.

[24]

Demmel, J., Dhillon, I. and Ren, H., On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic. Electronic Trans. Numer. Anal. v3. 116-149.

[25]

Bernstein, H. and Goldstein, M., Parallel implementation of bisection for the calculation of eigenvalues of tridiagonal symmetric matrices. Computing. v37. 85-91.

[26]

Parlett, B. and Marques, O., An implementation of the DQDS algorithm (positive case). Linear Algebra Appl. v309. 217-259.

[27]

Rutishauser, H., Der quotienten-differenzen-algorithmus. Z. Angew. Math. Phys. v5. 223-251.

[28]

P. Willems, On MR3-Type Algorithms for the Tridiagonal Symmetric Eigenproblem and Bidiagonal SVD, Dissertation, University of Wuppertal, 2010.

[29]

Buttari, A., Langou, J., Kurzak, J. and Dongarra, J., Parallel tiled QR factorization for multicore architectures. Concurr. Comput.: Pract. Exp. v20. 1573G-1590.

[30]

Marques, O., Voemel, C., Demmel, J. and Parlett, B., Algorithm 880: a testing infrastructure for symmetric tridiagonal eigensolvers. ACM Trans. Math. Software. v35.

Cited By

Laudadio TMastronardi NDooren P(2024)On computing modified moments for half-range Hermite weightsNumerical Algorithms10.1007/s11075-023-01615-995:3(1435-1457)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11075-023-01615-9
Liao C(2016)Optimizing PLASMA eigensolver on large shared memory systemsProceedings of the 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems10.5555/3019094.3019104(73-80)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3019094.3019104
Tang GYang WLi KYe YXiao GLi K(2015)An iteration-based hybrid parallel algorithm for tridiagonal systems of equations on multi-core architecturesConcurrency and Computation: Practice & Experience10.1002/cpe.351127:17(5076-5095)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1002/cpe.3511

MR3-SMP: A symmetric tridiagonal eigensolver for multi-core architectures
1. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

The algorithm of multiple relatively robust representations for multi-core processors
PARA'10: Proceedings of the 10th international conference on Applied Parallel and Scientific Computing - Volume Part I

The algorithm of Multiple Relatively Robust Representations (MRRR or MR³) computes k eigenvalues and eigenvectors of a symmetric tridiagonal matrix in O(nk) arithmetic operations. Large problems can be effectively tackled with existing distributed-...
Accurate Symmetric Rank Revealing and Eigendecompositions of Symmetric Structured Matrices

We present new $O(n^3)$ algorithms that compute eigenvalues and eigenvectors to high relative accuracy in floating point arithmetic for the following types of matrices: symmetric Cauchy, symmetric diagonally scaled Cauchy, symmetric Vandermonde, and ...
Block Diagonalization and a Numerical Method of the Eigenproblem for an n×n Normal Matrix
CDEE '10: Proceedings of the 2010 First ACIS International Symposium on Cryptography, and Network Security, Data Mining and Knowledge Discovery, E-Commerce and Its Applications, and Embedded Systems

It is important that the eigenproblem of a matrix is solved in the matrix analysis and its engineering application. For a normal matrix with multiplex eigenvalues, a method of block diagonalization is given by using Householder transformation and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Parallel Computing

Parallel Computing Volume 37, Issue 12

December, 2011

125 pages

ISSN:0167-8191

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2011.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 December 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Laudadio TMastronardi NDooren P(2024)On computing modified moments for half-range Hermite weightsNumerical Algorithms10.1007/s11075-023-01615-995:3(1435-1457)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11075-023-01615-9
Liao C(2016)Optimizing PLASMA eigensolver on large shared memory systemsProceedings of the 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems10.5555/3019094.3019104(73-80)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3019094.3019104
Tang GYang WLi KYe YXiao GLi K(2015)An iteration-based hybrid parallel algorithm for tridiagonal systems of equations on multi-core architecturesConcurrency and Computation: Practice & Experience10.1002/cpe.351127:17(5076-5095)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1002/cpe.3511

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents