用于乘两个稀疏矩阵的算法

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{:};