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

Sparse Matrizen zusammenbauen
 

RosaE.

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.09.2011, 10:44     Titel: Sparse Matrizen zusammenbauen
  Antworten mit Zitat      
Hallo!

Ich habe eine sehr große Matrix A, die in einer For-Schleife zusammengebaut wird.

Früher passiert das etwa so:
Code:

A = [];
for ...
A=[A;sparse(...) Asub sparse(...)];
end
 


Da hat jetzt Matlab aber immer die Warnung ausgespuckt, dass das schlecht sei und ich A preallokieren sollte. Ich weiß auch wie groß A wird, aber da A eine sparse-Matrix ist, weiß ich nicht, wie ich diese zusammenbauen soll.

Wenn ich jetzt in der For-Schleife so etwas mache wie:
Code:

A(von:bis) = [sparse(...) Asub sparse(...)];
 


Dann sagt MATLAB wieder, dass das indizieren bei sparse Matrizen langsam sei und ich A irgendwie mit "sparse" zusammenbauen solle.

Ich weiß aber nicht wie das geht.
Versteht ihr mein Problem?

Danke,
Rosa


RosaE.

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.09.2011, 15:53     Titel:
  Antworten mit Zitat      
Hey,

ich habe mich jetzt von http://www.mathworks.de/help/techdoc/ref/spalloc.html
, genauer von:
Code:
S = spalloc(n,n,3*n);
for j = 1:n
    S(:,j) = [zeros(n-3,1)' round(rand(3,1))']';end


inspirieren lassen. Der Code spuckt zwar immer noch die Warnung aus, wird aber unter dem Link als effizient bezeichnet.

Ich habe versucht das so in meinem Code umzusetzen, allerdings baue ich die Matrix dort Zeile für Zeile auf, wobei ich immer ca 500 Zeilen auf einmal setze.

Das Ergebnis ist leider anscheinend noch ineffizienter als vorher. Hat es irgendeinen Grund, dass die Sparse Matrix spaltenweise aufgebaut werden sollte?

Gruß,
Rosa
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 13.09.2011, 16:45     Titel:
  Antworten mit Zitat      
Hallo RosaE.

Man muss keine Nullen in ein Sparse-Array schreiben. Also könntest Du den ZEROS-Teil weglassen.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
RosaE.

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.09.2011, 17:05     Titel:
  Antworten mit Zitat      
Hi Jan!

Du meinst jetzt hier, oder:
Code:
S = spalloc(n,n,3*n);
for j = 1:n
    S(:,j) = [zeros(n-3,1)' round(rand(3,1))']';end


Der Code stammt so von der Mathworks Hilfe und ich verwende ihn jetzt auch nicht so 1:1.


Was ich vorher gemacht habe ist folgendes:

Code:
A = [];
for K = 1:AnzK
Asub = ....; %aus mehreren Untermatrizen zusammengebaut, wird dadurch sparse
A=[A;
     sparse(AnzN,(K-1)*AnzVar) Asub sparse(AnzN,(AnzK-K)*AnzVar)];
...
end


Was ich jetzt mache ist:
Code:

A = spalloc(..,...,...);
for K = 1:AnzK
Asub = ....;
A(AnzN*(K-1)+1 : K* AnzN,:) = [sparse(AnzN,(K-1)*AnzVar) Asub sparse(AnzN,(AnzK-K)*AnzVar)];
end
...


Und das neue scheint langsamer zu sein, obwohl das in meinen Augen ähnlich zu dem Beispiel in: http://www.mathworks.de/help/techdoc/ref/spalloc.html

ist.


Hast du eine Idee, wie ich Konstruktion von A beschleunigen könnte? Ich hoffe man kann aus diesen Codeschnipseln nachvollziehen, was ich tue.

Rosa
 
Jan S
Moderator

Moderator

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

Die Mathworks Hilfe ist schon toll, ohne Frage. Aber die Beispiele müssen nicht unbedingt die effizienteste Methode für ausgerechnet Deinen Code sein.

Ich würde vermuten, dass dies schneller ist:
Code:
S = spalloc(n, n, 3*n);
for j = 1:n
    S(n-2:n, j) = round(rand(3,1));
end

Dann muss kein temporärer Vektor aus Nullen erstellt werden, danach noch einer, bei dem die RAND-Werte angehängt werden, um dan nachher die Nullen wieder zu entfernen.

Am effizientesten sollte es sein, nur die nicht-Null Elemente direkt in die pre-allocierte SPARSE Matrix zu schreiben. Eine SPARSE Matrix aus anderen SPARSE Matrizen zusammenzubauen ist ineffizient, weil das Erstellen der SPARSE-Untermatrizen viel Zeit benötigt. Leider verstehe ich Deinen Code nicht ganz. Kannst Du statt der "..." Einfügungen einfach den Orginal-Code drinstehen lassen?

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
RosaE.

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 15.09.2011, 11:01     Titel:
  Antworten mit Zitat      
Hi Jan,

ich weiß leider nicht recht, wie ich deinen Ansatz in meinem Code umsetzen kann. Ich versuche den Code nochmal etwas genauer zu beschreiben. Eventuell kann ich dir ihn auch schicken, ich würde ihn aber nur sehr ungern hier öffentlich reinstellen.

Also, hier sind hoffentlich alle relevanten Infos (Original Code):
Code:

A = [];
for K = 1:AnzK
%Daten für K auslesen
%ein paar Untermatrizen erstellen
Asub = [...]; %eine Matrix, die aus den ganzen Untermatrizen zusammengebaut ist
A = [A;
      sparse(AnzN, (K-1)*AnzVar) Asub sparse(AnzN, (AnzK-K)*AnzVar)];
...
end
A = [A nochEineMatrix];
A = [A nochEineAndereMatrix];
 


D.h., dass A zeilenweise aus einer Matrix Asub, die pro Durchgang anders aussieht jedoch die gleichen Dimensionen behält, zusammengebaut wird. Ich würde die Konstruktion von A gerne schneller machen. Daher habe ich mir gedacht ich könnte erst Platz für A allokieren und A dann möglichst effizient zusammenbauen. Meine Lösungen sind aber bisher langsamer als der Originalcode.
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 15.09.2011, 14:45     Titel:
  Antworten mit Zitat      
Hallo RosaE,

Wenn Du Dich bei goMatlab anmeldest, könnte ich Dir eine PN schreiben.

Mein Ansatz lautet:
1. Die Ergebnismatrix als SPARSE pre-allozieren und die Anzahl der nicht-Nullen als Anzahl der Elemente vorgeben.
2. Dann möglichst spaltenweise oder als Spalten-Blöcke die nicht-Null-Elemente einfügen.

Eine Matrix in jeder Iteration wachsen zu lassen, ist immer sehr zeitraubend.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
RosaE.

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 15.09.2011, 17:09     Titel:
  Antworten mit Zitat      
Hallo Jan,

ich habe mich unter dem Benutzernamen "Wimme" angemeldet, allerdings bekomme ich keine Bestätigungsmail. Weiß nicht ob da etwas schief gelaufen ist, oder ob ich noch einfach etwas warten muss.

Aus welchem Grund ist es denn besser eine Sparse Matrix spaltenweise zusammenzubauen als zeilenweise?

Mich würde es nun wirklich brennend interessieren, wie ich meine Matrix so wie mein Code ist besser zusammengebaut bekomme! Wink
 
RoseE.

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 15.09.2011, 17:45     Titel:
  Antworten mit Zitat      
Hey,

ich glaube da ist wirklich etwas schief gelaufen. Kann ich mir den Bestätigungslink irgendwie noch einmal zu senden lassen?
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 15.09.2011, 22:24     Titel:
  Antworten mit Zitat      
Hallo RosaE,

Zitat:
Aus welchem Grund ist es denn besser eine Sparse Matrix spaltenweise zusammenzubauen als zeilenweise?


Die Werte in SPARSE und FULL Arrays werden in Matlab spaltenweise organisiert.
In X=rand(1000, 1000) liegen die Elemente X(1,1) und X(2,1) also nebeneinander im Speicher, während zwischen X(1,1) und X(1,2) 8000 Bytes liegen. Beim Lesen und Schreiben im Speicher werden die Daten zunächst in kleinen Blöcken in den Prozessor-Cache kopiert. Ein Zugriff auf X(1, :) springt also in großen Sprüngen durch insgesamt 8MB Speicher, während X(:,1) in 8kB passt.

Die Daten in SPARSE Arrays sind anders organisiert, da intern ja eine Liste mit den Indizes mitgeführt wird. Aber auch dabei ist der spalten-orientiert Zugriff deutlich schneller:
[code]ind = round(linspace(1, 1000, 14));
x1 = spalloc(1000, 1000, 1000*14);
tic;
for i = 1:1000
x1(ind, i) = rand(14, 1);
end
toc; % 0.128 sec

x2 = spalloc(1000, 1000, 1000*14);
tic;
ind = round(linspace(1, 1000, 14));
for i = 1:1000
x2(ind, i) = rand(14, 1);
end
toc; % 0.0190 sec[code]
6.7 mal schnell ist ein deutlicher Unterschied.
Ein zusätzliches TRANSPOSE verlängert hier übrigens die Laufzeit nicht messbar, sodass man x1 also deutlich effizienter durch "transpose(x2)" erstellen kann.

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.