1

固有値、固有ベクトルの 計算速度 と アルゴリズム


行列の固有値、固有ベクトルを求めるには、行列の次元数をNとするとN3 に比例した時間がかかる。

現在、研究室のワークステーションで行列の固有値、固有ベクトルを求めるのにかかる時間を下に示す。

計算プログラムは八木さんが作成したものもの。
計算する行列は、値がランダムの対称行列、行列の次元数は N
※ランダムといってもNが同じならば要素はいつも等しくなっている。

host名 プロセッサ 動作クロック 搭載メモリ 次元数 計算時間
------------------------------------------------------
soot  sparc     70MHz     57Mbyte  N=1000 約1000 秒
rope  ultra-sparc  170MHz    384Mbyte  N=1000 約 200 秒
                        N=2000 約1600 秒
また、物性研のスパコン ( 但し並列化していない )の場合
   ※スペックは調べていません         N=1000 約 30 秒
------------------------------------------------------
※メモリのビット幅も異なっているので、計算速度は動作クロック
だけでは決まらない。

次元数 N=10000 で 約1000秒 で計算するというのが、
本研究の目標にしている、専用LSIを用いた計算機の能力である。
これは、N=1000 で 計算時間 約 1秒に相当する。


対称行列の固有値、固有ベクトルを求めるのに下の方法を用いる。

  1. ハウスホルダー変換 をして、三重対角化する
  2. 二分法により固有値を求る
  3. 逆反復法により三重対角行列の固有ベクトルを求る
  4. そのベクトルを、ハウスホルダ変換の逆変換により元の対称行列の固有ベクトルを求める。

ハウスホルダー変換とは、相似変換(固有値が変わらない)により、対称行列を、固有値を求め易い、3重対角行列にすることである。
またこの3重対角行列は固有ベクトルも計算しやすくなる。元の行列の固有ベクトルではないが、ハウスホルダ変換の時の相似変換を逆に行えば、元の対称行列の固有ベクトルになる。