稀疏矩阵

                     

贡献者: addis

   稀疏矩阵(Sparse Matrix)有不同的储存方式(数据结构),这里介绍几种常见的1。本文的数组索引从 0 开始。

   一些常见的稀疏矩阵包如

1. Banded

   带对角矩阵(Banded Matrix)只储存矩阵主对角线上下的若干条对角线,上带宽和下带宽分别指定主对角线上面和下面有几条对角线,例如三对角矩阵的上带宽和下带宽都是 1。带内即使有矩阵元为零也必须储存。这样就可以按照 row major 或者 column major 来储存。详见 “数据结构:带对角矩阵”。

2. Coordinate List(COO)

   COO 格式列出非零矩阵元和对应的行标列标。通常将它们储存为三个数组 aiaja,顺序任意。除此之外,有时还需要储存三个数组的长度 nnz(none zero)以及矩阵的尺寸。

3. Compressed Sparse Row(CSR)

   也叫 Compressed Row Storage(CRS),这种格式做矩阵与矢量相乘较快,因为需要逐行获取矩阵的值。

   CRS 格式储存为三个一维数组 aiaja,想象 COO 格式的矩阵元按照行主序排列后储存,那么行标将会出现类似 0,0,1,1,1,1,2,2,3,3,3 这样的重复。所以为了提高效率可以把行标矩阵 ia 的信息压缩,令 ia[i] 表示第 i 行上方所有行的矩阵元个数,ia 的长度是矩阵行数加一。所以 ia[0] 恒为零,且最后一个元素就是非零元的个数 Nnz。第 i 行矩阵元从 a[ia[i]] 一直到 a[ia[i+1]-1]。注意如果矩阵的第 i 行是空的,那么 ia[i+1] 等于 ia[i]ia[i+1]-1 反而比 ia[i] 要小,于是循环 for(n=ia[i]; n<ia[i+1]; ++n) 不执行。ja 和 COO 一样仍然是对应矩阵元的列标。

4. Compressed Sparse Column(CSC)

   也叫 Compressed Column Storage(CCS),与 CRS 一样,只是改为 column major。


1. ^ 参考 Wikipedia 相关页面


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利