稀疏矩陣和它的三元組表示

Question

這個稀疏矩陣和它的3元組表示並沒有進入我的腦海...... 要麼它的有點棘手，要麼我的學習資源真的不是那麼好... 這裏是URI Sparse Matrix Slide

所以，如果你有任何東西要分享，請繼續。

謝謝

Answer 1

您引用的PPT演示文稿非常簡單。基本思想是您只想記錄非零的數組條目。當然，你跳過了一堆0條目，所以你還需要記錄行和列索引以及非零值。

他提出了幾種方法來做到這一點。一個只是一個很長的列表，按行和列排序。然後他看着一些矩陣操作的表現。

1）移調非常快;基本上只是一列列在索引上的列然後行。 2）添加兩個矩陣也很快;您可以遍歷兩個矩陣的兩個列表，一起增加值，就像兩個有序列表的合併一樣。請注意，您只能遍歷每個列表一次。

這兩個操作的鏈接列表選項的時間略長。

這些操作在內存中使用全矩陣時會花費更長時間，因爲基本上可以連續分頁和分頁，這比主要在高速緩存中工作要慢得多。

他不測量矩陣乘法或計算逆矩陣的性能。也許在使用稀疏矩陣的應用程序中通常不需要這些操作。也許你可以把它們想象成一個練習。