3个稀疏矩阵的有效积，产生密集的中间物

Question

我有3个都是稀疏的矩阵A，B和C。

我需要取AB的矩阵乘积，这导致矩阵密集。在那之后，我需要AB的wise wise乘积C。C是稀疏的，因此按元素相乘将使大多数密集积AB归零，从而再次导致稀疏矩阵。

知道，我正在尝试制定一种不实现AB的所有密集组件的策略。

如果C_ {i，J}为0，那么我不应该实现AB_ {i，j}。这意味着我可以跳过A_ {row i}和B_ {col j}的点积。但是在A的行上编写一个for循环以挑选出我想实现的行似乎效率很低。

还有另一种方法可以聪明地进行乘法吗？

这里是R中的示例数据生成器，尽管我拥有的真实产品AB比该生成器更密集。任何编程语言的FWIW帮助都是有用的，不一定是R。（Eigen会很棒！）

require(Matrix)

n = 10000
p = 100
A = rsparsematrix(n, p, .1)
B = rsparsematrix(p, p, .1)
C = rsparsematrix(n, p, .1)

Answer 1

这与三角形计数密切相关。如果A，B和C都是二元矩阵，则可以将它们解释为三方图的邻接矩阵，并为C中的每个边计数其属于多少个三角形。

也许在R中有一个三角计数的社区检测，可以根据您的用例进行调整。

在这样的库下面可能有以下技巧（我应该引用，但不要随便使用）。它涉及按度对图的节点进行排序，并将所有出局边从低度引导到高度。然后，对于每个节点，测试每对向外的边缘（楔形），以完成该边缘。