[發明專利]基于逆的多波前塊ILU預處理方法

有效

• 申請號: 201410245950.0
• 申請日: 2014-06-05
• 公開（公告）號: CN104035915A
• 公開（公告）日: 2014-09-10
• 發明（設計）人: 王浩;徐立;李斌;李建清;楊中海
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 電子科技大學專利中心 51203
• 代理人: 張楊

技術領域

本發明屬于數值求解領域，具體涉及一種基于逆的多波前塊ILU預處理方法，用于求解在科學和工程計算問題中產生的大型稀疏線性方程組。?

背景技術

在許多科學和工程領域，如核物理、高維微分方程數值解、結構和非結構問題的有限元分析、計算流體力學、石油地震數據處理、電力系統的優化設計及數值天氣預報等，這些大型、超大型的科學與工程問題非常復雜。這時傳統的實驗方法、嘗試方法不僅代價巨大，而且需要花費大量的時間；由于很難給出這些問題中各種物理量間的函數關系，無法通過解析方法得到這些復雜問題的精確解。相對于解析方法，數值方法并不通過具體數學函數關系求解，而是通過分布在若干點上的一系列具體數值來近似表征問題的解。數值方法雖只是近似方法，但只要所取點數足夠多，也能以足夠的精度逼近解析解，更重要的是它能夠求解復雜的偏微分方程，因而能夠在滿足精度要求的情況下，解決解析方法不能解決的問題。特別是隨著計算機技術的發展，諸如有限差分法、有限積分法、有限元法和邊界元法等數值仿真方法被廣泛應用于科學和工程問題，并成為最常用和最有效的方法之一。數值仿真方法的求解往往歸結為大型稀疏線性方程組的求解，這也是此類方法中最消耗時間和內存的步驟。?

稀疏線性方程組的主要求解方法有直接法和迭代法兩種，其中直接法通過直接對方程組進行一系列的運算而獲得解；而迭代法通過逐次逼近來求解方程組，迭代直至達到預設精度為止。對于大型稀疏線性方程組，直接法存儲花銷和計算量巨大、計算成本高；而如果直接將迭代法用于求解，其收斂性和收斂速度得不到有效保證。因此，更為有效的方法是通過矩陣分裂預處理、不完全分解預處理以及稀疏近似逆預處理等方法首先對方程組進行預處理，再采用迭代法求解。其中，不完全分解預處理生成的矩陣由于能夠對系數矩陣做較好的近似，能夠大大的降低矩陣的條件數和迭代法的收斂步數、實現簡單有效、適用范圍廣等優點得到了廣泛應用。傳統的不完全分解預處理有用于對稱方程組的不完全cholesky分解預處理和用于非對稱方程組的不完全LU(ILU)分解預處理等。?

傳統的ILU分解預處理如ILUT分解(參見“Iterative?Methods?for?Sparse?Linear?Systems”，Society?for?Industrial?and?Applied?Mathematics，2003，Saad)在處理不到十萬階的小型稀疏線性方程組時具有很好的計算性能，而對于幾十萬甚至上百萬階的大型稀疏線性方程組，其計算性能并不讓人滿意。?

發明內容

本發明的目的是為了克服傳統ILU預處理求解大型稀疏線性方程組時效率低下的問題，提出了基于逆的多波前塊ILU預處理方法，利用該方法能夠以更小的內存代價更加精確、高效地求出大型稀疏線性方程組的解。?

為了實現上述目的，本發明的技術方案是：基于逆的多波前塊ILU預處理方法，包括以下步驟(除非特殊說明，本文中L和U分別表示下三角和上三角LU分解因子矩陣；P表示排序產生的排列矩陣)：?

步驟一：對原矩陣A執行重排序和符號分解，將矩陣重新組織成一系列的稠密矩陣，?

減少稀疏矩陣分解過程中產生的填入元數量，增加稠密操作。?

i).進行以減少填入元為目的的重排序；?

ii).執行符號分解，并建立消去樹；?

iii).根據消去樹后序遍歷順序進行重排序；?

iv).再次執行符號分解，建立消去樹；?

最后形成重排序后的矩陣(其中P₀是重排序得到的排列矩陣，T表示轉置)。?

步驟二：計算對角scaling矩陣D_r和D_c，得到矩陣增強數值穩定性。?

步驟三：將矩陣劃分為若干超節點，以便利用稠密矩陣操作提升計算性能。?

步驟四：將各超節點劃分為若干塊矩陣。?