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

我想通過B = A^T * A矩陣進行一些計算。但B也應該稀疏，因爲稀疏度爲A。

我如何計算B的「掩碼」？「掩碼」是壓縮行存儲的列索引和行偏移量。

我看到的唯一方法是在嵌套循環（通過i和j）遍歷行並檢查B的（i，j）元素爲非零，如果A的行i和j至少有一個公共非 - 零列。但我認爲很慢。

PS對不起，我的英文不好

如果有人認爲這個問題是不正確的我打開建議 –

我不認爲你的假設，B必須是稀疏的，是真的。只要考慮A =（1，...，1; 0..0; 0 ... 0; 0..0; ...），即第一行中的每個元素都是1，那麼B中的每個元素都將是非零的！ – ead

我不確定。如果A = [[1,1]，[0,0]]，則B = [[1,0]，[0,0]]。因爲只有第一行和第一行之間的產品非零（我剛剛用numpy檢查過） –

我認爲你可以做到這一點在O(n^2)，與n - 非零元素的數量在矩陣A。

考慮Bij=sum Aki*Akj，Bij可能只有0，如果有一個k與Aki和Akj - 非零。

迭代通過A並通過A = Ak（連續訪問k第i行的非零元素的所有非零元素，此起彼伏的行中的一個元素，我想壓縮行存儲（CRS） - 爲CCS需要迭代在列），得到下面的算法：

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

至於兩個迴路只需要觸摸的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的形式，沒有其他信息。

2016-03-15 22:49:36 ead

回答