【正文】 部子矩陣中對(duì)應(yīng)的元素坐標(biāo) (loc_i, loc_j) (4) mat _ div： 三對(duì)角矩陣秩 2劃分。 (6) pdist_A: 將矩陣按 2D塊方式分布到二維處理器網(wǎng)格中 ? 其它子程序 (1) p*gnrm: 廣義特征問(wèn)題特征向量余范數(shù)求解 (2) p*nrm: 標(biāo)準(zhǔn)特征問(wèn)題特征向量余范數(shù)求解 (3) *lag_app_eigen： Laguerre迭代求解函數(shù)近似值 (4) *sort： 數(shù)據(jù)排序子程序 (5) Mem_free： 釋放內(nèi)存空間 (6) Comm_free： 釋放通信器 12 稀疏對(duì)稱(chēng)特征問(wèn)題 ? 在 HPSEPS中，提供了基于顯式重啟 再正交和deflate技術(shù)的 Lanczos算法的稀疏對(duì)稱(chēng)矩陣特征問(wèn)題并行求解模塊。輸入向量的第 j個(gè)元素在處理器 P上，輸出向量的第 j個(gè)元素也必須在處理器 P上 14 ? 主要模塊和接口： (1) p*lancs： Lanczos框架接口。 (2) p*getv：產(chǎn)生分布在不同處理器上的初始向量。 (4) p*orth：向量并行正交化過(guò)程 (5) p*norm2：并行計(jì)算向量的 2范數(shù)。 15 使用 HPSEPS編程的方法 HPSEPS為求解不同模式的矩陣特征問(wèn)題提供了相應(yīng)的模板。下面是使用 HPSEPS軟件包應(yīng)遵循的一些步驟： – 選擇一個(gè)合適的驅(qū)動(dòng)程序。 – 修改問(wèn)題依賴(lài)的變量。 16 ? 稠密特征問(wèn)題： 在深騰 7000超級(jí)計(jì)算機(jī)，使用 128， 256，512， 1024核并行求解 30000 30000和 60000 60000 規(guī)模問(wèn)題的全部本征對(duì)。 2048個(gè)核上性能達(dá)到了較高的可擴(kuò)展性能 N u m o f C o r e s 5 1 2 1 0 2 4 2 0 4 8T i m e ( s e c ) 2 2 2 0 . 6 1 3 5 0 . 4 9 1 2 . 5T F L O P S 4 . 5 T 8 . 2 T 1 4 . 5 TRun n i n g tim e (s) Num of C or e s 3 0000* 3 0000 6 0000* 6 0000 128 8 5 6 5 9 8 5 256 6 7 8 3 8 3 2 .78 512 4 6 5 2 7 5 8 .77 1024 4 0 3 2 2 3 0 .48 17 Hypre軟件包 美國(guó)加州大學(xué)（ UC） 勞倫斯 利弗莫爾國(guó)家實(shí)驗(yàn)室（ LLNL） / 應(yīng)用科學(xué)計(jì)算中心（ CASC） 18 軟件包概述 Hypre （ High Performance Preconditioners, 高性能預(yù)條件子） 源于美國(guó)能源部和 LLNL等在研究國(guó)防、環(huán)境、 能 源和生物科學(xué)中的物理現(xiàn)象時(shí)，開(kāi)發(fā)的一些模擬代碼 。 ? 常用的迭代法實(shí)現(xiàn)： Hypre提供一些最常用的基于 Krylov子空間迭代法。 ? 直觀的以網(wǎng)格為中心的界面： Hypre通過(guò)各種網(wǎng)格界面表示和處理稀疏矩陣，每個(gè)界面提供對(duì)一些求解器的訪問(wèn)，因此不需要用戶去學(xué)習(xí)和創(chuàng)建復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 19 Hypre：數(shù)據(jù)結(jié)構(gòu)、求解器和網(wǎng)格接口關(guān)系 第一層表示各種線性系統(tǒng)的網(wǎng)格界面， 第二層表示各種線性求解器（迭代法和預(yù)條件子） 第三層表示各種數(shù)據(jù)劃分和矩陣向量存儲(chǔ)策略。 ? 結(jié)構(gòu)化 （ Struct） 接口 ： 面向結(jié)構(gòu)網(wǎng)格離散的應(yīng)用 .每個(gè)網(wǎng)格點(diǎn)的離散格式具有相同的模式。應(yīng)用于稀疏線性方程組 , 為網(wǎng)格界面的補(bǔ)充 21 迭代法與預(yù)條件子 ? 迭代方法 Krylov解法器（ CG， GMRES(缺省情形 )， TFQMR， BiCGSTAB）； BoomerAMG（一個(gè)并行代數(shù)多重網(wǎng)格解法器）； 具有迭代加細(xì) (refinement)的 SuperLU直接解法器（串行）。 如果 A對(duì)稱(chēng) , 且有 Cholesky分解 ： A=LLT, 求解 得到三角近似逆 G, ； – PILUT并行求解 A的一個(gè)近似分解。由于 M是非對(duì)稱(chēng)的（即使 A 是對(duì)稱(chēng)的），因此不適合作為對(duì)稱(chēng)矩陣的迭代法（如CG）的預(yù)條件子； – Euclid是一種擴(kuò)展性能較好的并行不完全 LU分解（ ILU）預(yù)條件子，它支持各種 ILU（ k）和 ILUT, 包括塊 Jacobi ILU（ k），并行 ILU（ k），它比塊 Jacobi預(yù)條件子更有效 min || ||FI MA?min || ||FI MA?23 網(wǎng)格接口與求解器的關(guān)系 Hypre的網(wǎng)格界面與求解器的關(guān)系 X表示支持 HYPRE為不同的接口定義了不同的數(shù)據(jù)結(jié)構(gòu) ,并配以適合該接口的解法器 24 多重網(wǎng)格 MG ? 多重網(wǎng)格解法器是 HYPRE的重要特色 . ? 多重網(wǎng)格方法包含三個(gè)要素 ：光滑算子、限制算子和延拓算子 – 分片線性插值作為延拓 – 相鄰點(diǎn)的加權(quán)平均作為限制 – 松弛迭代 (如 GaussSeidel、 SSOR)等簡(jiǎn)單迭代作為光滑 ? HYPRE提供多個(gè)多重網(wǎng)格解法器 如 AMS,SMG,PFMG,MLI, BoomerAMG. 這些可滿足各種應(yīng)用的需求。二維時(shí) SMG只在 x方向半粗化 , 在 y方向用的是線光滑 , 三維時(shí)則采用面光滑。 用戶可以根據(jù)情況選擇不同的并行粗化技巧 （比 如 CLJP粗化 、 經(jīng)典 RS粗化 ） 和松弛策略 （比如 GaussSeidel松弛 、 Jacobi或加權(quán) Jacobi松弛 ） . 26 Hypre 使用方法 下面的例子是采用 并行半粗化 多 重網(wǎng)格迭代法求解結(jié)構(gòu)網(wǎng)格界面下的線性系統(tǒng) /* Set up the grid and stencil */ HYPRE_StructGridCreate(MPI_COMM_WORLD, dim, amp。 HYPRE_StructGridSetExtents(grid, ilower, iupper)。 % 構(gòu)造結(jié)構(gòu)網(wǎng)格和模板 HYPRE_StructStencilCreate(dim, stencil_size, amp。 HYPRE_StructStencilSetElement(stencil, 0, offset0)。A)。 % 構(gòu)造結(jié)構(gòu)化矩陣 HYPRE_StructMatrixSetBoxValues(A, ilower, iupper, nelts, elts, Avalues)。 HYPRE_StructVectorCreate(MPI_COMM_WORLD, grid, amp。 HYPRE_StructVectorInitialize(b)。 ... HYPRE_StructVectorAssemble(b)。x)。 % 解向量的初始化 27 HYPRE_StructVectorSetBoxValues(x, ilower, iupper, xvalues)。 /* Set up the solver */ HYPRE_StructPFMGCreate(MPI_COMM_WORLD, amp。 HYPRE_StructPFMGSetMaxIter(solver, 50)。 /* optional */ HYPRE_StructPFMGSetup(solver, A, b, x)。 %求解線性方程組 /* Get solution info and free up memory */ %返回結(jié)果并釋放內(nèi)存 HYPRE_StructVectorGetBoxValues(x, ilower, iupper, xvalues)。 HYPRE_StructGridDestroy(grid)。 HYPRE_StructMatrixDestroy(A)。 HYPRE_StructVectorDestroy(x)。 Abi Abb], u = [ui 。 u0]。 0 I] [ui 。 u0] 。 相關(guān)系數(shù) : 擴(kuò)散系數(shù) K=x2+exp(y)。 反應(yīng)系數(shù) C=。 右端項(xiàng) : F= 2π2 sin(πx)sin(πy) 。 29 Struct和 IJ兩種界面下 , 各求解器的迭代次數(shù)和運(yùn)行時(shí)間 (256 256,Np=4 ) 界面 結(jié)構(gòu)化網(wǎng)格界面 矩陣界面 求解器 SMG PCG + SMG AMG PCG + AMG PCG + Parasails CG 迭代次數(shù) 9 6 9 7 209 437 計(jì)算時(shí)間 (s) 注 : T(SMG) = T(SMG_setup) + T(SMG_solve), (cpu clock time), Np=4, tol= AMG的并行效率 (網(wǎng)格規(guī)模為 1024 1024) 30 MUMPS 由 CEC ESPRIT IV長(zhǎng)期研究計(jì)劃項(xiàng)目資助 31 MUMPS概述 MUMPS：多波前大規(guī)模并行稀疏直接解法器（ A MUltifrontal Massively Parallel sparse direct Solver） ? MUMPS是一個(gè)通過(guò)直接方法求解線性方程組 : Ax=b 的并行軟件包，其中 A是一個(gè)對(duì)稱(chēng)或非對(duì)稱(chēng)的稀疏方陣。通過(guò)將矩陣 A直接分解為 A=LU或 A=LDLT（對(duì)稱(chēng)矩陣）形式完成大規(guī)模線性方程的求解。 ? 部分分解和 Schur補(bǔ)矩陣 ? 提供了多個(gè)排序接口： AMD， AMF， PORD， METIS和 SCOTCH 33 輸入矩陣 ? 矩陣類(lèi)型 矩陣類(lèi)型在初始化階段（ JOB=1）由所有進(jìn)程通過(guò)參數(shù) mumps par%SYM設(shè)定： 0: A是非對(duì)稱(chēng)型 1： A是對(duì)稱(chēng)正定型 3： A是一般對(duì)稱(chēng)矩陣 ? 矩陣的輸入格式 MUMPS提供了多種矩陣輸入格式，這些由參數(shù) ICNTL(5)和ICNTL(18)控制。 并且平均每天被下載一次。兩個(gè)文件 須被包含在程序中， MPI的初始化和終止通過(guò)調(diào)用 MPI_INIT和 MPI_FINALIZE完成。通過(guò)設(shè)定 JOB=6，然后調(diào)用 MUMPS由所有進(jìn)程完成問(wèn)題的求解。 ? ParMETIS基于 MPI并行庫(kù)，實(shí)現(xiàn)了用于無(wú)結(jié)構(gòu)圖劃分、網(wǎng)格劃分、計(jì)算稀疏矩陣的填充 約化次序等多種算法。 ? ParMETIS中實(shí)現(xiàn)的算法基于并行多層 k路圖劃分算法、自適應(yīng)再劃分算法及并行多約束算法。 ? 網(wǎng)格劃分 – 直接計(jì)算非常大規(guī)模網(wǎng)格高質(zhì)量劃分 , 無(wú)需應(yīng)用程序創(chuàng)建基本圖； – 提供網(wǎng)格對(duì)偶圖的高效并行程序。 ? 劃分加細(xì) – 改進(jìn)由其它劃分算法產(chǎn)生的劃分的質(zhì)量。 43 子程序調(diào)用 ParMetis可以執(zhí)行下列操作 無(wú)結(jié)構(gòu)圖劃分 是否存在頂點(diǎn)坐標(biāo) ParMETIS_V3_PartKway 你有什么時(shí)間 /質(zhì)量權(quán)衡 ParMETISV3_PartGeomKway ParMETIS_V3_PartGeom ParMETIS_V3_Mesh2Dual ParMETIS_V3_PartMeshKway ParMETIS_V3_AdaptiveRepart ParMETIS_V3_RefineKway ParMETIS_V3_NodeND 網(wǎng)格劃分 由網(wǎng)格構(gòu)造