Implementation and performance evaluation of new inverse iteration algorithm with Householder transformation in terms of the compact WY representation
Hiroyuki Ishigami, Kimura Kinji, Yoshimasa Nakamura · 研究報告数理モデル化と問題解決（MPS） · 2011
A new inverse iteration algorithm that can be used to compute all the eigenvectors of a real symmetric tridiagonal matrix on parallel computers is developed. In the classical inverse iteration algorithm, the modified GramSchmidt orthogonalization is used, and this causes a bottleneck in parallel computing. In this paper, the use of the compact WY representation is proposed in the orthogonalization process of the inverse iteration algorithm with the Householder transformation. This change results in drastically reduced synchronization cost in parallel computing. The new algorithm is evaluated on a 32-core parallel computer, and it is shown that the algorithm is up to 7.46 times faster than the classical algorithm in computing all the eigenvectors of matrices with several thousand dimensions.