MATLAB - 稀疏矩阵

矩阵是由数字、符号或变量按行和列排列成的二维数组。矩阵的维度表示为“m x n”，其中“m”表示行数，“n”表示列数。矩阵的各个元素通常由其行和列索引来表示，记为“aᵢⱼ”，其中“i”表示行号，“j”表示列号。

示例

这里 A 是一个 2x3 矩阵，即它有 2 行 3 列。

A =

   1     2     3
   4     5     6

这里 A₁₁ = 1，A₁₂ = 2，A₁₃ = 3。A₂₁ = 4，A₂₂ = 5 和 A₂₃ = 6。

什么是稀疏矩阵？

稀疏矩阵是一种矩阵，其中大多数元素为零。因此，与非零元素相比，您会在稀疏矩阵中看到很多零元素。

为什么我们需要稀疏矩阵？

以下是使用稀疏矩阵获得的好处：

稀疏矩阵的优点

• 高效的内存使用 - 稀疏矩阵在内存使用方面很有优势。由于大多数元素都是零，因此仅存储非零值可以节省大量内存，而存储密集矩阵（包括大量不必要的零值）则会占用更多内存。
• 计算效率 - 许多涉及稀疏矩阵的操作可以进行优化，以利用稀疏结构。与密集矩阵相比，这会导致更快的计算，因为在密集矩阵中，涉及大量零值的计算可能是浪费的。
• 降低复杂度 - 对稀疏矩阵进行操作的算法由于非零元素数量减少而往往表现出较低的复杂度。这可以导致更快的算法和更短的处理时间。
• 求解稀疏线性系统 - 稀疏矩阵经常出现在线性方程组中，并且像迭代求解器这样的专门技术比用于密集矩阵的直接方法更有效地求解稀疏线性系统。

稀疏矩阵的缺点

• 复杂的索引 - 涉及稀疏矩阵的操作通常需要更复杂的索引和数据结构来有效地导航和操作非零元素。这种复杂性可能使实现涉及稀疏矩阵的算法更具挑战性。
• 稀疏矩阵-向量乘法 - 虽然某些操作对稀疏矩阵非常有效，但与密集矩阵相比，矩阵-向量乘法效率可能较低，尤其是在稀疏模式不规则时。

稀疏矩阵的创建

在 MATLAB 中，您可以使用 sparse 函数创建稀疏矩阵。此函数允许您指定非零值及其对应的行和列索引。sparse 函数会自动将密集矩阵的非零元素转换为稀疏格式，同时省略零。

语法

S = sparse(A)

这里 A 是您要从中创建稀疏矩阵的密集矩阵。在密集矩阵中，大多数或所有元素都是非零的。

让我们从密集矩阵创建一个稀疏矩阵。

示例 1

A = [0, 0, 0, 0;0, 1, 0, 2; 0, 0, 3, 0;0, 4, 0, 5]
sparse_matrix = sparse(A)

在此示例中，A 是输入的密集矩阵，sparse_matrix 是使用 sparse 函数创建的生成的稀疏矩阵。该函数会自动从密集矩阵中提取非零值及其对应的行和列索引，以创建稀疏表示。

当您在 Matlab 中执行相同的操作时，输出如下：

>> A = [0, 0, 0, 0;0, 1, 0, 2; 0, 0, 3, 0;0, 4, 0, 5]
>> sparse_matrix = sparse(A)

A =

   0     0     0     0
   0     1     0     2
   0     0     3     0
   0     4     0     5

sparse_matrix =

Compressed Column Sparse (rows = 4, cols = 4, nnz = 5 [31%])

  (2, 2) -> 1
  (4, 2) -> 4
  (3, 3) -> 3
  (2, 4) -> 2
  (4, 4) -> 5
>>

具有指定大小的非零稀疏矩阵

创建具有指定大小的非零稀疏矩阵涉及提供矩阵的维度以及非零元素的位置和值。

示例

num_rows = 5;
num_cols = 5;
nonzero_rows = [1, 2, 3, 4]
nonzero_cols = [2, 4, 1, 3]
nonzero_vals = [10, 20, 30, 40]
sparse_matrix = sparse(nonzero_rows, nonzero_cols, nonzero_vals, num_rows, num_cols)

在上面的示例中，创建的稀疏矩阵将具有 5x5 的维度。它将在位置 (1,2)、(2,4)、(3,1) 和 (4,3) 处具有非零元素，相应的数值为 10、20、30 和 40。

当您在 matlab 命令窗口中执行上述示例时，输出为：

>> num_rows = 5;
num_cols = 5;
nonzero_rows = [1, 2, 3, 4]
nonzero_cols = [2, 4, 1, 3]
nonzero_vals = [10, 20, 30, 40]
sparse_matrix = sparse(nonzero_rows, nonzero_cols, nonzero_vals, num_rows, num_cols)

nonzero_rows =

   1   2   3   4

nonzero_cols =

   2   4   1   3

nonzero_vals =

   10   20   30   40

sparse_matrix =

Compressed Column Sparse (rows = 5, cols = 5, nnz = 4 [16%])

  (3, 1) -> 30
  (1, 2) -> 10
  (4, 3) -> 40
  (2, 4) -> 20

>>