具有大量零的矩阵的有效乘法

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复制矩阵,这完全破坏了通过减少操作数量而获得的任何收益.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并删除副本,但这种方法花了大约6.8秒innerLoop.

我也尝试过计算外部偏移量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自动处理不同大小的"非稀疏部分".要获得稀疏矩阵,使用sparse-function.之后,您可以执行逐元素乘法,然后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(:))