Quel est le moyen le plus rapide pour calculer toutes les valeurs propres d'une matrice d'adjacence très grande et clairsemée en python?

J'essaie de comprendre s'il existe un moyen plus rapide de calculer toutes les valeurs propres et vecteurs propres d'une matrice de contiguïté très grande et clairsemée que d'utiliser scipy.sparse.linalg.eigsh Pour autant que je sache, cette méthode utilise uniquement la rareté et attributs de symétrie de la matrice. Une matrice d'adjacence est également binaire, ce qui me fait penser qu'il existe un moyen plus rapide de le faire.

J'ai créé une matrice de contiguïté clairsemée de 1000x1000 et comparé plusieurs méthodes sur mon ordinateur portable Ubuntu 13.04 x230:

• scipy.sparse.linalg.eigs: 0,65 seconde
• scipy.sparse.linalg.eigsh: 0,44 secondes
• scipy.linalg.eig: 6,09 secondes
• scipy.linalg.eigh: 1,60 secondes

Avec les eigs et eigsh clairsemés, je fixe k, le nombre des valeurs propres et des vecteurs propres souhaités, comme étant le rang de la matrice.

Le problème commence avec des matrices plus grandes - sur une matrice 9000x9000, il a fallu 45 minutes à scipy.sparse.linalg.eigsh!

FILTLAN est une bibliothèque C ++ pour calculer les valeurs propres intérieures de matrices symétriques clairsemées. Le fait qu'il existe un ensemble complet consacré à cela devrait vous dire que c'est un problème assez difficile. Trouver les plus grandes ou les plus petites valeurs propres d'une matrice symétrique peut être fait en décalant / inversant et en utilisant l'algorithme de Lanczos, mais le milieu du spectre est une autre affaire. Si vous voulez l'utiliser, vous pouvez utiliser SWIG pour appeler un programme C ++ à partir de python.

Si votre objectif final est de calculer de grandes puissances de la matrice, vous pouvez simplement calculer des vecteurs propres correspondant aux plus grandes valeurs propres, sachant que les petits modes seront moins importants lorsque vous prendrez de grandes puissances.

$k$

Pardonnez-moi si ceux-ci sont déjà évidents pour vous: vous pouvez exploiter la nature binaire de la matrice en disant à numpy qu'elle est constituée d'entiers au lieu de flottants, par exemple en utilisant

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

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

Vous pouvez également explorer la possibilité d'appeler une bibliothèque d'algèbre linéaire clairsemée parallèle comme CUSP ou cuSPARSE à partir de Python si la vitesse est votre préoccupation et que vous avez un GPU NVIDIA.

Je voudrais commenter la réponse de Daniel Shapero mais je n'ai pas assez de réputation SE.

La réponse acceptée me confond beaucoup. Je pense que le mode inversion de décalage peut être facilement utilisé pour calculer les valeurs propres intérieures. Voir: https://docs.scipy.org/doc/scipy/reference/tutorial/arpack.html

Pour répondre à la question d'origine: il est rare que vous souhaitiez toutes les valeurs propres d'une grande matrice clairsemée. Généralement, vous voulez des extrems ou un groupe de valeurs intérieures. Dans ce cas, pour une matrice hermitienne, eigshc'est plus rapide. Pour les non-hermitiens, vous devrez y aller eigs. Et ils sont beaucoup plus rapides que numpy eigou eigh.