稀疏矩阵的存储及转置运算

希赛网 2024-02-04 09:35:01

稀疏矩阵是指大部分元素为0的矩阵，通常在计算机科学、金融、物理学等领域中被广泛应用。由于矩阵中存在大量的0元素，相对于稠密矩阵来说，存储和运算的效率都有很大的提升空间。本篇文章将从以下几个角度来阐述稀疏矩阵的存储及转置运算：什么是稀疏矩阵？为什么需要稀疏矩阵存储？稀疏矩阵的存储结构和算法，稀疏矩阵的转置运算及其算法。

什么是稀疏矩阵？

在数学中，稀疏矩阵是指大部分元素为0的矩阵。通常来说，稀疏矩阵的非零元素比例很小，一般小于5%。相对的，密集型矩阵就是那些在总元素数量中非零元素比例很高的矩阵。两者常用如下方式进行定义：如果一个 n x n 的矩阵中只有不超过 t 个元素非零，那么我们称它是一个 t-稀疏矩阵。矩阵中一个元素为 0 或者非 0，就成为这个矩阵的一个元素。

为什么需要稀疏矩阵存储？

稀疏矩阵可以节省存储空间。实际上，以一个n x n的矩阵为例，假设其中只有t个元素是非零的，那么可以考虑只对非零元素进行存储。如果用行索引、列索引和元素值来分别存储每个非零元素的信息，每个非零元素存储需要的空间实际上是元素值、行坐标、列坐标所需要的空间之和，一共是3个f加上机器相关的字节数。那么稀疏矩阵存储所需要的空间是t(3+f)。相比之下，对于一个密集矩阵，储存所有元素的成本是n x n x f。

存储结构和算法

面对稀疏矩阵，存储结构是特别的。实际上，有很多这样的结构例如三元组、行压缩、列压缩和块压缩等。这里仅介绍较为常用的结构之一:按行压缩存储法。具体地，行压缩法将每一行的非零元素存储到一个一维数组中，同时相应的列数也存储在另外一个一维数组中，并且保存一个指向每一行中第一个非零元素的指针。以此类推，以n行的矩阵为例，需要三个一维数组：element[ ]（由非零元素构成的数组），row[ ]（对应于每个非零元素所在的行数），和col_idx[ ]（元素在其所在行中的列数）。其中，最后一个指针用来指向下一行中的第一个非零元素，因为我们是沿着一行一行读取矩阵的。此外，压缩的前提是对于压缩的Dense Matrix，一般都满足类似物理上的矩形空间填充过程，即从上到下，从左到右填满整个矩形空间。

稀疏矩阵转置运算及其算法

矩阵转置是指将矩阵进行旋转操作，即行变列、列变行。对于稠密矩阵来说，这个过程非常显然而且方便，就是将行与列对调即可完成操作。可是对于稀疏矩阵，由于其数据存储结构的特点，通常情况下进行转置需要重新生成一个新的稀疏矩阵。稀疏矩阵转置的一种比较常见的算法是CRS（compressed row storage）格式转置算法。该算法非常简单，核心思想就是交换行与列，如下面的例子所示：

对于一个4 x 4的稀疏矩阵：

1 0 3 5

0 0 2 0

0 0 0 0

0 6 0 0

CRS压缩存储结构是这样的：

val [ ] = {1, 3, 5, 2, 6};

col_idx [ ] = {1, 3, 4, 3, 2};

row_ptr [ ] = {1, 4, 4, 4, 5};

如果要转置这个稀疏矩阵，我们可以得到它的CSC（compressed column storage）格式如下：

val_transpose [ ] = {1, 6, 3, 5, 2};

row_idx [ ] = {1, 4, 1, 2, 4};