Multiplication matricielle-matricielle

Je travaille actuellement avec des matrices creuses, et je dois comparer le temps de calcul de la multiplication matricielle-matricielle clairsemée avec la multiplication matricielle-matricielle complète. Le problème est que le calcul de la matrice clairsemée est plus lent que le calcul de la matrice complète. Je compresse mes matrices avec le stockage en ligne comprimé, et multiplier 2 matrices prend beaucoup de temps (quadruple pour la boucle), donc je me demande s'il y a un meilleur format de compression plus approprié au fonctionnement matriciel-matrice (CRS est très pratique avec le calcul matriciel-vectoriel).Multiplication matricielle-matricielle

Merci d'avance!

Source

2013-09-26 HappyRave

voir: http://scicomp.stackexchange.com/questions/2226/what-is-the-overhead-in-sparse-matrix-multiplication – rerx

Je ne sais pas si je comprends votre question, mais si vous voulez Pour accélérer la multiplication matricielle, vous pouvez transformer chaque matrice en une matrice diagonale (http://en.wikipedia.org/wiki/Diagonal_matrix), qui est seulement O (n^3) pour chaque matrice. Alors la multiplication est seulement O (n). –

Il est généralement appelé "Lignes compactes compressées" (CSR), et non CRS. La transposition, Compressed Sparse Columns (CSC) est également couramment utilisé, y compris par le paquet CSparse qui finit par être le backend de beaucoup de systèmes, y compris MatLAB et SciPy (je pense).

Il existe également un format DCSC (Collyse Sparse Doublement Compressé) moins commun utilisé par le BLAS Combinatorial. Il compresse à nouveau l'index de la colonne, et est utile dans les cas où la matrice est l'hypersparse. Une matrice hypersparse a la plupart des colonnes vides, ce qui arrive avec la décomposition de la matrice 2D.

Cela dit, oui, il y a plus de frais généraux. Cependant, vos opérations sont maintenant dominées par le nombre de nonzeros, pas les dimensions. Ainsi, votre FLOPS pourrait être moins, mais vous obtenez toujours votre réponse plus rapidement.

Source

2013-09-26 08:25:39 Adam

Vous pouvez consulter le papier EFFICACE SPARSE MATRIX-MATRIX PRODUITS UTILISANT COLORINGS http://www.mcs.anl.gov/papers/P5007-0813_1.pdf pour une discussion sur la façon d'obtenir de hautes performances avec des produits matriciels à matrice clairsemée.

Source

2014-01-13 22:49:01 user1101165

Up vote par moi, à cause de la downvote originale. L'article lié est pertinent pour le sujet. – shuhalo

@shuhalo vous ne devriez pas vraiment upvode parce que quelqu'un d'autre downvoted, si c'est ce qui est arrivé ici –

Multiplication matricielle-matricielle

Répondre

Questions connexes