密行列固有値解法の最近の発展(I) : Multiple Relatively Robust Representationsアルゴリズム(<特集>行列・固有値問題における線形計算アルゴリズムとその応用)

概要

論文の詳細を見る
The Algorithm of Multiple Relatively Robust Representations (MR^3) is a new algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem proposed by I. Dhillon in 1997. It has attracted much attention because it can compute all the eigenvectors of an n×n matrix in only O(n^2) work and is easy to parallelize. In this article, we survey the papers related to the MR^3 algorithm and try to present a simple and easily understandable picture of the algorithm by explaining, one by one, its key ingredients such as the relatively robust representations of a symmetric tridiagonal matrix, the dqds algorithm for computing accurate eigenvalues and the twisted factorization for computing accurate eigenvectors. Limitations of the algorithm and directions for future research are also discussed.
日本応用数理学会の論文
2005-06-25