如何高效地垂直合并稀疏矩阵

Question

我的目标是将许多稀疏矩阵组合成一个大的稀疏矩阵。我能想到的两个想法是(1)创建一个大的稀疏矩阵并覆盖某些块，(2)单独创建这些块，使用vertcat来形成最终的稀疏矩阵。然而，我读到过覆盖稀疏矩阵非常低效，我也读到过vertcat并不是计算效率很高的选择。(我没有考虑使用for循环，因为它们非常低效。)

那么我还有哪些其他选择呢？ 编辑: 我所说的"组合"是指将矩阵"粘"在一起(垂直方向)，元素之间没有交互。

- TheRealFakeNews

---

如果您将它们直接相加会发生什么？更具体地说，您的矩阵的维度是什么，您的“组合”矩阵在您的书中是什么样子的？您能给一个玩具示例吗？ - Floris

@Floris 的维度范围可以从2x2到2^18 x 2^18，或者是Matlab脚本可以处理的最大值。我认为在2^18左右会产生错误。一个玩具示例可以是任何任意的东西。我的矩阵中唯一固定的是第一个和最后一个块，它们是speye，但是中间的所有内容都不同（尽管它们的大小是固定的）。 - TheRealFakeNews

@Floris，我也无法添加它们，因为我找不到适用于所有矩阵的全局索引。不过我刚看到了你的帖子，所以我认为这不会成为问题。 - TheRealFakeNews

我想我的问题是“你打算如何合并”。当你将一个10x10和另一个10x10合并时，结果是10x10还是20x10？ - Floris

@Floris 哦，我明白了。抱歉，10x10和5x10的组合会变成15x10。这些元素之间没有互动。 - TheRealFakeNews

Answer 1

根据 Matlab 帮助文档，您可以使用以下代码“分解”稀疏矩阵：

[i,j,s] = find(S);

这意味着如果你有两个矩阵S和T，并且你想要（有效地）将它们垂直连接起来，你可以这样做：

[is, js, ss] = find(S);
[it, jt, st] = find(T);
ST = sparse([is; it + size(S,1)], [js; jt], [ss; st]);

不确定这是否非常高效...但我猜想它并不太差。

编辑：在我的机器上，使用密度为1%的2000x1000稀疏矩阵与另一个密度为2%的矩阵结合，上述代码运行时间为0.016秒。只是做[S;T]快10倍。你认为垂直拼接很慢是什么原因？

编辑2：假设您需要对“许多”稀疏矩阵执行此操作，则以下方法可行（假设您希望将它们全部“放在同一位置”）：

m = 1000; n = 2000; density = 0.01;
N = 100;
Q = cell(1, N);
is = Q;
js = Q;
ss = Q;
numrows = 0; % keep track of dimensions so far

for ii = 1:N
    Q{ii} = sprandn(m+ii, n-jj, density); % so each matrix has different size
    [a b c] = find(Q{ii});
    sz = size(Q{ii}); 
    is{ii} = a' + numrows; js{ii}=b'; ss{ii}=c'; % append "on the corner"
    numrows = numrows + sz(1); % keep track of the size
end

tic
ST = sparse([is{:}], [js{:}], [ss{:}]);
fprintf(1, 'using find takes %.2f sec\n', toc);

输出：

using find takes 0.63 sec

这种方法的最大优点是你不需要在个别稀疏数组中拥有相同数量的列...这将由命令自动解决，它会将缺失的列视为全部为零。

- Floris

---

那么你还建议使用vertcat或find吗？ - TheRealFakeNews

find 方法（以及我使用 [is {:}] 进行的隐式 horzcat）似乎非常高效。您可能会问自己如何生成原始（源）稀疏矩阵；如果一开始就是在 (i，j，s) 格式中拥有它们，您可能永远不需要中间的 find 步骤... - Floris

在for循环的第一行，你是不是指的n-ii？jj没有定义吧？ - TheRealFakeNews

当然可以 - 打错了。我只是想制作不同大小的矩阵，以证明我能够做到...我无法从运行Matlab的计算机上复制/粘贴（长话短说），所以不得不手动输入。我的错误。 - Floris

Answer 2

考虑到已经给出的答案。

我稍微改变了实验，以便能够垂直拼接矩阵（它们应该具有相同的宽度），所以您不需要通过提取 ii（被错误输入为 jj）来调整n。

这种方法

tic
ST = sparse([is{:}], [js{:}], [ss{:}]);
fprintf(1, 'using find takes %.2f sec\n', toc);

使用0.45秒的速度比这个慢得多。

tic
ST = vertcat(Q{:});
fprintf(1, 'using vertcat takes %.2f sec\n', toc);

平均速度为0.18秒。

我还使用分析器进行了检查，第一个示例预期会更慢，因为至少内存分配高100倍。很可能是因为[ss {:}]数组构造显式地将数据复制到新数组中。

然而，即使使用预计算向量，速度也是0.3秒，而vertcat的速度为0.18秒。

因此，我建议在原始问题中使用vertcat是更好的选择。至少在2021年是这样的 :)

- ghastly_kitten