Discussion :

[S4sha]

Bonjour,

J'ai un problème très simple avec MATLAB. J'ai une matrice creuse H de taille 4608 x 687500 (5-6% de sparsite), et une matrice diagonale D de taille 687500 x 687500 (bien entendu creuse).

Je souhaite effectuer le produit H * D * H' le plus vite possible. J'ai essaye de faire le produit en deux etapes mais cela ne semble pas aider

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
>> tic ; H * D * H' ; toc
Elapsed time is 10.970775 seconds.
>> tic ; H1 = H * D ; toc
Elapsed time is 0.214301 seconds.
>> tic ; H1 * H' ; toc
Elapsed time is 10.111605 seconds.

Est-ce qu'il existe une manip ou une fonction specifique pour des produit du genre H * D * H'

Merci !

[Jerome Briot]

Je transfert la discussion dans le forum Algorithmes car je pense que tu auras plus de réponses ici

[S4sha]

Merci Dut

je viens de decouvrir cuSparse. C'est une librairie Cuda qui traite de ce genre de problème. Je vais voir s'il existe des fonctions mex qui utilisent cuSparse. Sinon je vais m'y mettre moi meme...

[Jerome Briot]

De mon point de vue, il faudra sans doute passer par une bibliothèque externe (via un fichier MEX).

Le produit matriciel fait partie des base de MATLAB (BLAS) et je doute que tu puisses accélérer ce qui est déjà optimisé par définition.

Dans tous les cas, n'hésite pas à nous faire un retour d'expérience sur ce problème

[S4sha]

Oui il faudra passer par un mex, mais avec Cuda et ma carte Nvidia, je pense que je peux accélérer significativement le calcul.

[FR119492]

Salut!
Comment tes matrices sont-elles stockées? Est-ce dans des tableaux 4608*687500 et 687500*687500 ? Si c'est le cas, ton ordinateur perd un temps considérable pour des additions de zéro et des multiplications par zéro.
Jean-Marc Blanc

[S4sha]

Salut!
Comment tes matrices sont-elles stockées? Est-ce dans des tableaux 4608*687500 et 687500*687500 ? Si c'est le cas, ton ordinateur perd un temps considérable pour des additions de zéro et des multiplications par zéro.
Jean-Marc Blanc

Non, ce sont des matrices creuses, construites avec 'sparse'. La matrice H est remplie a 1-5% environ...

[FR119492]

Salut!

ce sont des matrices creuses, construites avec 'sparse'

Tu ne réponds pas à ma question. Alors, je te la pose autrement: la mémoire de ton ordinateur est composée d'octets. Comment les divers termes de tes matrices sont-ils placés dans ces octets? D'autre part, j'ai cherché mais pas trouvé ce qu'est 'sparce'.
Jean-Marc Blanc

[Jerome Briot]

S4sha utilise MATLAB et donc les fonctions sparse et speye de MATLAB pour créer les matrices H et D.

Au sujet de l'implémentation des matrices creuses dans MATLAB, il y a bien ce document : SPARSE MATRICES IN MATLAB: DESIGN AND IMPLEMENTATION
Mais je ne sais pas si il est encore d'actualité.

[S4sha]

Salut!

Tu ne réponds pas à ma question. Alors, je te la pose autrement: la mémoire de ton ordinateur est composée d'octets. Comment les divers termes de tes matrices sont-ils placés dans ces octets? D'autre part, j'ai cherché mais pas trouvé ce qu'est 'sparce'.
Jean-Marc Blanc

Oups

Le message etait a l'origine dans le forum Matlab, donc je pensais que le cadre etait bien compris.

Matlab cree des matrices creuse avec la fonction 'sparse'. Une matrice creuse est une structure qui contient une liste de valeurs (les valeurs non-nulles), ainsi que leurs positions dans la matrice. Le format de stockage est CSC (compressed sparse column) il me semble.

Le produit de matrices creuses sous Matlab s'effectue avec son propre algorithme. C'est tres rapide, mais pour des larges dimensions cela peut prendre pres d'une minute.

J'essaie de creer une fonction C++ utilisant la librarie cuSPARSE de Cuda. cuSPARSE utilise le format CSR (compressed sparse row).

N’étant pas une brute en C++ (et encore moins en Cuda auquel je n'ai jamais touche), je me demandait si des gens avait déjà fait ce travail (produit de matrices creuses Matlab avec cuSPARSE)

[FR119492]

Salut!

Matlab cree des matrices creuse avec la fonction 'sparse'

Pour résoudre un problème, il faut le comprendre, et, en particulier connaître l'intégralité de ses données. Or tu nous dis que ta matrice H a été créée par 'sparse' mais tu nous caches ce qu'ont été les données de 'sparse'. On ne sait donc pas quelles sont les données contenues dans la matrice H ni comment elles y sont réparties. Tu nous dis aussi qu'elle est remplie entre 1% et 5%, mais on ne sait pas comment. Dans ces conditions, ton problème est insoluble autant pour nous que pour toi.
Jean-Marc Blanc