程式設(shè)計進階篇稀疏矩陣

MATLAB程式設(shè)計進階篇

稀疏矩陣張智星jang@.tw.tw/~jang清大資工系多媒體檢索實驗室5-1 稀疏矩陣的建立MATLAB的矩陣可分為兩種:完全矩陣（FullMatrix）

每一個元素都存成double的資料型態(tài)，佔用8個Byte一個m×n的完全矩陣，所佔用的記憶體空間是8×m×n個Byte稀疏矩陣（SparseMatrix）大部分的元素都是0只須儲存「非零元素的位置」及其「元素值」兩大優(yōu)點:

1.節(jié)省記憶體儲存空間

2.節(jié)省許多不必要的運算稀疏矩陣範(fàn)例-1(I)sparse指令可將一個完全矩陣轉(zhuǎn)換成稀疏矩陣範(fàn)例5-1：sparse01.m

S=(1,1)2(3,2)4(2,4)1可看出，S是一個稀疏矩陣，MATLAB只儲存其各個非零元素的位置（即其二維下標(biāo)(1,1)、(3,2)、(2,4)）和元素值（2、4、1）

clearall; %清除所有的變數(shù)A=[2000;0001;0400];%完全矩陣S=sparse(A)%將完全矩陣A轉(zhuǎn)換成稀疏矩陣S稀疏矩陣範(fàn)例-1(II)比較矩陣A和S所佔用的記憶體大小:>>whos

NameSizeBytesClassA3x496doublearrayS3x456sparsearray

Grandtotalis15elementsusing152bytes看出稀疏矩陣S佔用記憶體的位元組數(shù)目（56Bytes）比矩陣A（佔用96Bytes）小很多稀疏矩陣範(fàn)例-2(I)使用sparse指令來直接產(chǎn)生稀疏矩陣

S=sparse(i,j,s,m,n);

i是列索引j是行索引s是非零元素所形成的向量m是s的列維度n是s的行維度i、j、s都是長度相同的向量s(k)的二維下標(biāo)即是i(k)及j(k)稀疏矩陣範(fàn)例-2(II)>>S=sparse([132],[124],[241],3,4)

S=(1,1)2(3,2)4(2,4)1也可以在sparse指令加上第六種輸入變數(shù)，代表最多可以容納的非零元素個素，使得您可以後續(xù)再加入非零元素，而不必改變整個稀疏矩陣的結(jié)構(gòu)稀疏矩陣範(fàn)例-3(I)指令spdiags，可由對角線元素來建構(gòu)一個稀疏矩陣

S=spdiags(D,p,m,n)D是每一個直行代表矩陣的對角線向量p代表對角線的位置（0代表主對角線，-1代表向下位移一單位的次對角線，1代表向上位移一單位的次對角線)m代表矩陣的列維度n代表矩陣的行維度

稀疏矩陣範(fàn)例-3(II)範(fà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)4D=[329;249;114];d=[20-1];S=spdiags(D,d,4,3)稀疏矩陣範(fàn)例-3(III)以完全矩陣來顯示，可得:

>>A=full(S)

A=201940091004可看出矩陣A的三個非零對角線向量分別是D的三個行向量稀疏矩陣範(fàn)例-4(I)一般的load及save指令，也可以處理稀疏矩陣，並儲存於二進制的MAT檔案Spconvert指令，可將一個m×3的矩陣轉(zhuǎn)換成稀疏矩陣第一直行代表列索引第二直行代表行索引第三直行則是非零的元素值檔案spmat.dat的內(nèi)容可顯示如下：

>>typespmat.dat

112324241835稀疏矩陣範(fàn)例-4(II)建構(gòu)此稀疏矩陣範(fàn)例5-3：spconvert01.m

S=(1,1)2(3,2)4(8,3)5(2,4)1loadspmat.datS=spconvert(spmat)5-2 稀疏矩陣的儲存空間一個只包含實數(shù)的稀疏矩陣，假設(shè)其維度為m×n，含有nnz個非零元素，MATLAB動用了三個內(nèi)部陣列來儲存此稀疏矩陣的相關(guān)資訊：第一個陣列：以double方式儲存了所有的非零元素，其長度為nnz，使用的空間為大小8*nnz位元組（Bytes）。第二個陣列：以整數(shù)方式儲存了每個元素的列索引，其長度為nnz，使用的空間大小為4*nnz位元組（Bytes）。第三個陣列：以整數(shù)方式儲存了每個直行的起始指標(biāo)，其長度為n，使用空間大小為4*n位元組（Bytes）。稀疏矩陣的儲存空間整個稀疏矩陣佔用的空間大小為8*nnz+4*nnz+4*n+4=12*nnz+4*n+4，多出來的4個bytes是用來儲存其他經(jīng)常性資訊範(fàn)例5-4：memorySize.m

NameSizeBytesClasswest0479479x47924564doublearray(sparse)Grandtotalis1887elementsusing24564bytesclearallloadwest0479.matwhos稀疏矩陣的儲存空間驗證上述公式

>>12*(nnz(west0479))+4*size(west0479,2)+4ans=24564nnz(west0479)可傳回稀疏矩陣west0479的非零元素個數(shù)，其他類似的指令還有nonzeros（傳回一個包含所有非零元素的行向量）及nzmax（傳回最大的非零元素個數(shù)）提示在一個稀疏矩陣中，將一個非零元素設(shè)定成零時，MATLAB並不會自動釋放記憶體空間，換包話說，nnz會隨著非零元素的減少而減少，但nzmax並不會隨著改變但是多加一個非零元素時，若nnz已大於nzmax時，nzmax會隨之增大（即MATLAB會自動配置記憶體）以儲存新加的元素

5-3 稀疏矩陣的觀看與圖示spy指令可用於觀看稀疏矩陣的非零元素分佈情況範(fàn)例5-5：spy01.m

loadwest0479.mat%載入二進位制檔案west0479.matspy(west0479)%觀看稀疏矩陣的非零元素分佈情況稀疏矩陣的觀看與圖示矩陣west0479的維度是479*479，但是只包含1887個非零元素，因此此矩陣的密度只有1887/(479*479)=0.0082稀疏矩陣的觀看與圖示稀疏矩陣特別適用於表示一個「無向圖」（UndirectedGraph）的「鄰近矩陣」（AdjacencyMatrix），簡單地說，若某圖的第i和第j個節(jié)點有直線連接，則其相對應(yīng)的鄰近矩陣在第i列、第j行的元素值為1，其他元素值則為零稀疏矩陣的觀看與圖示對應(yīng)的鄰近矩陣可表示成：

>>A=spconvert([121;231;241;321;341;351;421;431;461;531;561;641;651])

A=(1,2)1(3,2)1(4,2)1(2,3)1(4,3)1(5,3)1(2,4)1(3,4)1(6,4)1(3,5)1(6,5)1(4,6)1(5,6)1稀疏矩陣的觀看與圖示假設(shè)這6個節(jié)點的座標(biāo)如下：>>xy=[01;12;10;20;22;31];%每個列向量是一組座標(biāo)可用gplot指令來畫出上述的無向圖：範(fàn)例5-6：gplot01.m

其中'-o'代表以實線（'-'）及圓圈（'o'）來作圖

A=spconvert([121;231;241;321;341;351;421;431;461;531;561;641;651]);xy=[01;12;10;20;22;31];%每一個列向量是一組(x,y)座標(biāo)gplot(A,xy,'-o') %畫出無向圖（UndirectedGraph）稀疏矩陣無向圖稀疏矩陣有趣的例子-1(I)Bucky球，此圖包含了60個三度空間中的點，每一點和他的三個鄰近點都是等距離，可用bucky指令來產(chǎn)生這些點的鄰近矩陣，並用gplot來顯示圖形

範(fàn)例5-7：gplot02.m

[A,xy]=bucky; %A為鄰近矩陣，xy為座標(biāo)gplot(A,xy,'-o'); %畫出無向圖（UndirectedGraph）axisequal %設(shè)定x軸和y軸的刻度一樣）稀疏矩陣有趣的例子-1(II)畫出抽象圖形(I)Treeplot指令來畫出一棵電腦圖學(xué)中的樹

範(fàn)例5-8：treePlot01.m

nodes=[0122444188101011111111];treeplot(nodes);畫出抽象圖形(II)使用nodes向量來代表這一棵樹，其中node(1)=0則代表第一個節(jié)點是此樹的根節(jié)點（Root），而node(i)=j代表第i個節(jié)點的父親是第j個節(jié)點，例如node(5)=4代表第5個節(jié)點的父親是第4個節(jié)點，依此類推稀疏矩陣有趣的例子-2是由NASA（美國太空總署）所主導(dǎo)的計畫，其中包含計算流過機翼的氣流所造成的作用力，由於必須進行偏微分方程的數(shù)值運算，所以必須對二維空間進行三角化切割，其鄰近矩陣即為一個稀疏矩陣，您可在MATLAB下執(zhí)行airfoil指令即可產(chǎn)生相關(guān)圖形，相關(guān)說明則記載於airfoil.m，可經(jīng)由typeairfoil.m來檢視之。5-4 稀疏矩陣的運算MATLAB針對完全矩陣設(shè)計的運算與函式，也都適用於稀疏矩陣，而且輸出也是大部分以稀疏矩陣的方式來表示若計算過程包含稀疏及完全矩陣，則計算結(jié)果的表示方式就依情況而變，其規(guī)則可見MATLAB線上輔助說明稀疏矩陣的運算稀疏矩陣的運算還包含下列幾種：排列（Permutation）及重排（Reordering）因子分解（Factorization）線性聯(lián)立方程式的求解固有值及奇異值的計算這方面的運算，牽涉到很多數(shù)學(xué)理論，有興趣的讀者，可參考MATLAB的手冊，或在MATLAB指令視窗下輸入「helpsparfun」以取得線上輔助說明5-5 本章指令彙整指令功能B=spars