- ベストアンサー
固有ベクトルの高速な求め方
- 固有ベクトルの求め方について調査しました。現在の手法では時間がかかるため、高速なアルゴリズムを探しています。
- 現在固有ベクトルを求める手法は遅く、特に大きな行列の場合は時間がかかります。高速なアルゴリズムの開発が望まれます。
- 対称行列の固有ベクトルを効率的に求める方法を探しています。現在の手法では時間がかかるため、高速化のためのアルゴリズムを研究中です。
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
一つ気づいたのですが、もしかして500個の固有値を全部求めていませんか？。そうすると全体で30分（1800秒）だとしても、1個あたりなら、ほんの数秒で、かなり優秀なコードと思えます。 ふつうは、低次の固有値・固有ベクトルを重視するので、せいぜい10個，多くて20個と思います。さっきの話が正しいとして、それなら数10秒です。 もし500個の固有値という事であれば、共役勾配法を利用した原点移動付逆ベキ乗法を試すしかないかな？、と思いました。
その他の回答 (1)
PCの性能にもよりますが、500×500の行列のLU分解に30分というのは、遅すぎると思いました。例えばLU分解に無駄はないでしょうか？。1回で済むところを、Loop手順の誤りで、毎回実行しているとか。 LU分解が正当だとして、対称行列ならば、原点移動付逆ベキ乗法があります。 これは具体的には、(Ａ－λＥ)x＝xを繰り返し解く操作に帰着します。det(Ａ－λＥ)はほぼ0になるので、Ａ－λＥの上三角化において0に近い対角成分がみつかったら、それを10^(-10)とかにおきかえて計算を続行します。得られたxのノルムを1に規格化して、これを数回行うと、xはほぼ固有ベクトルに収束します。xの初期値としては、x＝(1，1，・・・，1)なんかを選びます。 Ａ－λＥの上三角化は、固定したλに対して1回だけ行い、保存して繰り返し使用できます。これはLU分解1回と同じです。 それでも遅い場合には、上三角化のかわりに共役勾配法を利用できます。共役勾配法は非常に高速です。 参考文献： 行列計算ソフトウェア WS、スーパーコン、並列計算機 フロッピーディスク付（3.5inch2HD） 小国 力 編著 発行元：丸善(株)出版事業部 この本は古いですが、工学系の図書館には必ずあると思います。また小国さんの他の著書も参考になります。
お礼
返答遅れてしまって申し訳ありませんでした。 ちょっと質問の文章があいまいでしたね。すみません。 500×500の行列のLU分解に30分かかっているわけではなく、すべての固有値に対応する固有ベクトルを求めるのに30分必要になるという意味です。 詳しいことは2回目の回答のお礼に書きますね＾＾
お礼
あらためて、返答ありがとうございました。 ddtddtddtさんがおっしゃられた通り、500個のすべての固有値を求めています。 それは特異値分解、主成分分析といわれる手法ではすべての固有値と固有ベクトルが必要だからです。そして自分は今大学でその研究をしているからです。 固有値を求めるプログラムは正直自分でも驚くほど高速に求めることができました。固有値を高速に求めるにはQR法を高速に処理する問題になりますが、大概の専門書でのプログラムにおいて、そのなかで計算しなくてもよい部分を発見したため、それにより高速に求めることができました。しかも計算しなくてよい部分は行列の大きさの大体を占めているため、とても高速になります。 アルゴリズム自体は変わらないんですがね。 固有値を求めた後、ひとつの固有値に対してLU分解を行い固有ベクトルを求めますが、固有ベクトルは並列的に計算が可能なため、CPUをフルに活用することができます。 自分のPC環境は Xeon 2.8GHz ですので、シングルコアのマルチスレッディングで2スレッドで計算を行いました。 紹介していただいた参考書、および「共役勾配法を利用した原点移動付逆ベキ乗法」を試してみたいと思います。 ありがとうございました＾＾