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

Question

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

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

目前我将每个矩阵存储在一个连续的bitset(64位长的数组)中,并且基本上将它们与标准算法相乘,只需加快稀疏性,快速操作就可以找到一个字中的下​​一个设置位,以及通过位掩码操作进行矢量化.

我是否应该使用一些稀疏表示呢？

Answer 1

您可能需要考虑使用四叉树表示。四叉树可以很好地编码稀疏矩阵，并且适合于非常简单（且缓存高效）的递归乘法实现。将基本情况设为 8x8 矩阵，以便您可以将乘法实现为（汇编优化？）64 位乘 64 位运算。

Answer 2

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

\n\n

例如，对于具有 300 个非零元素的 100\xc3\x97100 矩阵，使用 2D 数组表示，乘法需要 100\xc3\x97100\xc3\x97100=1,000,000 \xe2\x80\x9coperations\xe2\x80\x9d。使用索引集仅需要 300\xc3\x97300=90,000 次操作。（当然这些操作不能直接比较。）

\n