如何在 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% 的零项。

C为整型数组

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

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

Answer 1

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

编辑

在了解您的问题背景后，我会建议执行以下程序。

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

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

给定A的大小(b x 750,000)和密度(0.25%)，C的密度为99.1%；每个列索引的平均长度为 1875.

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

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

如何在 python 中有效地计算（稀疏）位矩阵的矩阵乘积

How to calculate matrix product on (sparse) bit matrix efficiently in python

python

bit-manipulation

scipy

intel-mkl