【正文】 ???????????這樣，對(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ù)值模擬。 ? 矩陣重排序 – 計(jì)算稀疏矩陣的填充 約化 (fillreducing)次序； – 使用基于節(jié)點(diǎn)的嵌套剖分算法，此算法顯示比其它流行重排序算法更優(yōu)越。 45 下面為一個(gè)無結(jié)構(gòu)圖的劃分過程： 46 直接網(wǎng)格劃分 ParMETIS_V3_PartMeshKway支持由網(wǎng)格（而不是圖）作為輸入的劃分和重劃分計(jì)算。 48 劃分加密 PARMETIS提供了用來改善已存在劃分質(zhì)量的子程序ParMETIS_V3_ RefineKway。 49 填充 約化 (fillreducing)次序 ParMETIS_V3_NodeND是 PARMETIS提供的計(jì)算填充 約化次序的子程序。 50 Parmetis輸入輸出格式 ? 在 Parmetis中，所有與圖有關(guān)的子程序的輸入格式包括：圖的鄰接結(jié)構(gòu)、頂點(diǎn)和邊的權(quán)重、描述圖如何被分布在各處理器上的數(shù)組。 PDE解法器 SNES(無約束優(yōu)化、 非線性解法器 ) SLES(線性方程解法器 ) TS時(shí)間步進(jìn) 矩陣 向量 索引集 KSP(Krylov子空間方法 ) PC(預(yù)條件 ) DRAW BLAS LAPACK MPI 應(yīng)用程序 解法器應(yīng)用程序解法器應(yīng)用程序解法器向量 索引集向量矩陣 索引集向量子空間方法矩陣 索引集向量預(yù)條件子空間方法矩陣 索引集向量預(yù)條件子空間方法矩陣 索引集向量線性方程解法器預(yù)條件子空間方法矩陣 索引集向量無約束優(yōu)化、 非線性解法器 線性方程解法器預(yù)條件子空間方法矩陣 索引集向量無約束優(yōu)化、 非線性解法器 線性方程解法器預(yù)條件子空間方法矩陣 索引集向量無約束優(yōu)化、 非線性解法器 線性方程解法器預(yù)條件子空間方法矩陣 索引集向量時(shí)間步進(jìn)無約束優(yōu)化、 非線性解法器 線性方程解法器預(yù)條件子空間方法矩陣 索引集向量應(yīng)用程序時(shí)間步進(jìn)無約束優(yōu)化、 非線性解法器 線性方程解法器預(yù)條件子空間方法矩陣 索引集向量時(shí)間步進(jìn)無約束優(yōu)化、 非線性解法器 線性方程解法器預(yù)條件子空間方法矩陣 索引集向量PETSc實(shí)現(xiàn)的層次結(jié)構(gòu) 57 PETSc的數(shù)值組件 非線性解法器 牛頓迭代法 其它 線搜索 信賴域 時(shí)間步法 Euler 方法 向后 Euler方法 擬時(shí)間步 其它 Krylov 子空間方法 GMR CG CGS BiCGSta TFQMR Richardson Chebyshev 其它 預(yù)條件子 加法 Schwarz 塊 Jacobi Jacobi ILU ICC LU 其它 向量 壓縮稀疏行 (AIJ) 塊壓縮稀疏 (BAIJ) 塊對(duì)角 (BDiag) 稠密 其它 索引集 索引 塊索引 跨度 其它 向量 58 PETSc的基本對(duì)象 ? 向量 向量是最簡(jiǎn)單的 PETSc對(duì)象。 59 PETSc的核心組件 PETSc的三個(gè)核心組件包括：線性方程求解器（ SLES）、非線性方程求解器（ SNES）和時(shí)間步進(jìn)積分器（ TS）。 ? 基本用法 ? SNESCreate：創(chuàng)建一個(gè)非線性方程求解環(huán)境 ? SNESSetType：設(shè)置非線性求解器的類型 ? SNESSetFromOptions：通過運(yùn)行參數(shù)設(shè)置 SNES運(yùn)行選項(xiàng) ? SNESSolve：?jiǎn)?dòng)一個(gè)非線性方程求解器 ? SNESDestroy：釋放一個(gè)非線性方程求解器 ? SNESSetFunction：設(shè)置非線性函數(shù) ? SNESSetJacobian：設(shè)置雅可比矩陣 61 ? 時(shí)間步進(jìn)積分 TS 時(shí)間步進(jìn)積分器，用于求解依賴時(shí)間或時(shí)間演化的 ODE 方程，或依賴時(shí)間的離散化后的 PDE方程。在這個(gè)意義上，用戶可以在 PETSc上開發(fā)任何基于消息傳遞的應(yīng)用程序。 /* 近似解，右端向量和分析解 */ Mat A。 PetscInitialize(amp。 CHKERRQ(ierr)。Iend)。 ierr = MatSetValues(A,1,amp。J,amp。CHKERRQ(ierr)。 ierr = MatSetValues(A,1,amp。CHKERRQ(ierr)。 ierr =VecDuplicate(u,amp。 CHKERRQ(ierr)。 } else{ ierr = VecSet(amp。 if(flg) {ierr = VecView(u,PETSC_VIEWER_STDOUT_WORLD)。ksp)。CHKERRQ(ierr)。 CHKERRQ(ierr)。 CHKERRQ(ierr)。 } 。 CHKERRQ(ierr)。 CHKERRQ(ierr)。 /*求解線性方程組 */ ierr = SLESSolve(sles,b,x,amp。 CHKERRQ(ierr)。flg)。 ierr = PetscRandomDestroy(rctx)。 66 /*設(shè)置精確解和右端向量 */ ierr = PetscOptionsHasName(PETSC_NULL,random_exact_sol,amp。 ierr =VecSetFromOptions(u)。CHKERRQ(ierr)。CHKERRQ(ierr)。J,amp。 ierr = MatSetValues(A,1,amp。 j = I i*n。 /*獲得局部劃分的上下界 */ ierr = MatGetOwnershipRange(A,amp。 ierr =PetscOptionsGetInt(PETSC_NULL,n,amp。 PetscScalar v, one = , neg_one = 。 64 /*$Id: ,v 2022/08/07 21:30:54 bsmith Exp $*/ /* 運(yùn)行方式 : mpirun np procs ex2 [help] [all PETSc options] */ static char help[] = Solves a linear system in parallel with SLES.\n\ Input parameters include: \n\ random_exact_sol : use a random exact solution vector\n\ view_exact_sol : write exact solution vector to stdout\n\ m mesh_x : number of mesh points in xdirection\n\ n mesh_n : number of mesh points in ydirection\n\n。主要包括以下幾種類型： ? 線性代數(shù)求解器，如 AMG、 BlockSolve9 DSCPACK、hypre、 ILUTP、 LUSOL、 SPAI、 SPOOLES、 SuperLU、SuperLU_Dist； ? 最優(yōu)化軟件，如 TAO、 Veltisto； ? 離散化和網(wǎng)格生成和優(yōu)化工具包，如 Overture、 SAMRAI、SUMAA3d； ? 常微分方程求解器，如 PVODE； ? 其它，如 Matlab、 ParMETIS。雅可比矩陣的求解是 SNES解法器的重要組成部分。 PETSc 的矩陣運(yùn)算和操作主要包括矩陣的創(chuàng)建、插值、聚集、各種算術(shù)運(yùn)算和釋放。 ? 基于 MPI、 BLAS庫、 LAPACK庫 ? 使用 Fortran、 C/C++開發(fā) 越來越多的應(yīng)用程序在 PETSc環(huán)境上開發(fā)，并逐漸顯示出 PETSc在高效求解大規(guī)模數(shù)值模擬問題方面的優(yōu)勢(shì)和威力 54 ? PETSc：并行可擴(kuò)展科學(xué)計(jì)算工具箱（ Parallel Extensible Toolkits for Scientific Computing） ? 核心人員：美國數(shù)學(xué)與計(jì)算機(jī)部、 Argonne國家重點(diǎn)實(shí)驗(yàn)室等等 ? 基于 MPI、 BLAS庫、 LAPACK庫 ? 使用 Fortran、 C/C++開發(fā) ? PETSc軟件包含一個(gè)功能強(qiáng)大的工具集以在高性能計(jì)算機(jī)上數(shù)值求解偏微分方程及其相關(guān)問題 ? 可移植性： CRAY T3D， T3E， Origin 2022, IBM SP, HP UX, ASCI Red, Blue Mountain, NOWs， LINUX， ALPHA等 ? 公開源代碼，免費(fèi)下載 55 ? PETSc 的一些模塊處理： – 索引集，包括用于向量索引的置換，重新計(jì)數(shù)等 – 向量 – 矩陣（一般是 稀疏 的） – 分布陣列（對(duì)正規(guī)的基于網(wǎng)格問題的并行化有用） – Krylov 子空間方法 – 預(yù)條件子，包括多重網(wǎng)格和稀疏直接解法器 – 非線性解法器 – 解時(shí)間相關(guān)（非線性） PDEs 的時(shí)間步進(jìn)解法器 56 體系結(jié)構(gòu) PETSc為用戶提供了一個(gè)通用的層次化應(yīng)用程序開發(fā)平臺(tái)。當(dāng)圖已經(jīng)被分成 P部分（ P是處理器數(shù)），圖被重新分布在各處理器。二是假設(shè)圖已很好地分布，并且初始劃分有好的平衡。實(shí)驗(yàn)表明，這個(gè)例行通常占用了 PARMETIS計(jì)算劃分時(shí)約一半的運(yùn)行時(shí)間 47 自適應(yīng)加密網(wǎng)格 PARMETIS提供了重劃分自適應(yīng)加密網(wǎng)格的子程序 ParMETIS_V3_ AdaptiveRepart。因此，它非?？欤ㄍǔ１?ParMETIS PartGeomKway快 5到 10倍），但它的計(jì)算質(zhì)量差。 ? 圖重劃分 – 快速計(jì)算自適應(yīng)加密網(wǎng)格的高質(zhì)量再劃分； – 優(yōu)化移去的頂點(diǎn)個(gè)數(shù)以及所得劃分的邊切割。在程序中，首先設(shè)定 JOB=1對(duì)初始化 MUMPS，由主進(jìn)程讀入求解的問題（ N, NZ, IRN, JCN, A, 和 HS）。 ? MUMPS基于多波前方法的直接求解方法。 在 , Ω為單位正方形 , 處理機(jī)網(wǎng)格為 N N，每個(gè)處理機(jī)上的網(wǎng)格為 n n, h=1/(Nn+1), 采用結(jié)構(gòu)網(wǎng)格界面和 5點(diǎn)差分離散 , 并考慮邊界條件。 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 。 %創(chuàng)建求解器 (PFMG) /* Solve the linear system */ HYPRE_StructPFMGSolve(solver, A, b, x)。 HYPRE_StructVectorInitialize(x)。 HYPRE_StructMatrixAssemble(A)。 HYPRE_StructGridAssemble(grid)。矩陣 A支持 HYPRE 的 ParCSR格式 、 PETSc 的矩陣形式和 ISIS++ Row的矩陣形式。比如求解非對(duì)稱矩陣的 GMRES和求解對(duì)稱矩陣的 CG（包括 PCG, CGNR, BiCGStab）。 – 確定處理器的二維網(wǎng)格結(jié)構(gòu)，分布矩陣到各處理器（稠密問題）。其通過調(diào)用不同的模塊，完成矩陣的三對(duì)角分解、正交化處理，得到收斂的 Ritz對(duì)等。