Matlab 重复矩阵乘法 - 循环与内置性能

Question

给定一个矩阵 A，我需要与其他 n 向量相乘 Bi（即 i=1...n）。 A 的大小可以类似于 5000x5000，因此 Bi 类似于 5000x1.

如果我通过以下方式评价产品：

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

结果比计算以下乘积慢（数量级）：

%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

问题是向量 Bi 的数量 n 可能太大而无法存储在内存中，例如 n=300000，所以我需要使用循环方法，其中每次我评估产品时，使用它然后丢弃向量 Bi.

为什么这种方法与直接乘法相比这么慢，有没有办法克服这个问题？

Answer 1

您可以尝试循环批处理，例如

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

并调整 k 为您找到速度和内存的最佳平衡点。

MATLAB 的循环很慢，因为它是一种解释型语言。所以它必须即时处理很多事情。现在由于 JIT 编译器，循环得到了很大的改进，但与用 C 编写和编译的 built-in 函数相比，它们仍然很慢。此外，它们使用真正尖端的超快速矩阵乘法算法，与您通过循环实现的相当幼稚的算法相比，这也有助于 speed-up 您正在经历的。

Answer 2

为简单起见，我的回答将假设一个 n-by-n 方阵 A，但对于非方阵也是如此。

您的循环方法使用矩阵向量乘法。朴素的解决方案也是最著名的，导致运行时间为 O(n^2)，重复 n 次。您最终的总运行时间为 O(n^3)。

对于矩阵乘法，有更好的方法。最著名的算法只需要略低于 O(n^2.4) 的运行时间，这使得它对于大数来说要快得多。

使用矩阵乘法一次乘以多个向量 Bi 时，您将获得更好的运行时间。这不会达到纯矩阵乘法的性能，但使用更大的 b 切片可能是最快的内存效率解决方案。

针对不同讨论方法的一些代码：

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

除了 you might try going parallel, provided you have enough cores and large enough operations to make it profitable (see for more details on memory consumption of parfor):

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

我无法在 docs on mtimes（* 运算符）中看到它是否隐式多线程，但我认为值得一试。

Answer 4

为了将每个数组与矩阵相乘，只需将矩阵与一个矩阵相乘，该矩阵的列将包含您想要的数组。

所以如果你想检查这个

如果

size(a)=3,3

然后

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

是真的

这样可以节省很多循环时间

Matlab 重复矩阵乘法 - 循环与内置性能

Matlab repeated matrix multiplication - loop vs built-in performances

performance

matlab

matrix

matrix-multiplication

memory-efficient