稀疏矩陣

在科學與工程領域中求解線性模型時經常出現大型的稀疏矩陣。在使用計算機存儲和操作稀疏矩陣時，經常需要修改標準演演算法以利用矩陣的稀疏結構。由於其自身的稀疏特性，通過壓縮可以大大節省稀疏矩陣的內存代價。更為重要的是，由於過大的尺寸，標準的演演算法經常無法操作這些稀疏矩陣。

非零元素佔全部元素的百分比很小(例如5%以下)的矩陣。有的矩陣非零元素佔全部元素的百分比較大（例如近50％），但它們的分佈很有規律，利用這一特點可以避免存放零元素或避免對這些零元素進行運算，這種矩陣仍可稱為稀疏矩陣。

給定一個N×M的稀疏矩陣A，其第n行的行帶寬定義為：

整個矩陣的帶寬定義為：

早在20世紀，C.F.高斯、C.G.J.雅可比和其他一些人已經研究過利用矩陣稀疏性的一些辦法。20世紀50年代，在線性規劃和邊值問題的數值解中曾出現過一些處理稀疏問題的技術。D.M.楊和R.S.瓦爾加關於迭代法方面的研究也可看作處理高階稀疏問題的結果。但是，現代的稀疏矩陣技術主要是在60年代以後發展起來的，以60年代初期和中期W.F.廷尼和R.A.威洛比等人關於直接法的研究作為開端。

稀徠疏矩陣的計算速度更快，因為MATLAB只對非零元素進行操作，這是稀疏矩陣的一個突出的優點。假設矩陣A,B中的矩陣一樣。計算2*A需要一百萬次的浮點運算,而計算2*B只需要2000次浮點運算。因為MATLAB不能自動創建稀疏矩陣，所以要用特殊的命令來得到稀疏矩陣.

對於一個用二維數組存儲的稀疏矩陣Amn,如果假設存儲每個數組元素需要L個位元組,那麼存儲整個矩陣需要m*n*L個位元組。但是，這些存儲空間的大部分存放的是0元素，從而造成大量的空間浪費。為了節省存儲空間，可以只存儲其中的非0元素.

對於矩陣Amn的每個元素aij,知道其行號i和列號j就可以確定其位置。因此對於稀疏矩陣可以用一個結點來存儲一個非0元素。該結點可以定義如下:[i,j,aij] 該結點由3個域組成,i:行號,j:列號;aij元素值。這樣的結點被稱為三元組結點。矩陣的每一個元素Qij,由一個三元組結點(i,j,aij)唯一確定.

例如稀疏矩陣A:

50000

100200

0000

-300-605

其對應的三元組表為：

0050

1010

1220

30-30

32-60

335

解線性方程組的直接法的稀疏矩陣技術，根據不同領域中不同問題的特點，有各種不同稀疏解法。最常用的方法有稀疏去零消元法、等帶或變帶寬消元法、波陣法、子結構法、撕裂和修改技術等，它們都只不過是消元法或三角分解法在各種具體場合下的運用。

各種消元法方案中的關鍵問題都是方程式和未知數的排序問題。確切地說，就是在用某種直接法解稀疏線性方程組時，對方程式和未知數進行適當排序，使得在滿足一定的穩定性要求的前提下，解方程組所需的運算量和存貯量最少。一般說來，這等價於使新產生的非零元（“添補數”）最少。例如，對矩陣作一步消元法，將A變成，右下角矩陣是滿的,A的零元所在位置上產生了許多非零元，破壞了稀疏性，這就要增加許多存貯量和運算量；如果將矩陣A的第一行與最後一行，第一列與最後一列交換，這相當於重新排列方程式和未知數的次序，得矩陣，對Ã作消元法時，不會有新的非零元產生，存貯量和運算量大大減少。

與常用的演演算法相對應，排序問題可分為以下三類:①預先把矩陣排列成帶型或變帶寬型，並使帶寬或剖面儘可能小；②預先把矩陣排列成塊三角矩陣或其他特殊分塊矩陣；③在稀疏消元法的消元過程中，根據產生添補數最少的原則來確定選主元的次序（這也是一種排序）。對一般矩陣，排序問題是一個非常困難的問題，因為對一個給定的矩陣來說，所有可能的次序總數是一個巨大的數字，可以給出的排序演演算法只是按某一特殊準則來確定“最佳次序”的。討論中常用圖論作為工具。

稀疏矩陣的存貯並沒有一種最好的方式，在各種具體情況下，最好的方式與要存貯矩陣的結構及用途有關一種好的標準是矩陣的元素容易查找而且存貯量少。存貯方式基本上採用壓縮形式，使矩陣中大量的零元素不參加運算，以減少機器的運行時間，並可提高機器處理高階矩陣問題的能力。

對於帶型矩陣，只存貯帶內或剖面內的元素。如對矩陣

可用等帶寬存貯法，在帶的左上角和右下角增添若干個任意元素x，把帶內的元素存放在矩形數組

中。

對於對稱帶型陣

稀疏矩陣

可用變帶寬存貯法。它需要兩個數組：①存放剖面內的元素的一維數組S【1:11】={b11,b21，b22，b31，0，b33,b44，b53,0,b55,b66}；②對角元數組D【1:6】={1,3,6,7,10,11}，在它的第i個位置上存放對角元bii在數組S中的序號。這樣，矩陣的元素bij可通過D，i，j在S中找到。對應關係為

並規定D(0)=0。例如，由D【3】=6,D【2】=3,D【3】-31>D【2】，可得b31=S【4】。

對於元素隨機分佈的稀疏矩陣，只存貯矩陣的非零元素和必要的檢索信息。如對

可用行指針列標格式存貯，它需要三個數組：①根據按行向右的次序，存放矩陣非零元值的數組V={p11，p12，p14，p23，p31，p34，p41，p43,p44};②存放V中每一元素在原矩陣中的列標的數組C=｛1,2,4,3,1,4,1,3,4｝;③數組R=｛1,4,5,7,10｝，在它的第i個位置上存放矩陣第i行的第一個非零元在數組V中的序號，最後一個位置上的數等於矩陣非零元素個數加1。矩陣p的任意非零元素可根據R和C的值定出它在V中的位置。例如p31,先由R【3】=5，R【4】=7，確定第三行有兩個非零元V【5】和V【6】，再檢查V【5】和V【6】的列標，由C【5】=1,C【6】=4，可推出V【5】=p31。

此外，還有連接表存貯法和超矩陣存貯法等。

稀疏矩陣的研究已經深入到很多領域。例如，在結構分析、網路理論、電力分配系統、化學工程、攝影測繪學以及管理科學等方面研究中，都出現了上千階直至幾百萬階的稀疏矩陣。這裡考察從一個電信總局到其各支局間的通信問題。不妨假定有五個支局，依次編為1，2，3，4，5號，而總局編為6號，在平面上分別使用①，②，…,⑥這六個點表示（圖2）。如果規定i局和j局之間有通信關係的話，在點i和j之間用一條線連結，對應於矩陣中Aij塊和Aji塊非零,i局本身內部也有通信關係，對應於矩陣Aii塊非零，那麼，這個問題所導出的矩陣是一個雙面鑲邊的塊對角矩陣它是一個稀疏矩陣。

矩陣微積分迭代存貯