Qual é a maneira mais rápida de calcular todos os autovalores de uma matriz de adjacência muito grande e esparsa em python?

Estou tentando descobrir se existe uma maneira mais rápida de calcular todos os autovalores e autovetores de uma matriz de adjacência muito grande e esparsa do que usar scipy.sparse.linalg.eigsh Até onde eu sei, esse método usa apenas a escassez e atributos de simetria da matriz. Uma matriz de adjacência também é binária, o que me faz pensar que há uma maneira mais rápida de fazer isso.

Criei uma matriz de adjacência esparsa aleatória 1000x1000 e comparei entre vários métodos no meu laptop x230 ubuntu 13.04:

• scipy.sparse.linalg.eigs: 0.65 segundos
• scipy.sparse.linalg.eigsh: 0.44 segundos
• scipy.linalg.eig: 6.09 segundos
• scipy.linalg.eigh: 1.60 segundos

Com os eigs esparsos e eigsh, eu defino k, o número dos valores próprios e dos vetores próprios desejados, para ser a classificação da matriz.

O problema começa com matrizes maiores - em uma matriz de 9000 x 9000, foram necessários 45 minutos para scipy.sparse.linalg.eigsh!

FILTLAN é uma biblioteca C ++ para calcular autovalores interiores de matrizes simétricas esparsas. O fato de haver todo um pacote dedicado a isso deve dizer que é um problema bastante difícil. Encontrar os maiores ou menores valores próprios de uma matriz simétrica pode ser feito deslocando / invertendo e usando o algoritmo de Lanczos, mas o meio do espectro é outra questão. Se você quiser usar isso, poderá usar o SWIG para chamar um programa C ++ a partir do python.

Se seu objetivo final é calcular grandes potências da matriz, você pode apenas calcular autovetores correspondentes aos maiores autovalores, contando que os modos menores serão menos importantes à medida que você usa grandes potências.

$k$

Perdoe-me se estas já são óbvias para você: você pode explorar a natureza binária da matriz dizendo a numpy que ela consiste em números inteiros em vez de flutuadores, digamos usando

a = np.zeros(100,dtype=np.uint)

$A^{16}$$A^2$$A^4$$A^8$$\approx\log_2 k$$k$

Você também pode explorar a chamada de uma biblioteca de álgebra linear esparsa paralela, como CUSP ou cuSPARSE, do Python, se a velocidade for sua preocupação e você tiver uma GPU NVIDIA.

Gostaria de comentar a resposta de Daniel Shapero, mas não tenho reputação suficiente de SE.

A resposta aceita me confunde muito. Acho que o modo shift-invert pode ser facilmente usado para calcular valores próprios internos. Veja: https://docs.scipy.org/doc/scipy/reference/tutorial/arpack.html

Para responder à pergunta original: raramente é o caso de você querer todos os autovalores de uma grande matriz esparsa. Geralmente, você deseja extrems ou algum conjunto de valores internos. Nesse caso, para uma matriz hermitiana eigshé mais rápido. Para não-eremita, você terá que concordar eigs. E eles são muito mais rápidos que entorpecidos eigou eigh.