probleme d'une matrice 100000*4

**abidineb** · 14/03/2009, 02h48

bonjour
Voila mon problème, je veut calculer B d'une matriceX de dimension 100000*4 qui est très grande

Code :

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

1
2
3
4
5
6
 
 for i=1:100000
        for j=1:100000
            B=exp(-norm(X(i,:)-X(j,:))^2); 
    end
  end

on remarque que je veut pas stoker la matrice B(i,j) mais juste calculer a chaque fois B, la preuve j'ai pas mis d'indices dans l'expression de B dans le code.
le problème se présente dans le temps de calcul qui est vraiment grand; si qql peut m'aider même en intervenant pas sur le code mais juste me donner une idée pour rendre le code plus rapide. j'espère y trouver la réponse d'une personne généreuse. merci

**FR119492** · 14/03/2009, 13h47

Salut!

je veut calculer B d'une matriceX de dimension 100000*4 qui est très grande

Effectivement, c'est monstrueux, et je ne vois pas comment on pourra redescendre à un temps de calcul raisonnable. Mais, est-ce vraiment ce que tu veux? Ce calcul est-il vraiment nécessaire?
Jean-Marc Blanc

**abidineb** · 14/03/2009, 16h48

Salut
Je tiens a remercier M. Jean-Marc Blanc pour son intervention

, oui effectivement je veut calculer B pour tout les couples de la matrice X qui vraiment grande (100000*4). et même je facilite un peu la tache puisque je ne demande pas de stocker B(i,j).

c'est un calcul des similarités entres vecteurs, pour la classification ( je veut programmer un outil SVM). donc la première étape est de calculer la matrice B)
J'espère que j'etait clair, encore une fois merci, mais est ce que vraiment y'a t-il pas une autre solution dans matlab?

**Jerome Briot** · 14/03/2009, 17h31

Si on stockait chaque valeur de B, on obtiendrait une matrice symétrique par rapport à sa diagonale principale et avec des 1 sur cette même diagonale.

Tu pourrais donc très bien ne calculer que le triangle supérieur ou le triangle inférieur de cette matrice.

Cela revient approximativement au même si tu calcules uniquement B

Ce qui donne :

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
17
18
19
20
21
22
23
24
25
26
27
N = 4;
X = rand(N,4);

tic
for i=1:N
    for j=1:N
        B(i,j)=exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc


tic
for i=1:N
    for j=i:N
        BB(i,j)=exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc

tic
for i=1:N
    for j=i+1:N
        BBB(i,j)=exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc

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
17
18
19
20
21
22
23
24
25
26
27
28
Elapsed time is 0.000082 seconds.
Elapsed time is 0.000041 seconds.
Elapsed time is 0.000030 seconds.
>> B
 
B =
 
    1.0000    0.5030    0.6910    0.2596
    0.5030    1.0000    0.6529    0.5711
    0.6910    0.6529    1.0000    0.4787
    0.2596    0.5711    0.4787    1.0000
 
>> BB
 
BB =
 
    1.0000    0.5030    0.6910    0.2596
         0    1.0000    0.6529    0.5711
         0         0    1.0000    0.4787
         0         0         0    1.0000
 
>> BBB
 
BBB =
 
         0    0.5030    0.6910    0.2596
         0         0    0.6529    0.5711
         0         0         0    0.4787

Maintenant, le gain de temps ne sera peut être pas extraordinaire avec une grosse matrice. Mais si tu ne calcul qu'un scalaire à chaque fois (comme tu sembles le vouloir ici), le gains devrait être significatif

**abidineb** · 14/03/2009, 18h38

Salut M. Dut et merci beaucoup pour ta réponse de haut niveau. chapeau-. mais

oui alors je comprend que vous avez exploiter les propriétés de la matrice symétrique positive en stockant pas la diagonale puisque egual a 1 et l'autre moitie qui n'est pas aussi nécessaire de stocker.

je suis entièrement d'accord avec vous, mais cela n'empêche pas que pour une matrice de X=100000*4, le calcul de B est vraiment long presque une journée entière (1.86gigahz pour le Mprocesseur), est ce que vous me conseiller de déposer les armes, et ne plus reflichir sur cette question?

, car on peut pas améliorer plus, ou au contraire surement il existe une solution a ce problème

?
merci encore une fois, et ça fait plaisir d'avoir un forum comme celui la et des gens aussi bon, je vais envoyer tout mes collègues pour s'inscrire.
cordialement

**Jerome Briot** · 14/03/2009, 19h10

Encore une autre chose, tu calcules la norme pour ensuite l'élever au carré... hors ici, la norme est calculée avec une racine carrée... donc tu peux remplacer cette opération simplement par la somme des termes au carré

Voir la quatrième solution dans le code ci-dessous :

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
N = 1000;
X = rand(N,4);
 
tic
for i=1:N
    for j=1:N
        B = exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc
 
 
tic
for i=1:N
    for j=i:N
        BB = exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc
 
tic
for i=1:N
    for j=i+1:N
        BBB = exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc
 
tic
for i=1:N
    for j=i+1:N
        BBBB = exp(-((X(i,1)-X(j,1))^2 + ...
            (X(i,2)-X(j,2))^2 + ...
            (X(i,3)-X(j,3))^2 + ...
            (X(i,4)-X(j,4))^2));
    end
end
toc

Pour N = 1000, les temps d'exécution sont :

Code :

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

1
2
3
4
Elapsed time is 4.330543 seconds.
Elapsed time is 1.316174 seconds.
Elapsed time is 1.148326 seconds.
Elapsed time is 0.135687 seconds.

Le gain de temps est très significatif avec cette quatrième solution, plus de 30 fois plus rapide que la première

Ce qui devrait (théoriquement) ramener un calcul de 8h à simplement 15min

**Jerome Briot** · 14/03/2009, 19h23

Et pour être encore un peu plus précis dans les temps d'exécution :

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function test
 
N = 1000;
X = rand(N,4);
 
for n=1:5
 
    tic
    for i=1:N
        for j=1:N
            B = exp(-norm(X(i,:)-X(j,:))^2);
        end
    end
    t(1,n) = toc;
 
 
    tic
    for i=1:N
        for j=i:N
            BB = exp(-norm(X(i,:)-X(j,:))^2);
        end
    end
    t(2,n) = toc;
 
    tic
    for i=1:N
        for j=i+1:N
            BBB = exp(-norm(X(i,:)-X(j,:))^2);
        end
    end
    t(3,n) = toc;
 
    tic
    for i=1:N
        for j=i+1:N
            BBBB = exp(-((X(i,1)-X(j,1))^2 + ...
                (X(i,2)-X(j,2))^2 + ...
                (X(i,3)-X(j,3))^2 + ...
                (X(i,4)-X(j,4))^2));
        end
    end
    t(4,n) = toc;
 
end
 
mean(t,2)

ce qui renvoie :

Code :

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

Soit un facteur de vitesse x33 entre le premier et le dernier code

**FR119492** · 14/03/2009, 19h46

Salut!

je veut programmer un outil SVM

Il est toujours dangereux d'utiliser des abréviations avant d'en avoir indiqué le sens. Dans ton cas, SVM peut signifier, selon Wikipedia:

Science & Vie Micro
Séparateurs à Vaste Marge
Star View Metafile
Stored Value Marketing
Saskatchewan Volunteer Medal
Schuylkill Valley Metro
Solaris Volume Manager
Support vector machine
Scanning voltage microscopy
Secure Virtual Machine
Space Vector Modulation

Alors, que choisir?
Jean-Marc Blanc

**abidineb** · 14/03/2009, 23h56

salut;

Désole pour le retard ma connexion n'est pas bonne en ce moment

, bref je dit un grand merci A M. Dut pour sa réponse précieuse, vraiment c'est très gentille, voila je n'ai pas encore essaye la solution de la norme, car mon PC exécute déjà un code j'attends juste le résultat pour ne pas l'interrompre, demain sans faute je vous envois la réponse et le temps d'exécution pour mon problème.

je n'aurai jamais pense a la norme mais a qqch chose plus grand, eeeeh oui M.shanon a dit une fois il faut commencer par les choses simples, après on va voir...
donc merci beaucoup, vous aurez la réponse demain

.

Salut

M. Jean-Marc Blanc; vous avez totalement raison, c'est vrai il faut tout d'abord donner le sens a svm, je veut dire séparateur a vaste marge ou support vector machine; même chose c'est deux méthode de classification qui sont rester top secret pendant 10ans en 1970; la cause est connu.
merci pour votre remarque que je trouve importante

. je vais essaye la méthode de M. dut et je vous met au courant demain sans faute.
merci

M. dut;

Puisque j'attend l'execution du programme de mon pc se terminer pour essayer votre astuce. Avant d'essayer je trouve cette méthode efficace, puisque la racine de la norme c'est la somme des differences au caree

Je vais confirmer demain avec ma propre matrice.
merci

Salut M. Dut;
Je ne vous ai pas oublier pour donner ma réponse de confirmation, juste mon micro ne cesse pas de travailler, j'attends qu'il s'arrette pour prendre les résultats de toute une semaine de deroulement du programme, je ne veut pas perdre du temps( la semaine); des que il termine, j'exécuterais le code. Et on va voir

merci
cordialement

**FR119492** · 16/03/2009, 15h25

Salut!

les résultats de toute une semaine de deroulement du programme

A mon avis, ce n'est pas raisonnable; imagine une panne de courant d'une fraction de seconde et tu perds le travail de toute une semaine. Je pense qu'il doit y avoir beaucoup à améliorer au niveau algorithmique avant de se préoccuper de la programmation dans Matlab ou tout autre langage. C'est pourquoi je transfère cette discussion dans le forum Algo --> Maths.
Jean-Marc Blanc

**pseudocode** · 16/03/2009, 20h33

100.000 samples ca fait beaucoup.

Peut-être peut tu réduire le nombre de samples nécessaires a la détermination de ton SVM ?

google : Reducing the Number of Training Samples for Fast Support Vector Machine Classification

**abidineb** · 17/03/2009, 01h51

salut M.Dut
Donc voila j'ai arrêter le processus, pour essaye tout ce que vous m'avez dit Donc voila le résultat:
CODE 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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
N = 1000;
X = rand(N,4);
 
tic
for i=1:N
    for j=1:N
        B = exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc
 
 
tic
for i=1:N
    for j=i:N
        BB = exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc
 
tic
for i=1:N
    for j=i+1:N
        BBB = exp(-norm(X(i,:)-X(j,:))^2);
    end
end
toc
 
tic
for i=1:N
    for j=i+1:N
        BBBB = exp(-((X(i,1)-X(j,1))^2 + ...
            (X(i,2)-X(j,2))^2 + ...
            (X(i,3)-X(j,3))^2 + ...
            (X(i,4)-X(j,4))^2));
    end
end
toc

temps:
Elapsed time is 5.939777 seconds.
Elapsed time is 2.967195 seconds.
Elapsed time is 2.938300 seconds.
Elapsed time is 3.233909 seconds.

S'il vous plait comment vous avez obtenu dans la dernière mentionnes en gras Elapsed time is 0.135687 seconds et moi 3.23 seconds en essayant le même programme; donc pas d'amélioration. donc je trouve qu'on utilisant la norme est préférable; j'attends votre réponse avec impatience
merci?

BonjourJean-Marc

Vous avez bien fait de transférer la discussion; et désolé pour le mauvais chois; normalement c'est mon rôle de se placer dans le bon;
J'espère qu'on trouvera la solution a ce probleme; qui va regler pas mal de choses.

Rmarque: juste pour la panne de courant; j'utilise Un PC portable de durée autonomie batterie de 3heures donc normalement y a pas de risque, merci pour le conseil.

cordialement

salut M.pseudocode

Je vous félicite pour le conseil, bonne remarque mais je ne peut pas réduire le nombre de samples, car je doit l'utiliser tel qu'il est merci
mais c'est faisable.
J'espere qu'on trouvera une solution a ce petit code
merci

**Jerome Briot** · 17/03/2009, 07h30

Quelle est ta version de MATLAB ?
Sous quel système d'exploitation ?

J'ai utilisé MATLAB R2008a sous Linux et sous Windows XP et les résultats sont toujours identiques.

Sous XP :

Code :

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

Arf non... sous XP j'ai une accélération de x100... vive MATLAB sous Windows

Sinon, comme je l'ai dit plus haut, si tu veux vraiment des résultats précis, il faut utiliser le code de ce message : http://www.developpez.net/forums/d70...a/#post4110525

Pour que les résultats soient stables, il faut exécuter le code dans une fonction et faire plusieurs calculs puis une moyenne des temps d'exécution.

**abidineb** · 17/03/2009, 12h24

Bonjour M.Dut
Donc voila ma version de Matlab est :R2007b
Sous windows XP

Et maintenant j'utilise la fonction dont vous m'avez parle Et je trouve le même problème:
Voici le résultât en exécutant la fonction deux fois:
ans =

6.1927
3.0696
3.1343
3.2250

ans=

6.6223
3.2421
3.2339
3.3988

Même c'est pas normal on trouve la deuxième possibilité meilleure que la troisième. et la quatrième n'en parlant pas

pour la première exécution et je trouve ça pas normal.
que c'est que vous me conseillez de faire? SOS

merci
Cordialement

**Jerome Briot** · 17/03/2009, 12h51

Il faudrait vérifier si le JIT Accelerator est activé...

Que retourne ceci dans le Command Window ?

Code :

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

feature accel

Si le résultat est 0, alors tapes ceci :

Code :

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

feature accel on

Et relance le code test

Je viens de tester avec MATLAB R2007b sous Linux et effectivement les temps d'exécution diffèrent complètement avec ou sans le JIT

**abidineb** · 17/03/2009, 20h02

Re Salut
Effectivement le JIT est active ça donne 1 donc le problème ne provient pas du Jit

.

Je relance le code test dans matlab 7.0 autre version et je trouve:
Elapsed time is 5.172000 seconds.
Elapsed time is 2.547000 seconds.
Elapsed time is 2.562000 seconds.
Elapsed time is 3.610000 seconds.

même problème pour la dernière 3.61
est ce que peut être cela du qu'il faut utilise même version que vous c'est a dire 2008 que j'en ai pas.
merci

**Caro-Line** · 17/03/2009, 20h09

Juste pour info, pour ma part (Windows Vista, MATLAB R2007a)

J'obtiens ces résultats avec le code de Dut :

2.4576
1.1490
1.1457
0.0917

**Jerome Briot** · 17/03/2009, 20h10

Testé à l'instant sur MATLAB 7.1 sous Windows XP :

Code :

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

Comme je l'ai dit plus haut, je l'ai aussi testé sur MATLAB R2007b sous Linux.

**abidineb** · 17/03/2009, 20h13

Je suis allé chez un ami cet après midi; j'ai exécuté la même fonction test(MATLAB6.5); je trouve toujours le 4 code c'est a dire le code le plus simplifie donne un temps d'exécution grand par rapport aux autres (2 et 3 code).
Je comprend d'où viens le problème?

**Jerome Briot** · 17/03/2009, 20h20

Testé à l'instant sur MATLAB 6.5.1 sous Windows XP :

Code :

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

Tu copies bien la fonction dans un fichier m que tu appelles test.m
Ensuite, tu tapes test dans le Command Window
Et tu attends patiemment sans toucher à l'ordinateur que MATLAB ait finit

On est d'accord ?

probleme d'une matrice 100000*4

Mathématiques

Discussions similaires

Partager

Partager