二维Poisson方程的并行求解算法.pptxVIP

1第八讲

二维Poisson方程的

并行求解算法

主要内容201.二维Poisson方程的差分离散02.差分方程的Jacobi算法03.串行算法04.并行算法05.红黑排序的GS算法

二维Poisson方程3二维Poisson方程其中?=(0,a)?(0,b)，??为边界oab……1234……1234……五点差分离散x-方向和y-方向的步长分别取为网格点：(xi,yj)，其中xi=i*hx,yj=j*hy,i=0,1,...,m,j=0,1,...,nu在(xi,yj)点的近似值记为ui,j

40123......m0123......n蓝色为内点黑色为边界点

ui,jui,j-1ui+1,jui,j+1ui-1,j

二维Poisson方程6离散后的差分方程为整理后可得ui,jui,j-1ui+1,jui,j+1ui-1,ji=1,...,m-1,j=1,...,n-1边界条件：其中

求解该差分方程组的Jacobi迭代格式为Jacobi迭代7i=1,...,n-1,j=1,...,m-1k=0,1,2,...0201

程序示例8例：取1串行程序：jacobi.f2此时Poisson方程的解析解为3

并行算法9并行求解的基本思想：区域分解采用区域分解技术：假设使用np个进程并行求解，则将整个求解区域分解成

npx?npy个子区域，其中npx?npy=np每个进程负责求解一个子区域相邻两个子区域有一个网格步的重叠：便于子区域间的数据传递每个子区域包含的网格点大致相等以3?3的区域分解为例

蓝色为内点01黑色为边界点02

蓝色为内点黑色为边界点

并行算法12程序中使用的一些参数：np进程个数npx,npyx-方向和y-方向的进程个数myid当前进程的进程号myidx,myidy当前进程的x-方向和y-方向的进程坐标nx,ny整个区域x-方向和y-方向的网格点数-1nlx,nly子区域的x-向和y-方向的网格点数-1x0,y0子区域的左下角网格点(0,0)在整个区域中的位置（用于计算解析解）

并行算法13子区域蓝色为子区域内点黑色为子区域边界点

（伪边界）网格点：(0:nlx,0:nly)内点：

(1:nlx-1,1:nly-1)“边界点”：

(0,1:nly-1)

(nlx,1:nly-1)

(1:nlx-1,0)

(1:nlx-1,nly)(0,0)：子区域的左下角

几个关系式：并行算法14myidx,myidy与myid的关系式：nlx与nx的关系式：myidx=myid%npxmyidy=myid/npxmyid=myidx+myidy*npxnlx=(nx-1)/npx+2,(myidxrx)(nx-1)/npx+1,(myidx?rx)其中：rx=(nx-1)%npxnly与ny的关系式类似

并行算法15其中：x0=myidx*(nx-1)/npx+min(myidx,rx)y0=myidy*(ny-1)/npy+min(myidy,ry)子区域中的原点(0,0)在整个网格中的坐标01rx=(nx-1)%npxry=(ny-1)%npy并行计算程序：jacobi_mpi.f02

上机作业16将Jacobi迭代改为红黑排序的Gauss-Seidel迭代012345678红点:i+j=2k黑点:i+j=2k+1红黑排序GS算法：先更新红点的值再更新黑点的值依次类推，不断循环x0,y0)(i,j)?红、黑?