ベクトルの部分行列との乗算が遅い

Question

私は背の高い行列（以下の例は10000 x 3000です）を持ち、行のサブセット（たとえば500行）で内側の製品を取りたいと考えています。これは、何回も何回も（実際には100回、実際にはさらに多くの時間）ランダムに選択された異なる行で繰り返されます。インデックスのA(sub,:)はかなり遅いことが判明しました。私の例では、実際に必要とされる500を選択して乗算するのではなく、フルマトリクスのA（つまり10000行）を乗算する方が良いでしょう。

行インデックス（sub = randperm(10000);sub = sub(1:500);）のランダム生成は計算上安価です。私は公正になるために両方のループに入れました。

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 

問題は次のとおりです。行のサブセットのみが実際に必要な場合、スピードアップする方法はありますか？

Answer 1

列の代わりに行を掛けてみてください。これにより、データを並べ替えるか、またはスカラトランスポーズ（.'）または2つを適用する必要がありますが、それは配列のネイティブフォームなので、驚くほど高速化される可能性があります。例えば、Aと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 

必要になる場合は、出力を転置することができます。私のコンピュータでは、これは最初のケースよりも50％以上高速です。

私はBLAS/LAPACKがこの場合にはloop unrollingを使用できるという根本的な理由の少なくとも1つは信じています。