計算k個最大特徵值和對應特徵向量的最快方法

Question

我有一個大的NxN稠密對稱矩陣，並且希望特徵向量對應於k個最大特徵值。找到它們的最好方法是什麼（最好是使用numpy，但如果這是唯一的方法，可能通常使用blas/atlas/lapack）？通常N比k大得多（例如N> 5000，k < 10）。

如果我的起始矩陣是稀疏的，Numpy似乎只能找到k個最大的特徵值。

Answer 1

在SciPy中，可以使用linalg.eigh函數和eigvals參數。

eigvals：元組（LO，HI）的最小和最大（在 升序）特徵值的索引和相應的特徵向量是 返回：0 < = LO <喜< = M-1。如果省略，則返回所有特徵值和特徵向量。

你的情況應該設置爲(N-k,N-1)。

Answer 2

其實稀疏例程密集numpy的陣列的工作還可以，我認爲他們使用一些 樣的Krylov子空間迭代的，因此，他們需要計算幾個矩陣向量 產品，這意味着，如果說明您的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