Calcul de l'inverse d'une très grande matrice

Question

J'essaie de calculer l'inverse d'une très grande matrice (11300x21500) en C++. Jusqu'à présent, j'ai essayé les bibliothèques Eigen et Armadillo, mais les deux ont échoué au stade de l'initialisation, en disant qu'il n'y a pas assez de mémoire. Peut-il y avoir un moyen de surmonter cette situation?

Merci à l'avance

P.S
je devrais corriger la taille de la matrice à 21500x21500. Comme l'a suggéré UmNyobe, il ne s'agit pas d'une matrice carrée. Il est en fait la matrice d'observation, X, et je suis en train de calculer (X^TX) ^-1

J'ai une mémoire de 8 Go (dans un système 64 bits), mais je ne pense pas que je me sers de tout cet espace de mémoire. Le gestionnaire de tâches montre que l'utilisation de la mémoire au moment de l'erreur est de 1 Go. Peut-être qu'il existe une commande OS dans Windows7 qui ferme une application lorsque son utilisation de la mémoire dépasse 1 Go. Par ailleurs, mon but initial était de faire une régression sur cette matrice d'observation.

Encore une chose: la plupart des colonnes de chaque ligne de la matrice d'observation X sont nulles. Peut-il y avoir un moyen de profiter de cela, pour limiter l'utilisation de la mémoire dans l'opération d'inversion?

Answer 1

Vous ne pouvez pas inverser une matrice non carrée.

http://en.wikipedia.org/wiki/Invertible_matrix

Answer 2

Supposant la matrice est carré, ce que vous cherchez probablement est un algorithme en place d'inversion de matrice. Vous devez vérifier this.

Answer 3

En supposant une matrice (11300 x 11300) de nombre entier (32 bits), vous avez

4*(11300^2)/(1024^3) = 0.4757 GB 

Si vous utilisez double précision puis doubler ce nombre.

Si la bibliothèque utilise l'algorithme de Strassen, qui nécessite une mémoire supplémentaire de même amplitude, vous doublez le nombre précédent.

Inverser une matrice à double base de cette taille avec Strassen ou Gaussian vous coûtera 1,9 Go.

Answer 4

Je voudrais proposer une autre solution, qui ne fonctionne que si vous n'êtes pas intéressé par l'inverse de la matrice elle-même mais par le produit de l'inverse avec un vecteur. Par exemple, supposons que vous souhaitiez trouver le produit de vos temps inverses un vecteur v, c'est-à-dire w := (X^T X)^{-1} v. Dans ce cas, vous êtes à la recherche en fait une solution au problème

Find w such that (X^T X) w = v 

En utilisant des algorithmes itératifs, il est possible de trouver w donné X et v dans l'équation ci-dessus sans inversionX. Une possibilité qui me vient à l'esprit est l'utilisation du Method of Conjugate Gradients.Cet algorithme peut être implémenté en environ 10 lignes et nécessite seulement de pouvoir calculer le produit (X^T X) y avec un vecteur donné y. Dans notre cas, cela peut même être fait en deux étapes, à savoir calculer z := X y et dans une seconde étape X^T z, ce qui économisera de l'espace car vous n'avez pas besoin de stocker le produit X^T X.

Answer 5

Bien que vous compiliez votre programme sur une machine 64 bits, vous devez également vous assurer que vous utilisez les bibliothèques 64 bits correctes. Sinon, le programme peut être compilé en 32 bits et vous aurez toujours les mêmes problèmes de mémoire. En ce qui concerne le calcul de l'inverse, la fonction inverse de OpenCV peut aider. Assurez-vous d'utiliser l'inverse de DECOMP_SVD, car je l'ai trouvé plus efficace avec des matrices quasi singulières.