arrays - 两个稀疏矩阵相乘的算法

Question

我在 Matlab 中工作，我将稀疏矩阵存储为具有字段的结构数组:行、列和数据。因此，对于两个矩阵，我将有一个数组集合，为每个非零条目提供(行、列、数据)。

我正在尝试编写一个有效的程序来以这种形式将两个稀疏矩阵相乘，但遇到了一些困难。

然而，这存在数组中重复条目的问题，当我真的想添加它们时。

很感谢任何形式的帮助。

Answer 1

首先，您可以使用 ismember 来消除 forloops。如下:

[lia,locb] = ismember([a.column],[b.row]);
loca = find(lia);

这会给你 loca和 locb ，分别是答案矩阵的行索引和列索引。您可以按如下方式确定最终数组中的目标条目:

[dest,~,i] = unique([loca',locb'],'rows');
dest_row = num2cell(dest(:,1));
dest_col = num2cell(dest(:,2));

在这里，我们使用基于行的唯一排序来确保我们不会在最终矩阵中重复条目。 i索引数组是从初始数据(可能有重复)到最终数据(无重复)的映射。然后，您可以使用 accumarray 基于这些索引对数据求和。 :

dest_data = num2cell(accumarray(i,[a(loca).data].*[b(locb).data]));

我们将其中的每一个都转换为元胞数组，以便更容易地形成最终矩阵，您很快就会看到。假设你还没有，你应该预先分配最终的矩阵:

len = size(dest,1); % number of unique entries in the final matrix
c = repmat(struct('row',[],'column',[],'data',[]),len,1);

我们现在可以在最终矩阵中设置值:

[c.row] = dest_row{:};
[c.column] = dest_col{:};
[c.data] = dest_data{:};