matlab - 向量与子矩阵的乘法很慢

Question

我有一个高矩阵(下面的示例是 10000×3000)，我想用它的行的子集(例如 500 行)来获取内积。这对不同的、随机选择的行重复多次(在示例中为 100 次，但实际上更多次)。事实证明，索引 A(sub,:) 相当慢。在我的示例中，最好乘以整个矩阵 A(即 10000 行)，而不是选择性地选择和乘以实际需要的 500。

行索引的随机生成 (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

尝试乘以行而不是列。这可能需要您重新排列数据或应用标量转置 (.') 或两个，但由于这是数组的 native 形式，您可能会获得惊人的加速。例如，交换 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在这种情况下。