• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

稀疏矩阵表示方法

math admin 2年前 (2017-07-20) 1531次浏览 0个评论 扫描二维码

在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。在使用计算机存储和操作稀疏矩阵时,经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性,通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是,由于过大的尺寸,标准的算法经常无法操作这些稀疏矩阵。

三元组表示法

按照压缩存储的概念,只存储稀疏矩阵的非零元素。因此,除了存储非零元的值之外,还必须同时记录下它所在的行和列的位置(i,j)。反之,一个三元组(i,j,aij) 唯一确定了矩阵 A 的一个非零元素。由此,稀疏矩阵可以用表示非零元的三元组及其行列数和非零元的个数唯一确定。例如,下面三元组表:
((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),(6,7,8))
最后一个三元组(6,7,8),表示系数矩阵为 6 行 7 列,包含 8 个非零元。

十字链表示法

用三元组表法表示的稀疏矩阵,比起用二维数组存储,节约了空间,并且使得矩阵某些运算的运算时间比经典算法还少。但是,在进行矩阵加法、减法和乘法等运算时,有时矩阵中的非零元素的位置和个数会发生很大的变化。如 A=A+B,将矩阵 B 加到矩阵 A 上,此时,若还用三元组的表示法,势必会为了保持三元组表“以行序为主序”,而大量移动元素。十字链表能够灵活地插入因运算而产生的新的非零元素、删除因运算而产生的新的零元素,实现矩阵的各种运算。

在十字链表中,矩阵的每一个非零元素用一个结点表示,该结点除了(row,col,value)以外,还要有以下两个链域:

  • right: 用于链接同一行中的下一个非零元素
  • down:用以链接同一列中的下一个非零元素

整个结点的结构如图 5.22 所示。

在十字链表中,同一行的非零元素通过 right 域链接成一个单链表。同一列的非零元素通过 down 域链接成一个单链表。这样,矩阵中任一非零元素 Mij 所对应的结点既处在第 i 行的行链表上,又处在第 j 列的列链表上,这好像是处在一个十字交叉路口上,所以称其为十字链表。同时我们再附设一个存放所有行链表的头指针的的一维数组,和一个存放所有列链表的头指针的的一维数组。

整个十字链表的结构如图 5.23 所示。

十字链表

 转载自 http://blog.csdn.net/u011080472/article/details/52344080

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明稀疏矩阵表示方法
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!