稀疏矩阵的存储结构有哪些

在矩阵领域中，存在一种比较特殊的矩阵，即稀疏矩阵。稀疏矩阵指的是除对角线外，其余非零元素很少的矩阵。由于其非常特殊的性质，所以在存储时需要采用特殊的存储结构，以节省存储空间、提高存储效率。本文将从多个角度分析稀疏矩阵的存储结构有哪些。

一、基本概念

在讨论稀疏矩阵的存储结构之前，需要先了解一些基本概念。设 $A$ 是一个 $m\times n$ 的矩阵，则 $A$ 的稀疏度 (Density) 定义为：

$$D = \frac{\text{矩阵 $A$ 中的非零元素个数}}{\text{矩阵 $A$ 中元素的总个数}}$$

稀疏矩阵的稀疏度一般小于0.1，也就是说大部分元素都是0。

二、存储结构

1.普通的存储方式：顺序存储方式。从行的角度来讲就是先存储第一行的数据，然后是第二行等，从列的角度来讲就是先存储第一列的数据，然后是第二列等。但是如果采用普通方式存储稀疏矩阵会造成存储浪费种种问题。

2.二元组结构存储：将稀疏矩阵转化为一个包含三个元素的元组集合(Triples,i,j,x)。其中 $(i,j)$ 是矩阵 $A$ 的一个非零元素的下标， $x$ 是矩阵 $A$ 中与之对应的非零元素值。这样的话，稀疏矩阵的空间消耗降为 $O(s)$ 。

需要注意的是，由于 $0$ 数量远多于非 $0$ 数量，因此采用二元组结构存储会大大节省空间。

3.坐标存储方式：和二元组结构存储一样也是用三个数组来表示矩阵，分别是 row（行表），column（列表） 和 value（非零元素）。其中 row 和 column 数组保存非零元素的下标，而 value 数组保存非零元素的值。

4.压缩存储方式：将矩阵转化为三小块，分别是 Dia, Up 和 Lw 块。其中 Dia 块保存了矩阵的对角线元素，而 Up 和 Lw 块分别保存了矩阵上三角和下三角的非零元素。

三、存储效率的分析

我们以一个 $5\times5$ 的稀疏矩阵：

$$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 7 & 0 & 1 \\ \end{pmatrix}$$

来比较不同存储方式的效率。具体见下表：

| 存储方式 | 存储大小 | 存储效率 |

| --- | --- | --- |

| 顺序存储 | 25 |100.0%|

| 二元组结构 | 3 | 12.0% |

| 坐标存储 | 9 | 36.0% |

| 压缩存储 | 7 | 28.0% |

从表中可以看出，不同存储方式的存储效率有着巨大的差异。其实这也是和矩阵的稀疏度有关系。

四、适用场合

在不同的场合下，比较适合使用的存储方式也是不相同的。

1.顺序存储方式：只适用于非常密集的矩阵。

2.二元组结构存储：适合针对比较分散的稀疏矩阵，不需要存储 0 的矩阵。

3.坐标存储方式：适合于大部分稀疏矩阵，存储数据规模比较小。由于只保存非零数的坐标，因此虽然相对于顺序存储而言存储占用要偏大一些，但空间利用率更高。

4.压缩存储方式：适合于大规模稀疏矩阵，收缩比二元组结构和坐标存储结构高，尤其是三角矩阵时，可充分利用矩阵加法和乘法的特殊性质来处理矩阵，减小计算量，加速运算速度。

综上所述，针对密集和稀疏矩阵的不同特点，应该选择适当的存储结构来存储稀疏矩阵，以更好地优化空间、提高存储效率等。