如何找到矩阵 A^T * A 的非零元素，其中 A 是稀疏 (crs/ccs) 矩阵

Question

我有非常稀疏的大矩阵A（A是一个压缩的行存储）

我想对矩阵执行一些计算B = A^T * A。但是B也应该稀疏，因为A的稀疏性。

如何计算B的"掩码"？"掩码"是压缩行存储的列索引和行偏移量。

我看到的唯一方法是遍历嵌套循环中的行（通过 i 和 j），如果 A 的行 i 和 j 至少有一个公共非零列，则检查 B 的 （i， j） 元素是否为非零。但我认为很慢。

PS对不起我的英语不好

Answer 1

我认为你可以在O(n^2)中做到这一点，矩阵A中非零元素的数量n .

考虑Bij=sum Aki*Akj，Bij如果存在具有 Aki 和 Akj - 非零的k，则只能是非零。

遍历A的所有非零元素和A = Ak k行的非零元素（连续访问，行中的一个元素接一个，我假设压缩行存储 （crs） - 对于 ccs，您需要迭代列）产生以下算法：

for (k, i) in indices(nonzero(A)):
    for j in indices(nonzero(Ak)):
      Bij=nonzero

由于 for 循环只需要按行顺序接触A的非零元素（这是至关重要的！），并且操作Bij=nonzero成本O(1)，如果您使用例如哈希集或布尔字段，则生成的运行时间必须O(n^2)。

对于A=[1,..,1; 0,..,0; ...; 0, ..,0]即第一行非零元素的矩阵，您可以看到，确实存在最坏的情况，需要n^2操作。例如：

A=[1,1;0,0] -> A^T=[1,0;1,0]
B=A^t*A=[1,1;1,1]

我不确定它与您的方法有何不同，但如果您没有关于矩阵A形式的其他信息，我认为没有比这更快的东西了.