【正文】 rMETIS_V3_AdaptiveRepart，該子程序假設(shè)圖已很好的被分布在各處理器。 48 劃分加密 PARMETIS提供了用來改善已存在劃分質(zhì)量的子程序ParMETIS_V3_ RefineKway。實(shí)驗(yàn)表明，這個(gè)例行通常占用了 PARMETIS計(jì)算劃分時(shí)約一半的運(yùn)行時(shí)間 47 自適應(yīng)加密網(wǎng)格 PARMETIS提供了重劃分自適應(yīng)加密網(wǎng)格的子程序 ParMETIS_V3_ AdaptiveRepart。它可以用來為ParMETIS_V3_AdaptiveRepart子程序構(gòu)建一個(gè)輸入圖形。 ? PARMETIS沒有提供直接計(jì)算網(wǎng)格自適應(yīng)重劃分這樣的例程。 45 下面為一個(gè)無結(jié)構(gòu)圖的劃分過程： 46 直接網(wǎng)格劃分 ParMETIS_V3_PartMeshKway支持由網(wǎng)格（而不是圖）作為輸入的劃分和重劃分計(jì)算。因此，它非?？欤ㄍǔ１?ParMETIS PartGeomKway快 5到 10倍），但它的計(jì)算質(zhì)量差。 ? 當(dāng)頂點(diǎn)坐標(biāo)可用時(shí)， PARMETIS也為非結(jié)構(gòu)圖劃分提供了ParMETIS_PartGeom函數(shù)。該算法已被證明能夠迅速生成高質(zhì)量的劃分。 ? 矩陣重排序 – 計(jì)算稀疏矩陣的填充 約化 (fillreducing)次序； – 使用基于節(jié)點(diǎn)的嵌套剖分算法，此算法顯示比其它流行重排序算法更優(yōu)越。 ? 圖重劃分 – 快速計(jì)算自適應(yīng)加密網(wǎng)格的高質(zhì)量再劃分； – 優(yōu)化移去的頂點(diǎn)個(gè)數(shù)以及所得劃分的邊切割。 42 功能描述 ? 圖劃分 – 快速計(jì)算非常大規(guī)模圖的高質(zhì)量劃分； – 利用幾何信息 (當(dāng)可用時(shí) ) 降低劃分時(shí)間而不損失質(zhì)量； – 可為多相及多物理計(jì)算劃分圖。 ? ParMETIS擴(kuò)展了 METIS所提供的功能并包含了特別適合于并行計(jì)算和大規(guī)模數(shù)值模擬的子程序。最后設(shè)定 JOB=2，調(diào)用 MUMPS完成數(shù)據(jù)結(jié)構(gòu)的釋放 PROGRAM MUMPS_EXAMPLE NCLUDE ’’ INCLUDE ’’ TYPE (DMUMPS_STRUC) id INTEGER IERR, I CALL MPI_INIT(IERR) C Define a municator for the package id%COMM = MPI_COMM_WORLD C Ask for unsymmetric code id%SYM = 0 C Host working id%PAR = 1 C Initialize an instance of the package id%JOB = 1 CALL DMUMPS(id) 39 C Define problem on the host (processor 0) IF ( id%MYID .eq. 0 ) THEN READ(5,*) id%N READ(5,*) id%NZ ALLOCATE( id%IRN ( id%NZ ) ) ALLOCATE( id%JCN ( id%NZ ) ) ALLOCATE( id%A( id%NZ ) ) ALLOCATE( id%RHS ( id%N ) ) READ(5,*) ( id%IRN(I) ,I=1, id%NZ ) READ(5,*) ( id%JCN(I) ,I=1, id%NZ ) READ(5,*) ( id%A(I),I=1, id%NZ ) READ(5,*) ( id%RHS(I) ,I=1, id%N ) END IF C Call package for solution id%JOB = 6 CALL DMUMPS(id) C Solution has been assembled on the host IF ( id%MYID .eq. 0 ) THEN WRITE( 6, * ) ’ Solution is ’,(id%RHS(I),I=1,id%N) END IF C Deallocate user data IF ( id%MYID .eq. 0 )THEN DEALLOCATE( id%IRN ) DEALLOCATE( id%JCN ) DEALLOCATE( id%A ) DEALLOCATE( id%RHS ) END IF C Destroy the instance (deallocate internal data structures) id%JOB = 2 CALL DMUMPS(id) CALL MPI_FINALIZE(IERR) STOP END 55?2 3 4331 1 2241??????????20249613????????????????這樣，對(duì)一個(gè)構(gòu)造好的 矩陣和右端向量： ， 我們給出如下輸入： 5 ： N 12 : NZ 1 2 2 3 4 3 5 5 2 1 1 1 5 2 3 4 2 5 3 2 1 3 3 3 : A :RHS 我們將得到解 RHS(i) = i, i = 1, . . . , 5. 40 ParMETIS并行軟件 Lawrence Livermore National Laboratory 41 ParMETIS ParMETIS：并行圖劃分和填充 約化矩陣排序 (Parallel Graph Partitioning and Fillreducing Matrix Ordering) ， 特別適合于大規(guī)模無結(jié)構(gòu)網(wǎng)格的并行數(shù)值模擬。在程序中，首先設(shè)定 JOB=1對(duì)初始化 MUMPS，由主進(jìn)程讀入求解的問題（ N, NZ, IRN, JCN, A, 和 HS）。 ? 典型應(yīng)用包括： – 結(jié)構(gòu)力學(xué)和 CAD – 流體力學(xué)、磁流體和物理化學(xué) – 地震波傳播與成像，海洋模式 – 聲學(xué)和電磁學(xué)傳播 – 有限元分析，數(shù)值優(yōu)化，仿真 – 航空、地球物理等 37 ? OSSAU code of French CEA/CESTA：2D / 3D structural mechanics code ? ODYSSEE code of French CEA/CESTA 已成功應(yīng)用到具有 3千萬未知量的 3D網(wǎng)格問題 ? Electromagism code (Finite Element Meth. + Integral Equation) ? Complex double precision, Schur Compl. ? Fluid mechanics ? LU factorization with static pivoting (SuperLU approach like) ? Car body ? 148770 unknowns and 5396386 nonzeros 38 MUMPS使用方法及實(shí)例 ? 組裝格式程序 下面是使用 MUMPS計(jì)算雙精度問題的組裝格式例子程序。 ?單元格式： 矩陣由主進(jìn)程 (host)集中輸入， 置 ICNTL(5)=1 ICNTL(18)=0 ?組裝格式（ assembled format） – 矩陣由主進(jìn)程 (host)集中輸入 – 結(jié)構(gòu)由主進(jìn)程提供 (analysis) – 元素被分布到各處理器上 (numeric factorization) 34 主要計(jì)算步 ? MUMPS計(jì)算 Ax=b通過三步完成 : (1)分析 (JOB=1) ? 主進(jìn)程執(zhí)行排序操作 ? 主進(jìn)程執(zhí)行符號(hào)分解 (2) A=LU或 A=LDLT分解 (JOB=2) ? A被分布到各處理器 ? 由主進(jìn)程和一個(gè)或多個(gè)從進(jìn)程對(duì)每個(gè)波前矩陣進(jìn)行數(shù)值分解 (3) 求解 (JOB=3) ? b由主進(jìn)程分布到各處理器 ? x由分布到各處理器的因子計(jì)算得到 ? x被聚集到主進(jìn)程或分布到各處理器 35 主要特性 ? 每個(gè)處理階段可獨(dú)立調(diào)用 ? 異步通信 使得計(jì)算和通信實(shí)現(xiàn)了重疊 ? 動(dòng)態(tài)調(diào)度 算法是自適應(yīng)的，在執(zhí)行時(shí)重分布任務(wù)和數(shù)據(jù)到適當(dāng)?shù)奶幚砥? 36 MUMPS應(yīng)用 ? MUMPS用戶包括學(xué)術(shù)界和工業(yè)界，目前用戶數(shù)已超過 1000個(gè)。 32 主要功能 ? 求解不同類型的稀疏矩陣方程問題： 對(duì)稱或非對(duì)稱矩陣（部分主元法），復(fù)和實(shí)算術(shù)矩陣 ? 提供了多種矩陣輸入格式： ? 組裝格式（ assembled format） ? 分布式組裝格式（ distributed assembled format） ? 單元格式（ elemental format） ? 迭代加密和向前誤差分析 。 ? MUMPS基于多波前方法的直接求解方法。 4種迭代法： SMG、 PFMG、 PCG、 GMRES, 后兩種迭代法可以增加 SMG、 PFMG, 對(duì)角或塊 Jacobi等 4種預(yù)條件子。 邊界條件 : u0 =(sin(5πx)+sin(5πy))/1000。 對(duì)流系數(shù) B=。 在 , Ω為單位正方形 , 處理機(jī)網(wǎng)格為 N N，每個(gè)處理機(jī)上的網(wǎng)格為 n n, h=1/(Nn+1), 采用結(jié)構(gòu)網(wǎng)格界面和 5點(diǎn)差分離散 , 并考慮邊界條件。 ub] = [bi Aibu0 。 考慮到邊界條件 u= u0 on ?Ω, 即 ub= u0 . 于是 [Aii 0 。 ub], b = [bi 。 28 算例 ? 對(duì)流 反應(yīng) 擴(kuò)散方程 對(duì)流 反應(yīng) 擴(kuò)散 (ConvectionReactionDiffusion)方程 : div (K grad u + B u) + C u = F in Ω, 采用五點(diǎn)差分離散 , 得到方程組 : Au = b, 其中 A = [Aii Aib 。 HYPRE_StructVectorDestroy(b)。 HYPRE_StructStencilDestroy(stencil)。 HYPRE_StructPFMGDestroy(solver)。 %創(chuàng)建求解器 (PFMG) /* Solve the linear system */ HYPRE_StructPFMGSolve(solver, A, b, x)。 /* optional */ HYPRE_StructPFMGSetTol(solver, )。solver)。 ... HYPRE_StructVectorAssemble(x)。 HYPRE_StructVectorInitialize(x)。 HYPRE_StructVectorCreate(MPI_COMM_WORLD, grid, amp。 % 右端向量的初始化 HYPRE_StructVectorSetBoxValues(b, ilower, iupper, bvalues)。b)。 HYPRE_StructMatrixAssemble(A)。 HYPRE_StructMatrixInitialize(A)。 /* Set up the matrix, righthand side, and initial guess*/ HYPRE_StructMatrixCreate(MPI_COMM_WORLD, grid, stencil, amp。stencil)。 HYPRE_StructGridAssemble(grid)。grid)。而 PFMG僅使用簡(jiǎn)單的點(diǎn)光滑，因此 PFMG的健壯性不如 SMG，但是它在作 V循環(huán)迭代時(shí)效率更高 . – BoomerAMG既可作為迭代法 , 也可作為預(yù)條件子 。其中 SMG和 BoomerAMG是目前實(shí)際應(yīng)用中使用最廣泛的兩個(gè)解法器 . 25 – SMG求解矩形網(wǎng)格下對(duì)流擴(kuò)散方程的 FDM, FE