Volume 1, Issue 2
Optimization of the Multishift QR Algorithm with Coprocessors for Non-Hermitian Eigenvalue Problems

Takafumi Miyata, Yusaku Yamamoto, Takashi Uneyama, Yoshimasa Nakamura & Shao-Liang Zhang

East Asian J. Appl. Math., 1 (2011), pp. 187-196.

Published online: 2018-02

Preview Full PDF 92 1387
Export citation
  • Abstract

The multishift QR algorithm is efficient for computing all the eigenvalues of a dense, large-scale, non-Hermitian matrix. The major part of this algorithm can be performed by matrix-matrix multiplications and is therefore suitable for modern processors with hierarchical memory. A variant of this algorithm was recently proposed which can execute more computational parts by matrix-matrix multiplications. The algorithm is especially appropriate for recent coprocessors which contain many processor-elements such as the CSX600. However, the performance of the algorithm highly depends on the setting of parameters such as the numbers of shifts and divisions in the algorithm. Optimal settings are different depending on the matrix size and computational environments. In this paper, we construct a performance model to predict a setting of parameters which minimizes the execution time of the algorithm. Experimental results with the CSX600 coprocessor show that our model can be used to find the optimal setting.

  • Keywords

Eigenvalues multishift QR algorithm bulge-chasing performance modeling

  • AMS Subject Headings

65F15 65Y10 65Y20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{EAJAM-1-187, author = {Takafumi Miyata, Yusaku Yamamoto, Takashi Uneyama, Yoshimasa Nakamura and Shao-Liang Zhang}, title = {Optimization of the Multishift QR Algorithm with Coprocessors for Non-Hermitian Eigenvalue Problems}, journal = {East Asian Journal on Applied Mathematics}, year = {2018}, volume = {1}, number = {2}, pages = {187--196}, abstract = {

The multishift QR algorithm is efficient for computing all the eigenvalues of a dense, large-scale, non-Hermitian matrix. The major part of this algorithm can be performed by matrix-matrix multiplications and is therefore suitable for modern processors with hierarchical memory. A variant of this algorithm was recently proposed which can execute more computational parts by matrix-matrix multiplications. The algorithm is especially appropriate for recent coprocessors which contain many processor-elements such as the CSX600. However, the performance of the algorithm highly depends on the setting of parameters such as the numbers of shifts and divisions in the algorithm. Optimal settings are different depending on the matrix size and computational environments. In this paper, we construct a performance model to predict a setting of parameters which minimizes the execution time of the algorithm. Experimental results with the CSX600 coprocessor show that our model can be used to find the optimal setting.

}, issn = {2079-7370}, doi = {https://doi.org/10.4208/eajam.300510.250311a}, url = {http://global-sci.org/intro/article_detail/eajam/10903.html} }
TY - JOUR T1 - Optimization of the Multishift QR Algorithm with Coprocessors for Non-Hermitian Eigenvalue Problems AU - Takafumi Miyata, Yusaku Yamamoto, Takashi Uneyama, Yoshimasa Nakamura & Shao-Liang Zhang JO - East Asian Journal on Applied Mathematics VL - 2 SP - 187 EP - 196 PY - 2018 DA - 2018/02 SN - 1 DO - http://doi.org/10.4208/eajam.300510.250311a UR - https://global-sci.org/intro/article_detail/eajam/10903.html KW - Eigenvalues KW - multishift QR algorithm KW - bulge-chasing KW - performance modeling AB -

The multishift QR algorithm is efficient for computing all the eigenvalues of a dense, large-scale, non-Hermitian matrix. The major part of this algorithm can be performed by matrix-matrix multiplications and is therefore suitable for modern processors with hierarchical memory. A variant of this algorithm was recently proposed which can execute more computational parts by matrix-matrix multiplications. The algorithm is especially appropriate for recent coprocessors which contain many processor-elements such as the CSX600. However, the performance of the algorithm highly depends on the setting of parameters such as the numbers of shifts and divisions in the algorithm. Optimal settings are different depending on the matrix size and computational environments. In this paper, we construct a performance model to predict a setting of parameters which minimizes the execution time of the algorithm. Experimental results with the CSX600 coprocessor show that our model can be used to find the optimal setting.

Takafumi Miyata, Yusaku Yamamoto, Takashi Uneyama, Yoshimasa Nakamura & Shao-Liang Zhang. (1970). Optimization of the Multishift QR Algorithm with Coprocessors for Non-Hermitian Eigenvalue Problems. East Asian Journal on Applied Mathematics. 1 (2). 187-196. doi:10.4208/eajam.300510.250311a
Copy to clipboard
The citation has been copied to your clipboard