Quel est le moyen le plus rapide de trouver des valeurs/vecteurs propres en python ?

Question

Actuellement, j'utilise numpy qui fait le travail. Mais, comme j'ai affaire à des matrices de plusieurs milliers de lignes/colonnes et que ce chiffre atteindra plus tard des dizaines de milliers, je me demandais s'il existait un paquetage capable d'effectuer ce type de calculs plus rapidement ?

Answer 1

• **Si votre matrice est éparse, instanciez votre matrice en utilisant un constructeur de scipy.sparse puis utiliser les méthodes analogues de vecteurs propres/valeurs propres en linalg épicé.clairsemé . Du point de vue des performances, cela présente deux avantages :

  • votre matrice, construite à partir du constructeur spicy.sparse, sera plus petite proportionnellement à sa faible densité.

  • le site méthodes des valeurs propres et des vecteurs propres pour les matrices éparses ( eigs , eigsh ) acceptent un argument facultatif, k qui est le nombre de paires vecteur propre/valeur propre que vous voulez obtenir. Presque toujours, le nombre requis pour prendre en compte les plus de 99% de la variance est bien inférieur au nombre de colonnes, ce que vous pouvez vérifier. ex post En d'autres termes, vous pouvez demander à la méthode de ne pas calculer et de ne pas renvoyer tous les vecteurs propres ou paires de valeurs propres - au-delà du (généralement) petit sous-ensemble nécessaire pour tenir compte de la variance, il est peu probable que vous ayez besoin du reste.

• utiliser la bibliothèque d'algèbre linéaire dans SciPy , scipy.linalg au lieu de de la NumPy bibliothèque du même nom. Ces deux bibliothèques ont le même nom et utilisent les mêmes noms de méthodes. Pourtant, il y a une différence de performance. Cette différence est causée par le fait que numpy.linalg est un moins enveloppe fidèle sur les routines analogues de LAPACK qui sacrifient une partie des performances pour la portabilité et la commodité (c.-à-d, pour se conformer à la NumPy L'objectif de la conception est que l'ensemble du NumPy bibliothèque doit être construite sans le programme Fortran linalg sur SciPy sur d'autre part, est une enveloppe beaucoup plus complète de LAPACK et qui utilise f2py .

• sélectionnez la fonction appropriée à votre cas d'utilisation ; en d'autres termes, n'utilisez pas une fonction qui fait plus que ce dont vous avez besoin. Dans scipy.linalg il existe plusieurs fonctions pour calculer les valeurs propres ; les différences ne sont pas grandes, mais en choisissant soigneusement la fonction pour calculer les valeurs propres, vous devriez constater un gain de performance. Pour exemple :

  • scipy.linalg.eig renvoie à les deux les valeurs propres et vecteurs propres
  • scipy.linalg.eigvals ne renvoie que les valeurs propres. Donc, si vous n'avez besoin que des valeurs propres d'une matrice alors ne pas utiliser linalg.eig utiliser linalg.eigvals à la place.
  • si vous avez une matrice symétrique carrée à valeur réelle (égale à sa transposée), alors utilisez scipy.linalg.eigsh

• optimiser votre construction Scipy Préparation de votre environnement de construction SciPy s'effectue en grande partie dans l'interface de SciPy setup.py script. L'option la plus l'option la plus significative en termes de performances est d'identifier toute bibliothèques LAPACK optimisées telles que ATLAS ou le cadre Accelerate/vecLib (OS X seulement ?) afin que SciPy puisse les détecter et les construire. Selon la plate-forme dont vous disposez actuellement, l'optimisation de votre compilation SciPy puis la réinstallation peut vous donner une augmentation substantielle de la performance performances. Les notes supplémentaires de l'équipe SciPy sont les suivantes ici .

Ces fonctions fonctionneront-elles pour les grandes matrices ?

Je pense que oui. Il s'agit de méthodes de décomposition matricielle de niveau industriel, qui ne sont que de minces enveloppes pour les méthodes analogues de Fortran. LAPACK routines.

J'ai utilisé la plupart des méthodes de la bibliothèque linalg pour décomposer des matrices dont le nombre de colonnes est généralement compris entre 5 et 50, et dont le nombre de lignes dépasse généralement 500 000. Ni la SVD ni le valeur propre ne semblent pas avoir de problème à gérer des matrices de cette taille.

Utilisation de la SciPy bibliothèque linalg vous pouvez calculer les vecteurs propres et les valeurs propres, en un seul appel, en utilisant l'une des nombreuses méthodes de cette bibliothèque, eig , eigvalsh y eigh .

>>> import numpy as NP
>>> from scipy import linalg as LA

>>> A = NP.random.randint(0, 10, 25).reshape(5, 5)
>>> A
    array([[9, 5, 4, 3, 7],
           [3, 3, 2, 9, 7],
           [6, 5, 3, 4, 0],
           [7, 3, 5, 5, 5],
           [2, 5, 4, 7, 8]])

>>> e_vals, e_vecs = LA.eig(A)

Answer 2

Si vos matrices sont éparses, vous pouvez essayer d'utiliser la fonction sparse eigenvalue de scipy, qui devrait être plus rapide :

http://docs.scipy.org/doc/scipy/reference/sparse.linalg.html

Vous pouvez également consulter des paquets spécialisés comme SLEPc, qui a des liens avec python et peut effectuer des calculs en parallèle en utilisant mpi :

http://code.google.com/p/slepc4py/