时间戳

首页 > 解决方案 > 3 个稀疏矩阵的有效乘积，可创建密集中间体

algorithm - 3 个稀疏矩阵的有效乘积，可创建密集中间体

问题描述

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

我需要取 的矩阵乘积AB，这会产生一个密集矩阵。之后，我需要AB (element 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)

标签： algorithmsparse-matrixlinear-algebraeigennumerical-methods

解决方案

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

也许 R 中有一个三角形计数社区检测可以适应您的用例。

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

推荐阅读