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

有效

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

1.一種基于逆的多波前塊ILU預處理方法，包括：?

步驟一：對原矩陣A執行重排序和符號分解，將矩陣重新組織成一系列的稠密矩陣，減少稀疏矩陣分解過程中產生的填入元數量，增加稠密操作，最后形成重排序后的矩陣?其中P₀是重排序得到的排列矩陣，T表示轉置；?

步驟二：計算對角scaling矩陣D_r和D_c，得到矩陣

步驟三：將矩陣劃分為若干超節點，；?

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

步驟五：采用基于超塊-自適應塊不完全分解方法和基于逆拋棄策略的不需存儲更新陣的多波前法對各超節點進行塊ILU分解，將第i個超節點F_i表示為塊矩陣形式?獲得F_i的ILU分解所有超節點分解完畢后，獲得ILU分解其中是部分主元法產生的排列矩陣，是延遲主元產生的排列矩陣；?

步驟六：執行向前和向后回代，求解矩陣方程：

i).執行向前回代，解(P_rP_cD_rP₀)^-1Ly得

ii).執行向后回代，解Uz＝y得

iii).求出解向量

2.如權利要求1所述的一種基于逆的多波前塊ILU預處理方法，其特征在于所述步驟一包括：?

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

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

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

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

3.如權利要求1所述的一種基于逆的多波前塊ILU預處理方法，其特征在于所述步驟五中包括：?

i).集成完全相加部分的值信息；?

ii).集成完全相加部分來自子孫超節點的更新；?

iii).執行完全相加部分塊F₁₁的ILU分解

iv).按照新的主元順序調整已分解部分L₀,L₁,…L_i-1和U₀,U₁,…U_i-1，分別得到?和(其中下標0,1,…i-1表示第i個超節點之前的所?有已分解的超節點)；?

v).按照新的主元順序集成超節點的部分相加部分的值信息，得到調整主元順序后的部分相加部分和

vi).計算并集成部分相加部分來自子孫節點的更新；?

vii).分別求解部分相加部分矩陣方程。

4.如權利要求1或權利要求2所述的一種基于逆的多波前塊ILU預處理方法，其特征在于所述重排序采用基于多級嵌套剖分法和最小自由度排序技術的稀疏矩陣排序軟件包METIS對原稀疏矩陣A進行重排序。?

5.如權利要求1所述的一種基于逆的多波前塊ILU預處理方法，其特征在于步驟三中采用以下兩種松弛超節點技術：?

i).松弛超節點法：通過放松超節點非零結構“相同”的劃分條件，允許在非零結構有一定比例的不同，通過顯式添加零元獲得更大的超節點；?

ii).超節點融合技術：將較小的連續葉子節點合并為一個超節點，限制最小超節點的維數。?

6.如權利要求1所述的一種基于逆的多波前塊ILU預處理方法，其特征在于所述步驟五中采用不需存儲更新陣的多波前法，將當前波前陣對其對祖先節點的更新陣延遲到相應祖先節點波前陣分解時才計算并集成；波前陣被分為完全相加部分和部分相加部分，各部分分別求解，在分解時才集成相應的值信息。?

7.如權利要求1所述的一種基于逆的多波前塊ILU預處理方法，其特征在于步驟五中采用的不需存儲更新陣的多波前法采用了基于逆的拋棄策略，所述基于逆的拋棄策略的拋棄條件為：?

其中j＞k,m＞k，l_jk和u_km分別是分解因子L的第k列元素和U的第k行元素，單位向量e_k表示取矩陣第k行和第k列，τ為拋棄容限，T是矩陣轉置操作符，分別是逆分解因子的第k行范數和的第k列范數。?

8.如權利要求1所述的一種基于逆的多波前塊ILU預處理方法，其特征在于步驟五中采用的不需存儲更新陣的多波前法采用了超塊-自適應塊不完全分解方法，所述超塊-自適應塊不完全分解方法包括：?

i).在拋棄方式上，它的基本拋棄單元是塊，塊中滿足拋棄條件的元素都將被拋棄，當塊中所有元素均被拋棄，將整個塊拋棄；?

ii).在存儲策略上，采用基于內存池的自適應存儲策略，通過比較稀疏存儲方式和稠密存儲?方式所需代價，自動選擇存儲代價小的存儲方式；所有塊存儲空間和小片內存均采用內存池管理；?

iii).在計算架構上，采用超塊方法，將與同一塊或向量參與運算的多個連續存儲的塊拷貝到臨時存儲空間中形成一個超塊，再利用稠密矩陣運算實現；?

iv).所有塊的計算操作均采用BLAS3或LAPACK中的稠密矩陣運算實現。?