行列Aが与えられたとき,
Ax=λx, x≠0
を満たす固有値λ,固有ベクトルxを求める問題を標準固有値問題という.
Googleのページランク計算は固有値問題が関連している.ページランクとは,webページの
表示順に関連する値で,ある行列の絶対値最大固有値1に対応する固有ベクトルの成分で
ある.よって,ページランク計算は行列の固有ベクトルを求める必要がある.
固有値が既知である特徴を生かして近年,Refined-Arnoldi法が提案された.これは,Krylov
部分空間を生成し,その中で近似的に固有ベクトルを構築する解法である.
Refined-Arnoldi法は部分空間を徐々に拡大していき,近似固有ベクトルを真の固有ベクトル
に近づける.しかし,部分空間を増大するごとに計算量が多くなり,計算時間も増大する.
そこでリスタートという方法が必要となる.これは,部分空間を一定次元ごとに生成し,計算量
を抑える方法である.本発表では,リスタートによる収束性の違いを示す.
今後の展望として,リスタートに焦点を当てる.Refined-Arnoldi法は,線形方程式の解法の
一つであるGMRES法と,部分空間の生成や近似固有ベクトルの構築の点で共通している.
この事実に着目し,これまでに提案されたGMRES法のリスタートに関する拡張をRefined-
Arnoldi法に適用することが可能となる.これにより,ページランク計算に対する更なる高速
解法の開発を行う.