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, multishift QR algorithm, bulge-chasing, performance modeling.
AB - <p style="text-align: justify;">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.</p>