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

我有非常稀疏的大矩阵A（A是acompressed row storage）
我想对B = A^T * A矩阵进行一些计算。但由于B的稀疏性，A也应该稀疏。
如何计算B的“掩码”？mask”是压缩行存储的列索引和行偏移量。
我看到的唯一方法是遍历嵌套循环中的行（通过i和j），如果A的行i和j至少有一个公共的非零列，则将B的（i，j）元素检查为非零但我觉得很慢。
对不起，我英语不好

最佳答案

我想你可以用O(n^2)来做，矩阵中有n个非零元素。
考虑到A，Bij=sum Aki*Akj只有在存在Bij和k-非零的Aki时才能为非零。
遍历Akj的所有非零元素和A的第k行的非零元素（连续访问，一行接一行的元素，我假设压缩行存储（CRS）-对于需要在列上迭代的CC），生成以下算法：

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

因为这两个for循环只需要按行顺序接触A = Ak的非零元素（这很关键！）如果使用例如散列集或布尔字段，则操作A的成本Bij=nonzero，则生成的运行时间必须O(1)。
对于O(n^2)即第一行非零元素的矩阵，您可以看到，确实存在最坏的情况，需要A=[1,..,1; 0,..,0; ...; 0, ..,0]操作。
例如：

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

我不确定它是否与您的方法不同，但如果您没有关于矩阵形式的额外信息，我认为没有更快的方法。

关于algorithm - 如何找到矩阵A ^ T * A的非零元素，其中A是稀疏(crs/ccs)矩阵？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36013785/