手徵性合成

[拼音]：xishu juzhen

[英文]：sparse matrix

非零元素佔全部元素的百分比很小(例如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之間用一條線連結，對應於矩陣中Aij塊和Aji塊非零，i局本身內部也有通訊關係，對應於矩陣Aii塊非零，那麼，這個問題所匯出的矩陣是一個雙面鑲邊的塊對角矩陣

它是一個稀疏矩陣。

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

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

作一步消元法，將A變成

，

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

，

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

與常用的演算法相對應，排序問題可分為以下三類：

（1）預先把矩陣排列成帶型或變頻寬型，並使頻寬或剖面儘可能小；

（2）預先把矩陣排列成塊三角矩陣或其他特殊分塊矩陣；

（3）在稀疏消元法的消元過程中，根據產生添補數最少的原則來確定選主元的次序（這也是一種排序）。對一般矩陣，排序問題是一個非常困難的問題，因為對一個給定的矩陣來說，所有可能的次序總數是一個巨大的數字，可以給出的排序演算法只是按某一特殊準則來確定“最佳次序”的。討論中常用圖論作為工具。

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

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

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

中。

對於對稱帶型陣

可用變頻寬存貯法。它需要兩個陣列：

（1）存放剖面內的元素的一維陣列S[1:11]={b11，b21，b22，b31，0，b33，b44，b53，0，b55，b66}；

（2）對角元陣列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]-3+1>D[2]，可得b31=S[4]。

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

可用行指標列標格式存貯，它需要三個陣列：

（1）根據按行向右的次序，存放矩陣非零元值的陣列 V={p11，p12，p14，p23，p31，p34，p41，p43，p44}；

（2）存放V中每一元素在原矩陣中的列標的陣列C=｛1，2，4，3，1，4，1，3，4｝；

（3）陣列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。

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

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

參考書目

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