Mnożenie wektora z podmatrycami jest powolne

Question

Mam wysoką macierz (przykład poniżej to 10000 na 3000) i chcę wziąć produkty wewnętrzne z podzbiorem jej wierszy (np. 500 wierszy). Powtarza się to z różnymi losowo wybranymi wierszami wiele razy (100 razy w przykładzie, ale w rzeczywistości wiele razy). Okazuje się, że indeksowanie jest dość powolne. W moim przykładzie lepiej jest pomnożyć pełną macierz A (tj. 10000 wierszy) zamiast selektywnie wybierać i mnożyć 500, które są rzeczywiście potrzebne.

Losowe generowanie indeksów wierszy (sub = randperm(10000);sub = sub(1:500);) jest tanie obliczeniowo; Umieściłem go w obu pętlach, aby być sprawiedliwym.

A=randn(10000,3000); 
g=zeros(10000,1); 

tic 
for i=1:100 
    sub = randperm(10000); sub = sub(1:500); 
    b=randn(3000,1); 
    g(sub) = g(sub) + A(sub,:)*b; 
end 
toc 
% elapsed time is 1.58 sec 

tic 
for i=1:100 
    sub = randperm(10000); sub = sub(1:500); 
    b=randn(3000,1); 
    g = g + A*b; 
end 
toc 
% elapsed time is 1.28 sec 

Pytanie brzmi: czy istnieje sposób na przyspieszenie rzeczy, gdy faktycznie potrzebny jest tylko podzbiór wierszy?

Answer 1

Spróbuj pomnożyć przez wiersze zamiast kolumn. Może to wymagać zmiany kolejności danych lub zastosowania skalarnej transpozycji (.') lub dwóch, ale ponieważ jest to natywna forma tablic, możesz uzyskać zaskakujące przyspieszenie. Na przykład zamiana wymiary od A i g:

A = randn(3000,10000); 
g = zeros(1,10000); 

tic 
for i = 1:100 
    sub = randperm(10000,500); % Taking @Dan's suggestion 
    b = randn(1,3000);   % b is now a row vector 
    g(sub) = g(sub)+b*A(:,sub); % multiply across rows instead 
end 
toc 

można transponować wyjście, jeśli zajdzie taka potrzeba. Na moim komputerze jest to ponad 50% szybciej niż w pierwszym przypadku.

Wierzę, że przynajmniej jednym z powodów jest to, że BLAS/LAPACK może użyć w tym przypadku loop unrolling.