稀疏矩陣

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

用陰影表示出一些常見的稀疏矩陣中非零元素素的分佈。

　　早在一個世紀以前，C.F.高斯、C.G.J.雅可比和其他一些人已經研究過利用矩陣稀疏性的一些辦法。20世紀50年代，在線性規劃和邊值問題的數值解中曾出現過一些處理稀疏問題的技術。D.M.楊和R.S.瓦爾加關於迭代法方面的研究也可看作處理高階稀疏問題的結果。但是，現代的稀疏矩陣技術主要是在60年代以後發展起來的，以60年代初期和中期W.F.廷尼和R.A.威洛比等人關於直接法的研究作為開端。稀疏矩陣的研究已經滲入到很多領域。例如，在結構分析、網絡理論、電力分配系統、化學工程、攝影測繪學以及管理科學等方面研究中，都出現瞭上千階直至幾十萬階的稀疏矩陣。

　　這裡考察從一個電信總局到其各支局間的通信問題。不妨假定有五個支局，依次編為1，2，3，4，5號，而總局編為6號，在平面上分別使用①，②，…，⑥這六個點表示（圖2

）。如果規定 i局和 j局之間有通信關系的話，在點 i和 j之間用一條線連結，對應於矩陣中 A _ij塊和 A _ji塊非零， i局本身內部也有通信關系，對應於矩陣 A _ii塊非零，那麼，這個問題所導出的矩陣是一個雙面鑲邊的塊對角矩陣

它是一個稀疏矩陣。

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

　　各種消元法方案中的關鍵問題都是方程式和未知數的排序問題。確切地說，就是在用某種直接法解稀疏線性方程組時，對方程式和未知數進行適當排序，使得在滿足一定的穩定性要求的前提下，解方程組所需的運算量和存貯量最少。一般說來，這等價於使新產生的非零元（“添補數”）最少。例如，對矩陣

作一步消元法，將 A變成

，

右下角子陣是滿的， A的零元所在位置上產生瞭許多非零元，破壞瞭稀疏性，這就要增加許多存貯量和運算量；如果將矩陣 A的第一行與最後一行，第一列與最後一列交換，這相當於重新排列方程式和未知數的次序，得矩陣

，

對Ã作消元法時，不會有新的非零元產生，存貯量和運算量大大減少。

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

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

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

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

中。

對於對稱帶型陣

可用變帶寬存貯法。它需要兩個數組：①存放剖面內的元素的一維數組 S[1：11]={ b ₁₁， b ₂₁， b ₂₂， b ₃₁，0， b ₃₃， b ₄₄， b ₅₃，0， b ₅₅， b ₆₆}；②對角元數組 D[1：6]={1，3，6，7，10，11}，在它的第 i個位置上存放對角元 b _ii在數組 S中的序號。這樣，矩陣的元素 b _ij可通過 D， i， j在 S中找到。對應關系為

並規定 D(0)=0。例如，由 D[3]=6， D[2]=3， D[3]-3+1> D[2]，可得 b ₃₁= S[4]。

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

可用行指針列標格式存貯，它需要三個數組：①根據按行向右的次序，存放矩陣非零元值的數組 V={ p ₁₁， p ₁₂， p ₁₄， p ₂₃， p ₃₁， p ₃₄， p ₄₁， p ₄₃， p ₄₄}；②存放 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中的位置。例如 p ₃₁，先由 R[3]=5， R[4]=7，確定第三行有兩個非零元 V[5]和 V[6]，再檢查 V[5]和 V[6]的列標，由 C[5]=1， C[6]=4，可推出 V[5]= p ₃₁。

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

　　對稀疏矩陣的共軛斜量法、隆措什法等迭代法研究的興趣日益濃厚，稀疏矩陣的研究也不再局限於稀疏線性方程組的解法問題，而是擴展為對所有高階稀疏問題的研究。

　　

參考書目

　梯華森著，朱季納譯：《稀疏矩陣》，科學出版社，北京，1981。(R.P.Tewarson，Sparse Matrices，AcademicPress，New York，1973.)