sparse-matrix - 稀疏矩阵及其三元组表示

Question

这个稀疏矩阵和它的三元组表示并没有进入我的脑海......要么它有点棘手，要么我正在学习的资源真的不是那么好......这里是 URI 稀疏矩阵幻灯片

因此，如果您有任何要分享的内容，请继续。

谢谢

Answer 1

您引用的 ppt 演示文稿非常简单。基本思想是您只想记录不为零的数组条目。当然，您跳过了一堆 0 条目，因此您还需要记录行和列索引以及非零值。

他提出了几种方法来做到这一点。一个只是一个长列表，条目按行然后列排序。然后他查看了几个矩阵运算的性能。

1）转置非常快；只是一种按列排列的索引列表，然后基本上是行。2）两个矩阵相加也很快；您遍历两个矩阵的两个列表一起适当地添加值，有点像两个有序列表的合并。请注意，您只遍历每个列表一次。

对于链表选项，这两个操作花费的时间稍长。

在内存中使用完整矩阵时，这些操作需要更长的时间，因为您基本上几乎是连续地进行页面进出，这比主要在高速缓存中工作要慢得多。

他没有测量矩阵乘法或计算逆的性能。也许在使用稀疏矩阵的应用程序中通常不需要这些操作。也许您可以将它们视为一种练习。