python - 如何在Python中有效计算(稀疏)位矩阵上的矩阵乘积

Question

位数组之间的普通矩阵乘积:

           1, 0, 0
Matrix A = 1, 1, 1
           0, 0, 1

                 1, 1, 0
Transpose of A = 0, 1, 0
                 0, 1, 1

C = Matrix A times (Transpose of Matrix A)

    1, 1, 0
C = 1, 3, 1
    0, 1, 1

A 是一个 1 和 0 的位数组。实际矩阵 A 很大，大约有 0.25% 的 1 项和 99.75% 的 0 项。

C 是一个整数数组。

如何在不使用大量内存的情况下快速计算？

目前，我正在 python 中使用 scipy 的稀疏矩阵乘法例程来压缩浮点 1.0 和 0.0 的稀疏行矩阵。我还尝试直接调用 mkl 库中的 c 函数以减少内存使用。

Answer 1

现有的性能库(例如 MKL)始终使用 float/double 作为数据类型。与将 A 转换为浮点 CSR，然后调用 .dot() 或某些 MKL 例程相比，您可能会发现编写自己的 bit-mat-mul 代码更快。您甚至不需要乘法运算。它只计算位数。

编辑

了解您的提问背景后，我建议您执行以下步骤。

1. 将数组 A 转换为 CSR 格式并仅存储 col 索引和 row ptr；
2. 对于 A 的每一行 i 和 j 行，计算公共(public) col 索引的数量并将结果存储在 C(i, j) 中，其中 i<=j 仅当 C 是对称的时。如果列索引已排序，这会很快。

稠密矩阵 C 就是您想要的。

给定 A 的尺寸 (b x 750,000) 和密度 (0.25%)，C 的密度为 99.1%；每个 col 索引的平均长度为 1875。

所以你的问题变成了计算 2 个 1875-D 向量的公共(public)元素的数量 b*(b+1)/2 次。

for 循环的速度似乎是唯一剩下的问题。