WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

  
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

schnelle berechnung einer matrix
 

paolopinkel

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 09.10.2011, 13:22     Titel: schnelle berechnung einer matrix
  Antworten mit Zitat      
Liebes Forum,

ich habe n vektoren x_1 bis x_n der dimension d, die in einer n x d -Matrix M aufgelistet sind.
ich möchte gerne eine n x n Matrix A generieren mit a_ij = norm(xi-xj)^2. das ist an sich kein problem mit einer schleife, jedoch ist n oft >10000 und ich muss diese matrix ständig neu berechnen. weiss jemand die schnellste lösung ?

Vielen Dank


Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 09.10.2011, 17:18     Titel: Re: schnelle berechnung einer matrix
  Antworten mit Zitat      
Hallo paolopinkel,

Es wäre hilfreich, wenn Du den Source-Code postest. Sehr oft sind FOR-Schleifen nämlich sehr effizient, wenn sie optimal programmiert sind.

Ich habe in der FEX eine Funktion veröffentlicht, die der 2-norm von [10000 x 1] Vektoren 6 mal schneller berechnet als NORM. Allerdings ist "sqrt(X.' * X)" nochmal 2.5 mal schneller, aber nur auf einzelne Vektoren anwendbar. Für die effiziente Berechnung der 2-Norm für die Zeilen oder Spalten einer Matrix, ist dies schneller: http://www.mathworks.com/matlabcentral/fileexchange/29035-dnorm2. Es sollte sich leicht in Deinen Code einbauen lassen.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
paolopinkel

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 09.10.2011, 19:32     Titel:
  Antworten mit Zitat      
hallo Jan,

beim ersten mal hab ich nicht die ganze aufgabe gepostet, da ich dachte exp^ und /sigma^2 könnte man am besten im nachhinein komponentenweise anwenden. die vollständige aufgabenstellung ist:
A_ij = exp(norm(x_i-x_j)^2/sigma^2)

meine bisher schnellste lösung:

Code:

[n1  n2] =size(M);
A = .5*eye(n1);
for k =2:n1
    for j=1:k-1
       A(j,k) =exp((-norm(M(k,:)- M(j,:))^2)/(sigma^2));
    end
end
A = A'+A;
 


viele grüße
paolo
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 10.10.2011, 01:47     Titel:
  Antworten mit Zitat      
Hallo paolopinkel,

Wie groß ist M üblicherweise und was ist "sigma"?

Nun ein paar Methoden zur Beschleunigung:

1. Vermeiden wiederholter Berechnungen:
Code:
sigma = 0.7;
sigma2 = -1 / sigma ^ 2;
n1 = size(M, 1);
A = 0.5 * eye(n1);
for k = 2:n1
    for j = 1:k-1
       A(j, k) = exp((norm(M(k,:)- M(j,:))^2) * sigma2);
    end
end
A_orig = A'+A;

=> Bringt hier gar nichts, sollte man aber schon aus Prinzip verwenden.

2. Norm quadrieren? Dann kann man sich die teure Berechnung der Wurzel doch sparen! Die Summe der Quadrate ist das DOT-Produkt:
Code:
sigma = 0.7;
sigma2 = -1 / sigma ^ 2;
n1 = size(M, 1);
A = 0.5 * eye(n1);
for k = 2:n1
    for j = 1:k-1
       v = M(k, :) - M(j, :);
       A(j, k) = exp((v * v') * sigma2);
    end
end
A = A'+A;

Das benötigt nur noch 42% der Rechenzeit mit meinen Testdaten: M = rand(100, 10000).

3. M(K, :) wird wiederholt, also besser aus der inneren Schleife ziehen:
Code:
...
for k = 2:n1
   w = M(k,:);
   for j = 1:k-1
      v = w - M(j,:);
      A(j, k) = exp((v * v') * sigma2);
   end
end

32% der Original-Zeit!

4. Matlab (und jede andere Programmiersprache auch) rechnet schneller, wenn es auf Elemente zugreifen kann, die im Speicher neben einander liegen. Also müsste man M transponieren:
Code:
...
Mt = M';
for k = 2:n1
   w = Mt(:, k);
   for j = 1:k-1
      v = w - Mt(:, j);
      A(j, k) = exp((v' * v) * sigma2);  % Swap v and v'
   end
end

Und das braucht nur noch 16% Rechnenzeit.

5. Nachdem die Schleifen so weit abgespeckt sind, ist die temporäre Variable w wieder eine (winzige) Bremse:
Code:
...
Mt = M';
for k = 2:n1
   for j = 1:k-1
      v = Mt(:, k) - Mt(:, j);
      A(j, k) = exp((v' * v) * sigma2);
   end
end

15%.
Das EXP oder die Multiplikation mit sigma2 auf die fertige Matrix anzuwenden bringt nichts. Matlab's JIT-Beschleuniger macht das schon automatisch.

6.6 mal schneller ist ein hübsches Ergebnis. Reicht es Dir oder möchtest Du dies als C-Mex beschleunigen? Dann solltest Du aber unbedingt eine effiziente multi-threading BLAS-Bibliothek verwenden, denn v'*v ist die in naiver C-Implemtierung deutlich langsamer.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
paolopinkel

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 10.10.2011, 13:25     Titel:
  Antworten mit Zitat      
genial.
vielen dank für deine hilfe.

grüße
paolo
 
paolopinkel

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 10.10.2011, 15:38     Titel:
  Antworten mit Zitat      
hey jan.

oh mann, zu früh gefreut. hab das jetzt zuhause mal durchlaufen lassen. und ja, für 100x10000 ist es super. meine matrizen sind jedoch von der form 10000 x 20. also n1 >>>> n2. und da ist alte verfahren deutlich schneller.

hast du darauf eine antwort?

viele grüße,
paolo
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 10.10.2011, 17:55     Titel: Re: schnelle berechnung einer matrix
  Antworten mit Zitat      
Hallo paolopinkel,

Ups, da bin ich wohl mit "ich habe n vektoren x_1 bis x_n" durcheinander geraten. Dann alles wieder zurück. Nun ist die Vektorisierung doch schneller als die doppelte Schleife:

Code:

sigma = 0.7;
sigma2 = -1 / sigma ^ 2;
n1 = size(M, 1);
A = zeros(n1);
for k = 2:n1
   r = bsxfun(@minus, M(k, :), M(1:k-1, :));
   p = exp(sum(r .* r, 2) * sigma2);
   A(1:k-1, k) = p;
   A(k, 1:k-1) = p';
   A(k,k)        = 0.5;  
end

Ich habe noch A direkt symmetrisch befüllt, statt A=A+A'.
0.5 * eye(n1) muss n1^2 mutliplikationen ausführen. A(k,k)=0.5 ist viel billiger.
Unter MATLAB 2011b ist das 7.7 mal schneller als das Original.

Damit ist der Kurs in der Schleifen-Optimierung abgeschlossen ;-)
Die gezeigten Methoden sind auf andere Probleme übertragbar. Ein Problem wird deutlich: Die Optimierung benötigt Kenntnisse über die Größen-Ordnung der Dimensionen der Inputs. Ein Verfahren, dass allgenmein schneller ist, gibt es nicht. Die Grenze, aber der das eine oder andere Verfahren schneller ist, läßt sich nur extrem schwer bestimmen. Für [20 x 10000] statt [10000 x 20] ist es aber deutlich klar.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
paolopinkel

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 11.10.2011, 20:06     Titel:
  Antworten mit Zitat      
funktioniert tadellos.

vielen dank für deine hilfe!
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 11.10.2011, 21:17     Titel:
  Antworten mit Zitat      
Hallo paolopinkel,

Schön, wenn es Dir hilft - die Energie, die dein Rechner spart, verringert die Erwärmung meiner Erde :-)

Das ist ein erstklassiges Beispiel für Optimierung von FOR-Schleifen. Ich werde ein Tutorial daraus basteln.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

 Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.