matlab - 具有大量零的矩阵的高效乘法

Question

我有两个采用以下形式的数组:

    0…0…0 0 0 0…0        0…0…0 0 0 0…0
    ⋮  ⋮ ⋮  ⋮ ⋮  ⋮ ⋮        ⋮  ⋮ ⋮  ⋮ ⋮  ⋮ ⋮
    0…0 0 0 0 0…0        0…0 0 0 0 0…0
A = 0…0 1 2 3 0…0    B = 0…0 9 8 7 0…0
    0…0 4 5 6 0…0        0…0 6 5 4 0…0
    0…0 0 0 0 0…0        0…0 0 0 0 0…0
    ⋮  ⋮ ⋮  ⋮ ⋮  ⋮ ⋮        ⋮  ⋮ ⋮  ⋮ ⋮  ⋮ ⋮
    0…0…0 0 0 0…0        0…0…0 0 0 0…0

A 和 B 的非零区域的大小可能不完全相同，但上图已经变得有点笨拙了。

最终，我想要的值是 sum(sum(A .* B))。我觉得一定有一种方法可以只与非零元素相乘，但我能想到的每一种方法似乎都会导致 MATLAB 复制矩阵，这完全破坏了通过减少运算次数所获得的任何 yield 。 B 可重复用于内部循环的多次迭代，因此我可以在多次循环迭代中分摊 B 上昂贵的计算。

到目前为止我已经尝试过以下方法:

天真的方法:

function C = innerLoop(A, B)
    C = sum(sum(A .* B))
end

innerLoop 使用此方法进行 86,000 次调用大约需要 4.3 秒。 (基于 MATLAB 的“运行和时间”功能。)

收缩B首先:

function B = resize(self, B1)
    rows = abs(sum(B, 2)) > 1e-4;
    top = find(rows, 1, 'first');
    bot = find(rows, 1, 'last');

    cols = abs(sum(B, 1)) > 1e-4;
    left = find(cols, 1, 'first');
    right = find(cols, 1, 'last');

    self.Rows = top:bot; % Store in class properties for use in inner loop
    self.Cols = left:right; % Store in class properties for use in inner loop
    B = B(top:bot, left:right);
end

function C = innerLoop(A, B)
    result = A(self.Rows, self.Cols) .* B;
    C = sum(sum(result));
end

我希望这种方法能够让 MATLAB 意识到我没有写入 A 并删除副本，但这种方法在 innerLoop 中花费了大约 6.8 秒。

我还尝试只计算 innerLoop 外部的偏移量，希望 MATLAB 能够识别出我在两个矩阵上使用相同下标来优化的事实:

function B = resize(self, B1)
    rows = abs(sum(B, 2)) > 1e-4;
    top = find(rows, 1, 'first');
    bot = find(rows, 1, 'last');

    cols = abs(sum(B, 1)) > 1e-4;
    left = find(cols, 1, 'first');
    right = find(cols, 1, 'last');

    self.Rows = top:bot; % Store in class properties for use in inner loop
    self.Cols = left:right; % Store in class properties for use in inner loop
end

function C = innerLoop(A, B)
    result = A(self.Rows, self.Cols) .* B(self.Rows, self.Cols);
    C = sum(sum(result));
end

不幸的是，这是迄今为止最慢的，大约 8.6 秒。

我还尝试使用以下代码循环:

function C = innerLoop(A, B)
    C = 0;
    for i = self.Rows
        for j = self.Cols
            C = C + field(i, j) * self.Sensitivity.Z(i, j);
        end
    end
end

我知道 MATLAB 中的循环过去非常慢，但我读过一些论文，表明它比以前快得多。也就是说，如果循环版本完成运行，我会让您知道它花了多长时间，但现在已经超过几分钟了。

任何有关如何优化此问题的建议将不胜感激!

Answer 1

您可以使用稀疏矩阵来解决此问题。 Matlab 自动处理不同大小的“非稀疏部分”。要获得稀疏矩阵，请使用稀疏函数。之后，您可以进行逐元素乘法，然后在单独的行中对 C 的所有元素求和。

A = [0 0 0 0 0 0 0;
     0 0 0 0 0 0 0;
     0 0 1 2 3 0 0;
     0 0 4 5 6 0 0;
     0 0 0 0 0 0 0;
     0 0 0 0 0 0 0];

B = [0 0 0 0 0 0 0;
     0 0 0 0 0 0 0;
     0 0 9 8 7 0 0;
     0 0 6 5 4 0 0;
     0 0 0 0 0 0 0;
     0 0 0 0 0 0 0];

A = sparse(A);
B = sparse(B);

C = A .* B;
sum(C(:))