Quelle est la meilleure façon de déterminer le nombre de non zéros dans la multiplication matricielle clairsemée?

Je me demandais s'il existe une méthode rapide et efficace pour trouver à l'avance le nombre de non-zéros pour une opération de multiplication matricielle clairsemée en supposant que les deux matrices sont au format CSC ou CSR.

Je sais qu'il y en a un dans le paquet smmp mais j'ai besoin de quelque chose qui est déjà implémenté en C ou C ++.

Toute aide serait appréciée. Merci d'avance.

Vous pouvez simplement simuler le produit matrice-matrice en formant le produit des deux motifs de rareté - c'est-à-dire que vous considérez le motif de rareté (qui est stocké dans des tableaux séparés au format CSR) comme une matrice qui contient soit un zéro soit un un dans chaque entrée. Pour exécuter ce produit simulé, il vous suffit de former le etopération sur ces zéros et uns et est donc beaucoup plus rapide que le produit matrice-matrice réel - en fait, tout ce que vous avez à faire est de parcourir les lignes et les colonnes des deux matrices et de vérifier qu'il y a au moins une entrée dans un ligne et la colonne que vous multipliez avec où les deux matrices sont non nulles. Il s'agit d'une opération bon marché - beaucoup moins chère dans tous les cas que d'avoir à faire la multiplication à virgule flottante dans le produit réel, ce qui vous oblige non seulement à faire de l'arithmétique à virgule flottante (cher), mais également à lire les nombres à virgule flottante réels de la mémoire ( encore plus cher, mais vous n'en avez pas besoin lorsque vous multipliez le motif de rareté car les valeurs non nulles de la matrice sont stockées séparément dans CSR).

J'ai en fait écrit le code original dans Matlab pour A * B, A et B clairsemés. La pré-allocation d'espace pour le résultat était en effet la partie intéressante. Nous avons observé ce que Godric souligne - que connaître le nombre de non-zéros en AB est aussi coûteux que de calculer AB.

Nous avons fait l'implémentation initiale de Matlab clairsemé vers 1990, avant le document d'Edith Cohen qui donnait le premier moyen pratique et rapide d'estimer avec précision la taille de l'AB. Nous avons mis en place un estimateur de taille inférieure, et si nous manquions d'espace au milieu du calcul, nous doublions l'allocation et copions le résultat partiellement calculé.

Je ne sais pas ce qu'il y a dans Matlab maintenant.

Une autre possibilité serait de calculer AB une colonne à la fois. Chaque colonne peut être stockée temporairement dans un accumulateur clairsemé (voir le document Matlab clairsemé pour une explication de ceux-ci), et de l'espace alloué pour contenir la taille exactement connue de la colonne de résultat. Le résultat serait sous forme de colonnes éparses compressées éparses - chaque colonne dans CSC mais sans contiguïté intercolonne - en utilisant 2 vecteurs de longueur numcols (col start, col length), plutôt qu'un, comme métadonnées. C'est une forme de stockage qui peut valoir le coup d'œil; il a une autre force - vous pouvez agrandir une colonne sans réaffecter la matrice entière.

Cet article décrit un algorithme pour approximer la taille d'une résultante du produit matriciel de deux matrices clairsemées.

Le problème avec la recherche d'un nombre exact d'entrées non nulles dans une multiplication matricielle clairsemée est que chaque élément de la résultante dépend de l'interaction de deux vecteurs, qui tous deux sont susceptibles de contenir au moins quelques éléments non nuls. Par conséquent, pour calculer le nombre dont vous avez besoin pour évaluer les opérations logiques sur une paire de vecteurs pour chaque élément de la résultante. Le problème avec cela est qu'il nécessite un nombre d'opérations similaire au nombre d'opérations nécessaires pour calculer le produit matriciel lui-même. Dans mes commentaires, j'ai mentionné la possibilité d'exploiter certaines structures dans les éléments non nuls des matrices originales, mais ces mêmes exploits pourraient également être utilisés pour réduire le travail effectué dans la multiplication matricielle.

Vous feriez probablement mieux d'utiliser le papier ci-dessus pour surestimer les besoins en mémoire, faire la multiplication puis tronquer la mémoire allouée, ou déplacer la matrice résultante vers un tableau de taille plus appropriée. De plus, les produits à matrice clairsemée ne sont pas rares, et je garantirais presque que ce problème a été résolu auparavant. En fouillant un peu dans certaines bibliothèques open source, les bibliothèques à matrice clairsemée devraient vous conduire aux algorithmes qu'ils utilisent pour préallouer la mémoire.

Pour CSR ou CSC, avez-vous la garantie que votre tableau d'éléments de matrice n'a pas déjà de zéros? Dans ce cas, il est simple de déterminer le nombre d'éléments non nuls, en utilisant quelque chose de similaire à:

int nnz = sizeof(My_Array)/sizeof(long int);

Cependant, si ce n'est pas le cas (cela semble un peu trop facile), vous pouvez essayer une réduction . Si votre tableau d'éléments de matrice est très grand, cela peut être le moyen le plus efficace de calculer le nombre d'éléments non nuls. De nombreuses bibliothèques C / C ++ parallèles telles que Thrust (une bibliothèque CUDA) ou OpenCL (que vous n'avez pas besoin d'un GPU pour utiliser) prennent en charge les réductions conditionnelles - pour chaque élément, ajoutez le résultat de Condition(Element). Si vous définissez la condition sur, Element != 0vous ajouterez le nombre d'éléments non nuls. Vous pouvez également supprimer les éléments de valeur zéro de votre tableau d'éléments, tableau d'index de ligne / colonne et ajuster vos pointeurs de colonne / ligne.

La façon la plus simple de mettre en œuvre la RSE est d'essayer

std::vector< std::map<int, complex<float>> > 

pour représenter votre matrice. Dans ce cas, vous n'aurez pas vraiment à vous soucier du nombre d'éléments non nuls, tout est accessible via

std::map< int, complex<float> >::iterator

sur chaque rangée. Meilleur ..