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

Question

我有非常稀疏的大矩阵A（A是一个compressed row storage）

我想对 B = A^T * A 矩阵执行一些计算。但是 B 由于 A.

的稀疏性也应该是稀疏的

我如何计算 B 的 "mask"？ "Mask"是压缩行存储的列索引和行偏移。

我看到的唯一方法是迭代嵌套循环中的行（通过 i 和 j），如果 A 的行 i 和 j 至少有一个共同点，则检查 B 的 (i, j) 元素是否为非零非零列。但是我觉得很慢。

PS对不起我的英语不好

Answer 1

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

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

遍历 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)，如果您使用 for例如哈希集或布尔字段，结果运行时间必须是 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。

How to find non-zero elements of matrix A^T * A where A is sparse (crs/ccs) matrix?