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

>>