行列の固有値を計算するのにどれくらいの費用がかかりますか?
最高のアルゴリズムの複雑さは?
1000 x 1000 のマトリックスがある場合、実際にはどのくらいの時間がかかりますか? マトリックスがスパースであれば、それが役立つと思いますか?
固有値計算が終了しない場合はありますか?
ではR、次のおもちゃの例のように固有値を計算できます。
m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14 3
誰がそれが使用するアルゴリズムを知っていますか?
固有値を計算する他の (オープンソース) パッケージはありますか?
固有値計算のアルゴリズムのほとんどは、big-Oh（n ^ 3）にスケーリングされます。ここで、nは（対称および正方）行列の行/列の次元です。
現在までの最良のアルゴリズムの時間計算量を知るには、Scientific Computing/NumericalMethodsの最新の研究論文を参照する必要があります。
ただし、最悪の場合を想定した場合でも、1000x1000行列に対して少なくとも1000^3の操作が必要になります。
Rは、デフォルトでLAPACKルーチン（DSYEVR、DGEEV、ZHEEV、およびZGEEV）の実装を使用します。ただし、EISPACK = TRUEをパラメーターとして指定して、EISPACKのRS、RG、CH、およびCGルーチンを使用することもできます。
固有値計算に最も人気があり、優れたオープンソースパッケージはLAPACKとEISPACKです。
大きな行列では、通常、すべての固有値は必要ありません。上位数人に次元削減を (たとえば) 実行してもらいたいだけです。
標準アルゴリズムは、ARPACK に実装されているアーノルディ-ランチョス反復アルゴリズムです。
www.caam.rice.edu/software/ARPACK/
eigs には matlab インターフェイスがあります。
eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.
また、R インターフェイスも追加されました。
行列がスパースの場合に役立つと思いますか？
はい、スパース行列でうまく機能するアルゴリズムがあります。
例を参照してください：http：//www.cise.ufl.edu/research/sparse/
1000x1000 のマトリックスがある場合、実際にはどのくらいの時間がかかりますか?
MATLAB (LAPACK ベース) は、デュアルコア 1.83 GHz マシンで、1000x1000 ランダムのすべての固有値を約 5 秒で計算します。行列が対称の場合、計算は大幅に高速化され、約 1 秒しかかかりません。
固有値アルゴリズムを見てみましょう。これは、さまざまな方法にリンクしています。それらはすべて異なる特性を持ち、うまくいけば目的に適したものになるでしょう.
Apache Mahoutは、map-reduceに基づいて構築されたオープンソースフレームワークです（つまり、非常に大きなマトリックスで機能します）。多くのマトリックス関連の問題は、「ビッグオーランタイムとは何か」ではなく、「並列化可能性」であることに注意してください。Mahoutは、Lanczosを使用していると言います。これは、基本的に、必要な数のプロセッサで並行して実行できます。
QRアルゴを使用しています。Wilkinson、JH（1965）代数的固有値問題を参照してください。クラレンドンプレス、オックスフォード。スパース性を利用しません。