稀疏矩阵的类型？

在本文中，我们将详细了解稀疏矩阵及其类型。

稀疏矩阵的含义是什么？

在工程、科学、计算和经济等实际应用中，大量数值问题会使用巨大的矩阵。这些矩阵通常包含许多零元素，具有高比例零项的矩阵称为稀疏矩阵。

之所以称为稀疏，是因为非零元素的密度相对较低。如果我们将稀疏矩阵存储为二维数组，那么将花费大量空间来显式存储所有这些零。此外，在对稀疏矩阵（如加法、减法和乘法）进行操作时，如果将其存储为二维数组，许多操作都是在值为零的元素上进行的，这会导致时间和空间的浪费。因此，更好的策略是显式存储非零元素，这大大减少了所需的存储空间和执行各种操作所需的计算。

稀疏矩阵的类型

稀疏矩阵有不同的变体，这取决于矩阵稀疏的性质。基于这些特性，稀疏矩阵可以分为：

• 规则稀疏矩阵
• 不规则稀疏矩阵 / 非规则稀疏矩阵

规则稀疏矩阵

规则稀疏矩阵是具有明确定义的稀疏模式的方阵，即非零元素以明确定义的模式出现。各种类型的规则稀疏矩阵包括：

• 下三角规则稀疏矩阵
• 上三角规则稀疏矩阵
• 三对角线规则稀疏矩阵

下三角规则稀疏矩阵

下三角规则稀疏矩阵是指主对角线上方的所有元素都为零的矩阵。下面的矩阵是一个下三角规则稀疏矩阵。

存储下三角规则稀疏矩阵

在下三角规则稀疏矩阵中，非零元素按行存储在一维数组中。

例如：上图中所示的 5x5 下三角规则稀疏矩阵存储在一维数组 B 中：

B = { A₁₁, A₂₁, A₂₂, A₃₁, A₃₂, A₃₃, A₄₁, A₄₂, A₄₃, A₄₄, A₅₁, A₅₂, A₅₃, A₅₄, A₅₅}

此处 B [1] = A₁₁, B [2] = A₂₁, B [3] = A₂₂, ……………………………………… B [14] = A_54, B [15] = A₅₅

要计算非零元素的总数，我们需要知道每一行中非零元素的数量，然后将它们相加。由于第 i 行的非零元素数量为 i，因此 n 行的下三角规则稀疏矩阵中的非零元素总数为：

1 + 2 + ………………… + i + ………………….. + (n-1) + n = n (n+1)/2

上三角规则稀疏矩阵

上三角规则稀疏矩阵是指主对角线下方的所有元素都为零的矩阵。下面的矩阵是上三角规则稀疏矩阵。

存储上三角规则稀疏矩阵

在上三角规则稀疏矩阵中，非零元素按列存储在一维数组中。

例如，上图中所示的 5x5 下三角规则稀疏矩阵存储在一维数组 B 中：

B = { A₁₁, A₂₁, A₂₂, A₃₁, A₃₂, A₃₃, A₄₁, A₄₂, A₄₃, A₄₄, A₅₁, A₅₂, A₅₃, A₅₄, A₅₅}

此处 B [1] = A₁₁, B [2] = A₂₁, B [3] = A₂₂, B [4] = A_31,B [5] = A_{32 ,}B [6] = A_33, B [7] = A_{41 ,}B [8] = A_{42 ,}B [9] = A_{43 ,}B [10] = A_{44 ,}B [11] = A_{51 ,}B [12] = A_{52 ,}B [13] = A₅₃ , B [14] = A_54, B [15] = A₅₅

为了计算非零元素的总数，我们需要知道每一行中非零元素的数量，然后将它们相加。由于第 i 行的非零元素数量为 i，因此 n 行的下三角规则稀疏矩阵中的非零元素总数为：

1 + 2 + ………………… + i + ………………….. + (n-1) + n = n (n+1)/2

上三角规则稀疏矩阵

上三角规则稀疏矩阵是指主对角线下方的所有元素都为零的矩阵。下面的矩阵是上三角规则稀疏矩阵。

存储上三角规则稀疏矩阵

在上三角规则稀疏矩阵中，非零元素按列存储在一维数组中。

例如，上图中所示的 5x5 下三角规则稀疏矩阵存储在一维数组 B 中：

C = { A₁₁, A₁₂, A₂₂, A₁₃, A₂₃, A₃₃, A₁₄, A₂₄, A₃₄, A₄₄, A₁₅, A₂₅, A₃₅, A₄₅, A₅₅}

此处 C [1] = A₁₁, C [2] = A₁₂, C [3] = A₂₂, C [4] = A_13,C [5] = A_{23 ,}C [6] = A_33, C [7] = A_{14 ,}C [8] = A_{24 ,}C [9] = A₃₄, C [10] = A_{44 ,}C [11] = A_{15 ,}C [12] = A_{25 ,}C [13] = A₃₅ , C [14] = A_45, C [15] = A₅₅

为了计算非零元素的总数，我们需要知道每一列中非零元素的数量，然后将它们相加。由于第 i 列的非零元素数量为 i，因此 n 列的上三角规则稀疏矩阵中的非零元素总数为：

1 + 2 + ………………… + i + ………………….. + (n-1) + n = n (n+1)/2

三对角线规则稀疏矩阵

三对角线规则稀疏矩阵是指所有非零元素都位于主对角线、上面和下面的三条对角线上。

存储三对角线规则稀疏矩阵

在三对角线规则稀疏矩阵中，所有非零元素按行存储在一维数组中。

例如，上图中所示的 5x5 三对角线规则稀疏矩阵存储在一维数组 D 中：

D = { A₁₁, A₁₂, A₂₁, A₂₂, A₂₃, A₃₂, A₃₃, A₃₄, A₄₃, A₄₄, A₄₅, A₅₄, A₅₅}

此处 D [1] = A₁₁, D [2] = A₁₂, D [3] = A₂₁, D [4] = A_22, D [5] = A_23, D [6] = A_{32 ,}D [7] = A_33, D [8] = A_{34 ,}D [9] = A_{43 ,}D [10] = A_{44 ,}D [11] = A_{45 ,}D [12] = A_54, D [13] = A₅₅

为了计算非零元素的总数，我们需要知道对角线上、对角线上方和对角线下方非零元素的数量。方阵沿对角线的元素数量为 **'n'**，对角线上方的元素数量为 **(n-1)**。因此，n 行方阵中的非零元素总数为：

因此，n 行方阵的总元素数为 = 3n-2

在本例中，n = 5，所以总元素数为 = 3 * 5 - 2 = 13

不规则稀疏矩阵

不规则稀疏矩阵是指非零元素出现模式不规则或无结构的矩阵。下面的矩阵是一个不规则稀疏矩阵。

在上图中，有几种常见的存储稀疏矩阵的方案。其中大多数方案将矩阵的所有非零元素存储在一维数组中。

不规则稀疏矩阵的存储方案

在此方案中，我们将矩阵的所有非零元素存储在一维数组中，并使用几个辅助数组来指定稀疏矩阵中非零元素的位置。在用于存储不规则稀疏矩阵的几种可用存储方案中，最常见的存储方案是：

• 索引存储法
• 压缩行存储格式

使用索引存储法存储不规则稀疏矩阵

使用索引存储法，我们可以通过构造三个一维数组 AN、AI 和 AJ 来存储不规则稀疏矩阵 A，每个数组的元素数量等于非零元素的总数。

• 数组 AN 按行连续存储非零元素。
• AI 包含矩阵 A 中非零元素 A[I, J] 对应的行号。
• AJ 包含矩阵 A 中非零元素 A[I, J] 对应的列号。

让我们考虑一个如下所示的 4x6 稀疏矩阵 A：

在这个稀疏矩阵的 24 个元素中，只有 10 个元素是非零的。这些非零元素是：

图：三个一维数组 AI、AJ、AN 的表示

为了使用索引存储法来存储它。我们构造三个一维数组 AN、SI、AJ，每个数组包含 10 个元素（即非零元素的总数），如上图所示。

数组 AN 包含连续存储的 10 个非零元素。每个非零元素的相应行号和列号分别存储在数组 AI 和 AJ 中。

使用压缩行存储格式存储不规则稀疏矩阵

另一种节省空间且最广泛使用的表示不规则稀疏矩阵的方案是压缩行存储。在此方案中，我们使用三个一维数组 AN、AI 和 AJ。一维数组 AN 包含按行顺序从矩阵中提取的所有非零元素值。下一个一维数组 AJ 的长度等于 AN 的长度，它包含 AN 中相应元素在原始矩阵中的列位置。构造一个长度等于行数的ⱼ维数组 AI，该数组存储 AN 数组中非零元素第一个条目的位置。

例如

AI [2] = 4 表示第 2 行的第一个非零元素存储在 AN[4] 中，值为 2。

为了通过压缩行存储格式存储它，我们构造三个一维数组 AN、AI 和 AJ，如下图所示：

数组 AN 包含按行顺序连续存储的 10 个非零元素。相应的列号存储在一维数组 AJ 中。一维数组 AI 包含指向数组 AJ 和 AN 中每行的第一个非零元素的指针。