《matlab05-稀疏矩阵》由会员分享，可在线阅读，更多相关《matlab05-稀疏矩阵（31页珍藏版）》请在金锄头文库上搜索。
1、MATLAB 程式設計進階篇稀疏矩陣張智星 (Roger Jang)jangmirlab.orghttp:/mirlab.org/jang清大資工系 多媒體檢索實驗室MATLAB 程式設計進階篇：稀疏矩陣5-1稀疏矩陣的建立 n根據元素的值，MATLAB 的矩陣可分為兩種 :n完全矩陣（Full Matrix） n每一個元素都存成 double 的資料型態，佔用 8 個 Byte n一個 mn 的完全矩陣，所佔用的記憶體空間是 8mn 個 Byte n稀疏矩陣（Sparse Matrix） n大部分的元素都是 0 n只須儲存非零元素的位置及其元素值 n優點n節省記憶體儲存空間n節省某一些不必要
2、的運算 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-1(I)nsparse 指令可將一個完全矩陣轉換成稀疏矩陣n範例5-1：sparse01.m S = (1,1) 2 (3,2) 4 (2,4) 1 n可看出，S 是一個稀疏矩陣，MATLAB 只儲存其各個非零元素的位置（即其二維下標 (1,1)、(3,2)、(2,4)）和元素值（2、4、1） clear all; % 清除所有的變數A = 2 0 0 0; 0 0 0 1; 0 4 0 0; % 完全矩陣S = sparse(A) % 將完全矩陣 A 轉換成稀疏矩陣 SMATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-1(II)n
3、比較矩陣 A 和 S 所佔用的記憶體大小 : whos Name Size Bytes Class Attributes A 3x4 96 double S 3x4 88 double sparsen看出稀疏矩陣 S 佔用記憶體的位元組數目（88 Bytes）比 矩陣A（佔用 96 Bytes）還要小。MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-2(I)n使用 sparse 指令來直接產生稀疏矩陣 S = sparse(i, j, s, m, n);n i 是列索引 n j 是行索引 n s 是非零元素所形成的向量 n m 是 s 的列維度 n n 是 s 的行維度 n i、j、s 都
4、是長度相同的向量 n s(k) 的二維下標即是 i(k)及 j(k) MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-2(II) S = sparse(1 3 2, 1 2 4, 2 4 1, 3, 4) S = (1,1) 2 (3,2) 4 (2,4) 1n也可以在 sparse 指令加上第六種輸入變數，代表最多可以容納的非零元素個素，使得您可以後續再加入非零元素，而不必改變整個稀疏矩陣的結構 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-3(I)n指令 spdiags，可由對角線元素來建構一個稀疏矩陣 S = spdiags(D, p, m, n)nD 是每一個直行代表矩陣的對
5、角線向量 np 代表對角線的位置（0 代表主對角線，-1 代表向下位移一單位的次對角線，1 代表向上位移一單位的次對角線 )nm 代表矩陣的列維度nn 代表矩陣的行維度 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-3(II)n範例5-2：sparse02.m S = (1,1) 2 (2,1) 9 (2,2) 4 (3,2) 9 (1,3) 1 (3,3) 1 (4,3) 4 D = 3 2 9; 2 4 9; 1 1 4;d = 2 0 -1;S = spdiags(D, d, 4, 3)MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-3(III)n以完全矩陣來顯示，可得 : A
6、 = full(S) A = 2 0 1 9 4 0 0 9 1 0 0 4 n可看出矩陣 A 的三個非零對角線向量分別是 D 的三個行向量。（在D的第一個行向量中，只用到最後一個元素1。） 提示：D = 3 2 9 2 4 9 1 1 4d = 2 0 -1MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-4(I)n一般的 load 及 save 指令，也可以處理稀疏矩陣，並儲存於二進制的 MAT 檔案 nspconvert指令，可將一個 m3 的矩陣轉換成稀疏矩陣 n第一直行代表列索引 n第二直行代表行索引 n第三直行則是非零的元素值 n檔案 spmat.dat 的內容可顯示如下： ty
7、pe spmat.dat 1 1 2 3 2 4 2 4 1 8 3 5 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣範例-4(II)n建構此稀疏矩陣 n範例5-3：spconvert01.m S = (1,1) 2 (3,2) 4 (8,3) 5 (2,4) 1 load spmat.datS = spconvert(spmat)MATLAB 程式設計進階篇：稀疏矩陣5-2稀疏矩陣的儲存空間n一個只包含實數的稀疏矩陣，假設其維度為 mn，含有 nnz 個非零元素，MATLAB 動用了三個內部陣列來儲存此稀疏矩陣的相關資訊： n第一個陣列：以 double 方式儲存了所有的非零元素，其長度為
8、 nnz，使用的空間為大小 8*nnz 位元組（Bytes）。 n第二個陣列：以整數方式儲存了每個元素的列索引，其長度為 nnz，使用的空間大小為 4*nnz 位元組（Bytes）。n第三個陣列：以整數方式儲存了每個直行的起始指標，其長度為 n，使用空間大小為 4*n 位元組（Bytes）。n注意：上述儲存方式僅是用於MATLAB第六版！MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的儲存空間n整個稀疏矩陣佔用的空間大小為 8*nnz + 4*nnz + 4*n + 4 = 12*nnz + 4*n + 4，多出來的 4 個 bytes 是用來儲存其他經常性資訊 n範例5-4：memorySi
9、ze.m Name Size Bytes Class west0479 479x479 24564 double array (sparse) Grand total is 1887 elements using 24564 bytes clear allload west0479.matwhosMATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的儲存空間n驗證上述公式 12*(nnz(west0479) + 4*size(west0479,2) + 4 ans = 24564 nnnz(west0479) 可傳回稀疏矩陣 west0479 的非零元素個數，其他類似的指令還有 nonzeros（傳
10、回一個包含所有非零元素的行向量）及 nzmax（傳回最大的非零元素個數） MATLAB 程式設計進階篇：稀疏矩陣提示 n在一個稀疏矩陣中，將一個非零元素設定成零時，MATLAB 並不會自動釋放記憶體空間，換包話說，nnz 會隨著非零元素的減少而減少，但 nzmax 並不會隨著改變 n但是多加一個非零元素時，若 nnz 已大於 nzmax 時，nzmax 會隨之增大（即 MATLAB 會自動配置記憶體）以儲存新加的元素 MATLAB 程式設計進階篇：稀疏矩陣5-3稀疏矩陣的觀看與圖示 nspy 指令可用於觀看稀疏矩陣的非零元素分佈情況 n範例5-5：spy01.m load west0479.m
11、at % 載入二進位制檔案 west0479.matspy(west0479) % 觀看稀疏矩陣的非零元素分佈情況MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的觀看與圖示n矩陣 west0479 的維度是 479*479，但是只包含 1887 個非零元素，因此此矩陣的密度只有 1887/(479*479) = 0.0082 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的觀看與圖示n稀疏矩陣特別適用於表示一個無向圖（Undirected Graph）的鄰近矩陣（Adjacency Matrix），簡單地說，若某圖的第 i 和第 j 個節點有直線連接，則其相對應的鄰近矩陣在第 i 列、第 j
12、行的元素值為 1，其他元素值則為零 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的觀看與圖示n稀疏矩陣特別適用於表示一個無向圖（Undirected Graph）的鄰近矩陣（Adjacency Matrix）n若某圖的第 i 和第 j 個節點有直線連接，則其相對應的鄰近矩陣在第 i 列、第 j 行的元素值為 1，其他元素值則為零n為節省空間，僅用上三角或是下三角矩陣MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的觀看與圖示n對應的鄰近矩陣可表示成： A = spconvert(1 2 1; 2 3 1; 2 4 1; 3 4 1; 3 5 1; 5 6 1; 4 6 1); full(A)
13、ans = 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的觀看與圖示n假設這 6 個節點的座標如下： xy = 0 1; 1 2; 1 0; 2 0; 2 2; 3 1; % 每個列向量是一組座標n可用 gplot 指令來畫出上述的無向圖：n範例5-6：gplot01.m n 其中 -o 代表以實線（-）及圓圈（o）來作圖 A = spconvert(1 2 1; 2 3 1; 2 4 1; 3 2 1; 3 4 1; 3 5 1; 4 2 1; 4 3 1; 4 6 1;
14、 5 3 1; 5 6 1; 6 4 1; 6 5 1); xy = 0 1; 1 2; 1 0; 2 0; 2 2; 3 1; % 每一個列向量是一組 (x, y) 座標gplot(A, xy, -o) % 畫出無向圖（Undirected Graph） MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣無向圖MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣有趣的例子-1(I) nBucky 球，此圖包含了 60 個三度空間中的點，每一點和他的三個鄰近點都是等距離，可用 bucky 指令來產生這些點的鄰近矩陣，並用 gplot 來顯示圖形 n範例5-7：gplot02.m A, xy = buck
15、y; % A 為鄰近矩陣，xy 為座標 gplot(A, xy, -o); % 畫出無向圖（Undirected Graph）axis equal% 設定 x 軸和 y 軸的刻度一樣）MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣有趣的例子-1(II)MATLAB 程式設計進階篇：稀疏矩陣畫出抽象圖形(I) nTreeplot指令來畫出一棵電腦圖學中的樹 n範例5-8：treePlot01.m nodes = 0 1 2 2 4 4 4 1 8 8 10 10 11 11 11 11;treeplot(nodes);MATLAB 程式設計進階篇：稀疏矩陣畫出抽象圖形(II)n使用 nodes
16、向量來代表這一棵樹，其中 node(1)=0 則代表第一個節點是此樹的根節點（Root），而 node(i)=j 代表第 i 個節點的父親是第 j 個節點，例如 node(5)=4 代表第5個節點的父親是第 4 個節點，依此類推 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣有趣的例子-2n是由 NASA （美國太空總署）所主導的計畫，其中包含計算流過機翼的氣流所造成的作用力，由於必須進行偏微分方程的數值運算，所以必須對二維空間進行三角化切割，其鄰近矩陣即為一個稀疏矩陣，您可在 MATLAB 下執行 airfoil 指令即可產生相關圖形，相關說明則記載於 airfoil.m，可經由 type
17、airfoil.m 來檢視之。 MATLAB 程式設計進階篇：稀疏矩陣5-4稀疏矩陣的運算 nMATLAB 針對完全矩陣設計的運算與函式，也都適用於稀疏矩陣，而且輸出也是大部分以稀疏矩陣的方式來表示 n若計算過程包含稀疏及完全矩陣，則計算結果的表示方式就依情況而變，其規則可見 MATLAB 線上輔助說明 MATLAB 程式設計進階篇：稀疏矩陣稀疏矩陣的運算n稀疏矩陣的運算還包含下列幾種：n排列（Permutation）及重排（Reordering）n因子分解（Factorization）n線性聯立方程式的求解n固有值及奇異值的計算n這方面的運算，牽涉到很多數學理論，有興趣的讀者，可參考 MAT
18、LAB 的手冊，或在 MATLAB 指令視窗下輸入help sparfun以取得線上輔助說明 MATLAB 程式設計進階篇：稀疏矩陣5-5本章指令彙整指令功能B = sparse(A)將一個完全矩陣 A 轉換成稀疏矩陣 BB = sparse(i, j, s, m , n )直接產生一個稀疏矩陣 B，其中 ：i 是列索引j 是行索引s 是非零元素形成的向量m 是 B 的列維度n 是 B 的行維度i、j、s 都是長度相同的向量B = spdiags(D, p, m, n)由矩陣 D 的對角線元素來建構一個稀疏矩陣 B，其中：D 的每一個直行代表矩陣的對角線向量p 代表對角線的位置（0 代表主對角
19、線，-1 代表向下位移一單位的次對角線，1 代表向上位移一單位的次對角線，依此類推）m 與 n 則分別代表矩陣的列維度與行維度full(B)以完全矩陣來顯示矩陣 BMATLAB 程式設計進階篇：稀疏矩陣5-5本章指令彙整spconvert(C)將一個 m3 的矩陣 C，轉換成稀疏矩陣，其中：第一直行代表列索引第二直行代表行索引第三直行則是非零的元素值nnz(C) 傳回稀疏矩陣 C 的非零元素個數nonzeros(C)傳回稀疏矩陣 C 的所有非零元素形成的行向量nzmax(C)傳回稀疏矩陣 C 的目前可容納非零元素個數的最大值，當nnz nzmax 時，MATLAB 會動態調增配置記憶體給 nzmax，以儲存新增的非零元素 spy(C)觀看稀疏矩陣 C 的非零元素分佈情況gplot(A, xy, -o);畫出無向圖（Undirected Graph）treeplot(nodes)畫出樹狀圖
