Implementation and performance evaluation of new inverse iteration algorithm with Householder transformation in terms of the compact WY representation

摘要

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 Gram-Schmidt 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.