基于CSR的不完全分解預條件技術

【摘 要】針對有限元方法產(chǎn)生的大型稀疏線性方程組，研究并實現(xiàn)了基于CSR存儲策略的不完全預條件技術。并分別對零填充和帶閥值的不完全分解進行了對比分析。結果表明：閥值的不完全分解預條件具有較好的迭代加速效果，但需根據(jù)實際情況調(diào)整預條件參數(shù)，以達到最佳加速效果。

【關鍵詞】大型稀疏線性方程組 預條件技術 不完全分解

在有限元數(shù)值模擬中，對所獲得的大型線性方程組的求解是難點之一。通?？煞譃閮深悾褐苯臃ê偷?。由于舍入誤差的影響，當矩陣規(guī)模較大時直接法往往求解失真甚至失敗。因此，通常采用迭代法進行求解。理論上，Gauss-Seidel迭代法、超松弛迭代法等基本迭代方法均可用于大型線性方程組的求解，但這些方法的收斂性較差，缺乏時效性。目前多采用基于預條件的Krylov子空間方法來加速收斂。本文針對有限元數(shù)值模擬中所獲得的大型稀疏線性方程組，采用CSR壓縮存儲策略存儲系數(shù)矩陣，并在此基礎上實現(xiàn)了不完全預條件算法。結合GMRES迭代方法，獲得了比較滿意的收斂效果。

一、不完全分解預條件矩陣的構造

迭代法的收斂速度取決于系數(shù)矩陣的條件數(shù)，即系數(shù)矩陣的范數(shù)與其逆的范數(shù)的乘積。對線性系統(tǒng)Ax=b預條件的基本思想是尋找一個預條件矩陣M≈A，通過將其作用于原系統(tǒng)以改善所獲得的新系統(tǒng)的條件數(shù)，從而加快迭代的收斂速度。預條件技術的關鍵是預條件矩陣M的構造。常見的預條件有分裂型預條件、截斷級數(shù)預條件、不完全分解預條件以及稀疏近似逆預條件等[1-2]。所謂不完全分解，就是將系數(shù)矩陣A分解成A=LU+R的形式，其中L為單位下三角矩陣，U為上三角矩陣，R為剩余矩陣，其構造方法以高斯消元法為基礎。由于在消元過程中經(jīng)常會產(chǎn)生元素填充（fill-in）而使矩陣L和U的稀疏性大大降低，故常采用某種舍棄策略來舍棄部分元素（除對角元外）以降低內(nèi)存需求。

（一）零填充不完全分解技術

最簡單的不完全分解技術是不做任何填充的不完全分解，即矩陣L和U完全保存系數(shù)矩陣A的稀疏模式，稱之為ILU（0）設系數(shù)矩陣，其對應的非零模式為，則零填充不完全分解可通過如下算法獲得。

（二）帶閥值的不完全分解技術

由于ILU（0）預條件技術舍棄了大量填充元，當系數(shù)矩陣嚴重病態(tài)時，采用ILU（0）預條件技術迭代速度依然比較慢甚至出現(xiàn)不收斂的情況（如圖2）。為了得到更好的不完全分解預條件子，必須允許有填充元。Y.saad（1994）首次提出了帶閥值的不完全LU分解技術[3]，其采用基于元素大小而不是元素位置的舍棄策略，稱之為ILUT（p，），其中參數(shù)p和用于控制不完全分解中非零元的個數(shù)。

二、實際算例

利用不完全預條件方法，結合GMRES迭代對電磁場有限元方法獲得的大型線性方程組進行求解。其中系數(shù)矩陣的階數(shù)為153872。其中，迭代終止條件設置為收斂精度達到1e-5或迭代300次。圖1顯示零填充不完全分解預處理的GMRES迭代基本不收斂，主要原因是由于舍棄了大量的填充元導致最終獲得的預條件矩陣與原系數(shù)矩陣相差較大，經(jīng)過預處理之后的新系統(tǒng)依然病態(tài)；有填充的不完全分解效果較好，在預定的迭代步數(shù)內(nèi)，收斂精度基本達到1e-5，而且可以看到，其收斂趨勢依然明顯，如果繼續(xù)迭代將可達到更高的收斂精度。

三、結論

（一）實際應用中，由于系數(shù)矩陣嚴重病態(tài)，零填充不完全分解預處理由于舍棄了大量填充元，預處理效果不明顯甚至不收斂。

（二）帶閥值的不完全預條件效果比較好，迭代收斂速度快。但需通過數(shù)值試驗以確定最佳參數(shù)。

參考文獻：

[1]周少博.大型線性方程組不完全分解預條件方法的研究[D]. 成都：電子科技大學，2008

[2]楊勇.大型線性方程組不完全分解預條件的研究[D]. 成都：電子科技大學，2013