万维百科

稀疏矩阵

稀疏矩阵的例子
上述稀疏矩阵仅包含9个非零元素,另外包含26个零元。其稀疏度为74%,密度为26%。
计算有限元问题时得到的稀疏矩阵。非零元素用黑点表示。

稀疏矩阵(英语:sparse matrix),在数值分析中,是其元素大部分为零的矩阵。反之,如果大部分元素都非零,则这个矩阵是稠密的。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。

在使用计算机存储和操作稀疏矩阵时,经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性,通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是,由于过大的尺寸,标准的算法经常无法操作这些稀疏矩阵。

定义

给定一个N×M的稀疏矩阵A,其第n行的行带宽定义为:

整个矩阵的带宽定义为:

例子

计算方法

稀疏矩阵的“注入元”是指执行算法是从初始的零值变为非零值的那些元素。为减少内存要求和算术操作的次数,我们经常通过交换某些行或某些列来尽量减少注入元。符号柯列斯基分解英语Symbolic Cholesky decomposition可以用来在做实际的柯列斯基分解之前计算最坏情况下注入元的数目。与此类似,可以用符号QR分解在做实际的QR分解之前计算最坏情况下注入元的数目。

消去树英语elimination tree法是一种用于高斯消元法LU分解中的系统处理如何减少注入元的方法。与此相关的一种称为嵌套解剖英语Nested dissection的方法,可以看成是它的一个特例。

延伸阅读


本页面最后更新于2021-08-19 06:57,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器