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

Question

所以，我使用的布尔矩阵的维数通常是几十到几百，它们通常是相当稀疏的(在大多数行和列中只有2-4个非零)，并且我的运行时主要由它们的乘法控制。

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

目前，我将每个矩阵按行存储在一个连续的位集(64位长的数组)中，并使用基本的标准算法将它们相乘，只是通过在字中定位下一组位的快速操作以及通过位掩码操作进行矢量化来加速稀疏性。

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

Answer 1

您可能需要考虑使用四叉树表示法。四叉树可以很好地对稀疏矩阵进行编码，并适合于非常简单(和缓存效率高)的递归乘法实现。将基本情况设置为8x8矩阵，这样您就可以将乘法实现为(汇编优化的)64位乘以64位运算。

Answer 2

我认为使用稀疏表示是有意义的。即使使用像一组非零索引这样简单的东西，我认为您也会获得更好的性能。

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

Answer 3

1的x和y的列表。例如：

0，2，0，12，0，60，1，2，1，39...等

这意味着在0处有1，在0,12处有2，1，等等。

好的方面是，您实际上不需要新的数据类型，而且解析起来非常简单。

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