Matlab ripetuta moltiplicazione matrice - loop vs prestazioni integrate

Question

Data una matrice A, ho bisogno di moltiplicare con altri n vettori Bi (ad esempio i=1...n). La dimensione di A può essere come 5000x5000 e quindi Bi come 5000x1.

Se valuto il prodotto nel seguente modo:

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

Il risultato è il modo (ordini di grandezza) più lento di calcolo dei prodotti come:

%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 

Il problema è che il numero n di vettori Bi potrebbe essere troppo grande per essere archiviato in memoria, ad esempio n=300000, quindi è necessario utilizzare un approccio ad anello in cui ogni volta che valuto il prodotto, utilizzarlo e quindi scartare il vettore Bi.

Perché un tale approccio è così lento rispetto alla moltiplicazione diretta e ci sono modi per superarlo?

Answer 1

Si potrebbe provare un ciclo su lotti così per esempio

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

E regolare k di trovare il miglior compromesso tra velocità e memoria per voi.

I cicli di MATLAB sono lenti perché è un linguaggio interpretato. Quindi deve elaborare un sacco di cose al volo. I loop sono notevolmente migliorati in questi giorni a causa del compilatore JIT, ma sono ancora lenti rispetto alle funzioni built-in che sono scritte e compilate in C. Inoltre, usano algoritmi di moltiplicazione delle matrici super veloci e all'avanguardia con il tuo algoritmo abbastanza ingenuo realizzato tramite il looping, che aiuta anche la velocizzazione che stai vivendo.

Answer 2

Per semplicità la mia risposta assumerà una matrice quadrata n-by-n A, ma è vera anche per i non quadrati.

L'approccio del ciclo utilizza la moltiplicazione del vettore matrice. La soluzione ingenua è anche la più conosciuta, risultante in un runtime di O (n^2) che viene ripetuto n volte. Finisci con un runtime totale di O (n^3).

Per la moltiplicazione della matrice, esiste un approccio migliore. L'algoritmo più noto richiede solo un tempo di esecuzione inferiore a O (n^2.4), rendendolo molto più veloce per un numero elevato.

Otterrete un tempo di esecuzione migliore quando si moltiplicano più vettori Bi contemporaneamente utilizzando la moltiplicazione di matrice. Ciò non raggiungerà le prestazioni di una moltiplicazione di matrice pura, ma lavorare con fette più grandi di b è probabilmente la soluzione più efficiente in termini di memoria.

del codice per i diversi approcci discussi:

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

Oltre a @Dan's answer si potrebbe provare ad andare in parallelo, a patto di avere abbastanza core e grandi operazioni sufficiente a rendere redditizia (vedi this answer per maggiori dettagli sulla memoria consumo di parfor):

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

non riesco a vedere nel (l'operatore docs on mtimes*) se è implicitamente multithread, ma è vale la pena uno scatto immagino.

Answer 4

Per fare le moltiplicazioni di ogni matrice con la matrice basta moltiplicare la matrice con una matrice che avrà come colonne gli array desiderati.

Quindi, se si desidera controllare questo

se

size(a)=3,3 

poi

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

vale

In questo modo si risparmia un sacco di tempo dal ciclo