最快的稀疏布尔矩阵表示和乘法方法是什么？

Question

因此，我使用的是布尔矩阵，其维度通常为几十到几百，它们通常非常稀疏（大多数行和列中只有2-4个非零元素），我的运行时间主要受它们的乘法支配。

在这种情况下，哪种数据结构最适合加速乘法？

目前，我将每个矩阵按行存储在连续的位集中（64位长整型数组），并使用基本算法进行乘法运算，但使用了快速定位单词中下一个设置位的操作以及位掩码操作的向量化来加速稀疏性。

也许我应该使用一些稀疏表示法吗？

- jkff

---

“dimension is usually a couple dozen to a couple hundred”是什么意思？这听起来更像是元素的数量（或一个维度的长度），而不是维度（即指定选取一个元素所需的坐标数）。 - Rex Kerr

Answer 1

您可能希望考虑使用四叉树表示法。四叉树可以很好地编码稀疏矩阵，并且非常适合实现递归乘法（高速缓存效率）。将基本情况设置为8x8矩阵，这样您就可以将乘法实现为一个（汇编优化？）64位乘64位的操作。

- Keith Randall

---

有人需要将此代码移植到C/C++ :) https://github.com/BNFC/bnfc/blob/master/source/runtime/Data/Matrix/Quad.hs - Chad Brewbaker

Answer 2

我认为使用稀疏表示是有意义的。即使只是一组非零索引，你也会获得更好的性能。

例如，对于一个100×100的矩阵，其中有300个非零元素，使用二维数组表示，乘法需要100×100×100=1,000,000个“操作”。而使用索引集仅需要300×300=90,000个操作。（当然，这些操作不能直接比较。）

- svick

---

是的，这就是关键：这些操作实际上并不是直接可比较的，因为在索引集合上执行90000次操作是否比在64位掩码上进行1000000次矢量化操作更快并不明显。我想我只能实现它并查看结果了。 - jkff

Answer 3

一个由1、x和y组成的列表。例如：

[0,2,0,12,0,60,1,2,1,39 ... 等等]

这意味着在0,2处有一个1，在0,12处有一个1，以此类推。

好处是你不需要新的数据类型，而且解析起来非常简单。

要进行乘法运算，你需要查找所有匹配/部分匹配的索引。

- TaslemGuy

---

我认为创建新的数据类型更加清晰易懂，也更容易操作。 - svick

这就是关键所在：考虑到当前实现是通过对64位位掩码进行向量操作来实现的，非常低级高效，我不确定新实现是否会更快。看起来我只能去实现它了。 - jkff