两个稀疏矩阵相乘的算法

Question

我正在使用Matlab，并将稀疏矩阵存储为结构数组，其包含行、列和数据三个字段。因此，对于两个矩阵，我将获得一组数组，每个数组都提供每个非零条目的（行、列、数据）。

我试图编写一个高效的程序，在这种形式下相乘两个稀疏矩阵，但遇到了一些困难。

然而，这种方法存在一个问题，数组中会有重复的条目，而我实际上想要进行相加。

任何帮助都将不胜感激。

- Wooster

---

你是在做这个作为练习，对吧？你知道Matlab有稀疏矩阵的内置功能吗？ - Luis Mendo

是的，我正在做这个练习来尝试理解那些函数！谢谢。 - Wooster

我想到了一种方法，每当有列和行匹配时，我们就再做一个循环，循环遍历所有之前的匹配，这将有所贡献，但在那里再放一个循环似乎有点过度杀伐？ - Wooster

我不确定这会不会帮助你理解。用于矩阵乘法的函数并非在Matlab中编写，而是在C语言中编写。因此，在Matlab中执行最有效的方法可能在C语言中并不是最有效的。 - patrik

@Wooster：你选择的稀疏矩阵存储数据结构并不是很高效：https://en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix - Amro

Answer 1

首先，您可以通过使用 ismember 来避免使用 for 循环，具体方法如下：

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

- MrAzzaman