《第八讲二维Poisson方程的并行求解算法.ppt》由会员分享，可在线阅读，更多相关《第八讲二维Poisson方程的并行求解算法.ppt（17页珍藏版）》请在三一文库上搜索。
1、1,第八讲 二维 Poisson 方程的 并行求解算法,2,主要内容,二维 Poisson 方程的差分离散 差分方程的 Jacobi 算法 串行算法 并行算法 红黑排序的 GS 算法,3,二维Poisson方程,二维 Poisson 方程,其中 =(0, a) (0, b)， 为边界, ,1 2 3 4 ,1 2 3 4 ,4,0 1 2 3 . . . . . . m,0 1 2 3 . . . . . . n,蓝色为内点,黑色为边界点,5,6,二维Poisson方程,离散后的差分方程为,整理后可得,i = 1, . , m-1, j = 1, . , n-1,边界条件：,其中,7,Jaco
2、bi 迭代,求解该差分方程组的 Jacobi 迭代格式为,i = 1, . , n-1, j = 1, . , m-1,k = 0, 1, 2, .,8,程序示例,例：取,串行程序： jacobi.f,此时 Poisson 方程的解析解为,9,并行算法,并行求解的基本思想：区域分解,采用区域分解技术： 假设使用 np 个进程并行求解，则将整个求解区域分解成 npx npy 个子区域，其中 npx npy = np,每个进程负责求解一个子区域,相邻两个子区域有一个网格步的重叠： 便于子区域间的数据传递,每个子区域包含的网格点大致相等,以 3 3 的区域分解为例,10,蓝色为内点,黑色为边界点,0
3、,1,2,3,4,5,6,7,8,11,蓝色为内点,黑色为边界点,0,1,2,3,4,5,6,7,8,12,并行算法,程序中使用的一些参数：,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),14,并行算法,几个关系式：,myidx, myidy 与 myid 的关系式：,nlx 与 nx 的关系式：,myidx = myid % npx myidy = myid / npx myid = myidx + my
4、idy * npx,nlx =,(nx-1)/npx + 2, (myidx rx) (nx-1)/npx + 1, (myidx rx),其中：rx = (nx-1) % npx,nly 与 ny 的关系式类似,15,并行算法,子区域中的原点 (0,0) 在整个网格中的坐标,x0 = myidx * (nx-1)/npx + min(myidx, rx) y0 = myidy * (ny-1)/npy + min(myidy, ry),其中：,rx = (nx-1) % npx ry = (ny-1) % npy,并行计算程序： jacobi_mpi.f,16,上机作业,将 Jacobi 迭代改为 红黑排序的 Gauss-Seidel 迭代,红点: i+j=2k 黑点: i+j=2k+1,红黑排序 GS 算法： 先更新红点的值 再更新黑点的值 依次类推，不断循环,17,(x0,y0),(i,j)?,红、黑?,