python - numpy を使用して k 個の最大固有値と対応する固有ベクトルを計算する最速の方法

Question

大きな NxN 密対称行列があり、k 個の最大固有値に対応する固有ベクトルが必要です。それらを見つける最良の方法は何ですか（できればnumpyを使用しますが、それが唯一の方法である場合は一般的にblas/atlas/lapackを使用します）？一般に、N は k よりもはるかに大きい (たとえば、N > 5000、k < 10)。

Numpy には、開始行列がスパースの場合、k 個の最大固有値を見つけるための関数しかないようです。

Answer 1

SciPyでは、パラメーターを指定してlinalg.eigh関数を使用できeigvalsます。

eigvals：tuple（lo、hi）返される最小および最大（昇順）の固有値と対応する固有ベクトルのインデックス：0 <= lo <hi<=M-1。省略した場合、すべての固有値と固有ベクトルが返されます。

あなたの場合、どちらをに設定する必要があります(N-k,N-1)。

Answer 2

実際、スパースルーチンは密なnumpy配列でも機能します。ある種のクリロフ部分空間反復を使用するため、いくつかの行列ベクトル積を計算する必要があります。つまり、k << Nの場合、スパースルーチンは（わずかに？ ） もっと早く。

ドキュメントをチェックしてください http://docs.scipy.org/doc/scipy/reference/tutorial/arpack.html

そして次のコード（それが終わるまで友達とおいしいコーヒーを飲みに行く）

import numpy as np
from time import clock
from scipy.linalg import eigh as largest_eigh
from scipy.sparse.linalg.eigen.arpack import eigsh as largest_eigsh

np.set_printoptions(suppress=True)
np.random.seed(0)
N=5000
k=10
X = np.random.random((N,N)) - 0.5
X = np.dot(X, X.T) #create a symmetric matrix

# Benchmark the dense routine
start = clock()
evals_large, evecs_large = largest_eigh(X, eigvals=(N-k,N-1))
elapsed = (clock() - start)
print "eigh elapsed time: ", elapsed

# Benchmark the sparse routine
start = clock()
evals_large_sparse, evecs_large_sparse = largest_eigsh(X, k, which='LM')
elapsed = (clock() - start)
print "eigsh elapsed time: ", elapsed