Discussion :

[Mathieu999]

Bonjour,

Dans un algo je dois multiplier trois matrices A*Delta*B, qui sont toutes trois des matrices binaires. A et B sont définies en tant que 'sparse', mais si je définis également Delta en tant que 'sparse', l'exécution prend deux fois plus de temps. Or toutes ces matrices sont effectivement creuses dans les faits.

Quelqu'un aurait-il une idée de la cause de cette lenteur ?

Merci d'avance

PS : J'utilise Matlab R2009b

[Jean Dumoncel]

Bonjour,

aurais-tu un exemple de code simple qui reproduit ce comportement?

[Mathieu999]

Voici un bout du code que j'utilise :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
for i=1:N
    for j=i:N
        A=sparse(G(i).am); %matrice d'adjacence d'un graphe
        B=sparse(G(j).am);
 
        LA=repmat(LabA,1,size(LabB,1)); %LabA :labels des noeuds du grapheA
        LB=repmat(LabB',size(LabA,1),1);
        Delta=(LA==LB); % comparaison binaire des labels
 
        SMat=Delta+alpha*(A*Delta*B)+alpha*(A^2*Delta*B^2);
 
        V=sum(SMat(:)); 
        S(i,j)=V;
    end
end

Pour info, la taille des matrices va jusque 5000x5000.

[Invité]

Bonjour,

As-tu essayé de convertir ta matrice Delta en sparse? Voir ce message qui pourrais expliquer cette lenteur.

[Mathieu999]

En fait le code tel que je l'ai mis plus haut est la version rapide.

Si je convertis Delta en sparse avec par exemple Delta=sparse(LA==LB)
le temps d'exécution double.

Etrange n'est-ce pas ?

[Mathieu999]

Bon apparemment pour que cela fonctionne, je dois d'abord définir Delta en tant que sparse

Code :

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

1
2
3
 
Delta=sparse(zeros(N,N));
Delta=(LA==LB);

Peut-être est-ce dû au fait que ce soit une matrice 'logique' ?

Ceci dit, le résultat global est encore plus rapide quand je ne définis aucune matrice en tant que sparse...

[Invité]

Une amélioration avec BSXFUN:

Code :

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

1
2
3
LA=repmat(LabA,1,size(LabB,1)); %LabA :labels des noeuds du grapheA
LB=repmat(LabB',size(LabA,1),1);
Delta=(LA==LB); % comparaison binaire des labels

Remplacé par:

Code :

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

Delta = bsxfun(@eq,LabA,LabB.');

As-tu pensé à pré-allouer S?

[Mathieu999]

Je n'avais pas pensé à BSXFUN, merci ça accélère un peu le bidule

Sinon oui j'ai pré-alloué S, ce qui m'a fait gagner pas mal de temps de calcul.

[Jerome Briot]

Bon apparemment pour que cela fonctionne, je dois d'abord définir Delta en tant que sparse

Code :

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

1
2
3
 
Delta=sparse(zeros(N,N));
Delta=(LA==LB);

Sauf que :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
>> Delta=sparse(zeros(N,N));
>> issparse(Delta)
 
ans =
 
     1
 
>> Delta=(LA==LB);
>> issparse(Delta)
 
ans =
 
     0

Pour conserver Delta comme matrice creuse, il faudrait faire par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
>> [i,j] = find(LA==LB);
>> Delta = sparse(i,j,true,N,N);
>> issparse(Delta)
 
ans =
 
     1
 
>> whos Delta
  Name         Size              Bytes  Class      Attributes
 
  Delta      300x300            262929  logical    sparse

ou plus simplement :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
>> Delta=sparse(LA==LB);
>> issparse(Delta)
 
ans =
 
     1
 
>> whos Delta
  Name         Size              Bytes  Class      Attributes
 
  Delta      300x300            262929  logical    sparse