Matlab wiederholte Matrixmultiplikation - Schleife gegen eingebaute Leistungen

Question

Gegeben eine Matrix A, muss ich mit anderen n Vektoren multiplizieren (d. H. i=1...n). Die Größe von A kann wie 5000x5000 und somit Bi wie 5000x1 sein.

Wenn ich das Produkt in der folgenden Art und Weise auswerten:

for i=1:n 
    product=A*Bi; 
    % do something with product 
end 

Das Ergebnis ist Art und Weise (Größenordnung) langsamer als die Berechnung der Produkte wie:

%assume that S is a matrix that contains the vectors Bi as columns, i.e. S(:,i)=Bi, then: 
results=A*S; %stores all the products in matrix form 
% do something with results 

Das Problem ist, dass die Zahl n von Vektoren Bi möglicherweise zu groß, um im Speicher gespeichert zu werden, zum Beispiel n=300000, so muss ich eine Schleife Ansatz verwenden, wo jedes Mal, wenn ich das Produkt auswerte, verwenden Sie es und dann den Vektor verwerfen.

Warum ist ein solcher Ansatz im Vergleich zur direkten Multiplikation so langsam, und gibt es Möglichkeiten, dies zu überwinden?

Answer 1

könnten Sie versuchen, eine Schleife über Chargen so zum Beispiel

for i = 0:(n/k)-1 
    product = A*S(:,(i*k+1):(i+1)*k) 
end 

Und k justieren für Sie aus der Geschwindigkeit und Speicher die besten Handel zu finden.

MATLABs Schleifen sind langsam, da es sich um eine interpretierte Sprache handelt. Es muss also eine Menge Dinge im laufenden Betrieb erledigen. Die Schleifen sind heutzutage wegen des JIT-Compilers stark verbessert, aber sie sind im Vergleich zu den eingebauten Funktionen, die in C geschrieben und kompiliert werden, immer noch langsam. Außerdem verwenden sie im Vergleich dazu ultraschnelle Matrix-Multiplikationsalgorithmen mit Ihrem ziemlich naiven Algorithmus, der durch Schleifen erreicht wird, die auch in der Beschleunigung helfen, die Sie erfahren.

Answer 2

Der Einfachheit halber nehme meine Antwort eine n-mal-n quadratische Matrix A an, aber es gilt auch für Nichtquadrate.

Ihr Schleifenansatz verwendet Matrixvektormultiplikation. Die naive Lösung ist auch die bekannteste, die zu einer Laufzeit von O (n^2) führt, die n-mal wiederholt wird. Sie haben eine Gesamtlaufzeit von O (n^3).

Für die Matrixmultiplikation gibt es einen besseren Ansatz. Der bekannteste Algorithmus benötigt nur wenig weniger als O (n^2,4) Laufzeit, wodurch er für große Zahlen viel schneller wird.

Sie erzielen eine bessere Laufzeit, wenn Sie mehrere Vektoren Bi gleichzeitig mit Matrixmultiplikation multiplizieren. Dies wird nicht die Leistung einer reinen Matrixmultiplikation erreichen, aber die Arbeit mit größeren Schichten von b ist wahrscheinlich die schnellste speichereffiziente Lösung.

einige Code für die verschiedenen diskutierten Ansätze:

n=5000; 
k=100; 
A=rand(n,n); 
S=rand(n,n); 
workers=matlabpool('size'); 
%for a parfor solution, the batch size must be smaller because multiple batches are stred in memory at once 
kparallel=k/workers; 
disp('simple loop:'); 
tic; 
for i = 1:n 
    product = A*S(:,n); 
end 
toc 
disp('batched loop:'); 
tic; 
for i = 1:(n/k) 
    product = A*S(:,(i-1)*k+1:(i)*k); 
end 
toc 
disp('batched parfor loop:'); 
tic; 
parfor i = 1:(n/kparallel) 
    product = A*S(:,(i-1)*kparallel+1:(i)*kparallel); 
end 
toc 
disp('matrix multiplication:'); 
tic; 
A*S; 
toc 

Answer 3

Neben @Dan's answer Sie könnten versuchen, gehen parallel, sofern Sie genügend Kerne und groß genug, um Operationen haben sie rentabel zu machen (this answer für weitere Details über Speicher sehen Verbrauch von parfor):

parfor ii = 0:(n/k)-1 
    product = A*S(:,(ii*k+1):(ii+1)*k) 
end 

ich in den docs on mtimes (die * Bediener nicht sehen kann), ob es implizit multithreaded, aber es ist einen Versuch wert, denke ich.

Answer 4

Um die Multiplikationen jedes Arrays mit der Matrix durchzuführen, multiplizieren Sie einfach die Matrix mit einer Matrix, die die gewünschten Arrays als Spalten enthält.

Also, wenn Sie wollen, dass diese

a*b==horzcat(a*b(:,1),a*b(:,2),a*b(:,3)) 

wahr

wenn

size(a)=3,3 

dann überprüfen, ist

Auf diese Weise können Sie eine Menge Zeit aus Schleife sparen