La multiplication de grandes matrices creuses provoque une erreur de mémoire

Question

J'ai un grand graphe simple G, qui a environ 100k noeud, et sa matrice d'adjacence A (creuse, symétrique et binaire). J'ai besoin de calculer (A*A).A, mais malheureusement A*A provoque une erreur de mémoire dans MATLAB. Y a-t-il un moyen efficace de le faire?

Note: J'ai essayé avec un format de matrice clairsemée.

Answer 1

Tout d'abord: je suppose que nnz(A) est assez faible. Je viens de tester cela avec nnz(A) = 9999963, et size(A) = 1000000x1000000. L'approche intuitive consiste à travailler avec les données en "morceaux". Prenez les 10000 premières colonnes (toutes les lignes) et les 10000 premières lignes (toutes les colonnes), les 10000 suivantes, les prochaines, etc. Je crois que cela devrait éviter les problèmes de mémoire.

Je viens de tester A*A, et j'ai eu les mêmes problèmes de mémoire que vous. Ce que j'ai fait était, convertir A en logique: A_logical = logical(A). Cela réduit la taille de votre matrice un peu. Notez, vous ne pouvez pas utiliser uint8 ou quelque chose de similaire, puisque les seuls types de données pris en charge par sparse sont logical et double.

Maintenant, A_logical*A_logical échoue avec le message d'erreur:

Error using * 
Both logical inputs must be scalar. 

Cependant, la quadrature d'une matrice logique fonctionne très bien:

A_square = A_logical^2; 

Note, le résultat de la A_logical^2 n'est pas un matrice logique, mais un double, de sorte que vous obtiendrez les bonnes valeurs, non seulement 1 et 0.

Cela a bien fonctionné pour moi, sans aucun problème de mémoire. L'ordinateur s'est arrêté pendant environ 20 secondes, donc c'est un calcul "difficile", mais ça a marché.