第八讲二维 Poisson 方程的并行求解算法.pptVIP

第八讲二维 Poisson 方程的并行求解算法 主要内容 二维Poisson方程 二维Poisson方程 Jacobi 迭代 程序示例 并行算法 并行算法 并行算法 并行算法 并行算法 上机作业 * * 二维 Poisson 方程的差分离散 差分方程的 Jacobi 算法 串行算法 并行算法 红黑排序的 GS 算法 二维 Poisson 方程 其中 ?=(0, a) ? (0, b)，?? 为边界 o a b … … 1 2 3 4 … … 1 2 3 4 … … 五点差分离散 x-方向和 y-方向的步长分别取为 网格点：( xi , yj )，其中 xi = i*hx, yj = j*hy , i = 0, 1, ... , m, j = 0, 1, ... , n u 在 ( xi , yj ) 点的近似值记为 ui, j 0 1 2 3 . . . . . . m 0 1 2 3 . . . . . . n 蓝色为内点 黑色为边界点 ui, j ui, j-1 ui+1, j ui, j+1 ui-1, j 离散后的差分方程为 整理后可得 ui,j ui, j-1 ui+1, j ui, j+1 ui-1, j i = 1, ... , m-1, j = 1, ... , n-1 边界条件： 其中 求解该差分方程组的 Jacobi 迭代格式为 i = 1, ... , n-1, j = 1, ... , m-1 k = 0, 1, 2, ... 例：取 串行程序： jacobi.f 此时 Poisson 方程的解析解为 并行求解的基本思想：区域分解 采用区域分解技术： 假设使用 np 个进程并行求解，则将整个求解区域分解成 npx ? npy 个子区域，其中 npx ? npy = np 每个进程负责求解一个子区域 相邻两个子区域有一个网格步的重叠： 便于子区域间的数据传递 每个子区域包含的网格点大致相等 以 3 ? 3 的区域分解为例 蓝色为内点 黑色为边界点 0 1 2 3 4 5 6 7 8 蓝色为内点 黑色为边界点 0 1 2 3 4 5 6 7 8 程序中使用的一些参数： 子区域的左下角网格点 (0, 0) 在整个区域中的位置（用于计算解析解） x0, y0 子区域的 x- 向和 y-方向的网格点数 -1 nlx, nly 整个区域 x-方向和 y-方向的网格点数 -1 nx, ny 当前进程的 x-方向和 y-方向的进程坐标 myidx, myidy 当前进程的进程号 myid x-方向和 y-方向的进程个数 npx, npy 进程个数 np 子区域 蓝色为子区域内点 黑色为子区域边界点 （伪边界） 网格点：(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)：子区域的左下角 几个关系式： myidx, myidy 与 myid 的关系式： nlx 与 nx 的关系式： myidx = myid % npx myidy = myid / npx myid = myidx + myidy * npx nlx = (nx-1)/npx + 2, (myidx rx) (nx-1)/npx + 1, (myidx ? rx) 其中：rx = (nx-1) % npx nly 与 ny 的关系式类似 子区域中的原点 (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