五點差分格式求解泊松方程并行算法的研究

以二維靜電場泊松方程數值求解的串行算法(雅可比迭代、超松弛迭代)為基礎，提出了五點差分格式超松弛迭代(SOR)求解二維靜電場泊松方程的并行算法，通過與雅可比迭代(Jacobi)并行算法的時間復雜度、加速比和空間復雜度進行對比，得出超松弛迭代的并行算法具有更低的時間復雜度、空間復雜度和更高的加速比與效率。通過實驗驗證，CHIPIC軟件的泊松模塊宜采用超松弛迭代并行算法。
關 鍵 詞 雅可比迭代; 并行算法; 泊松; 超松弛迭代

CHIPIC[1]是我國自行開發的電磁粒子模擬[2]軟件，其模擬計算通?；ㄙM大量的時間，因此有必要開發其并行版本。作為這一工作的前期實踐，本文對其靜電場計算模塊即泊松模塊的并行計算進行了研究。
1 二維靜電場泊松方程的串行算法[3]
為簡單明了地說明算法的設計思想，本文采用一個最簡單求解二維場域內電位的例子。如圖1所示，一個長直接地金屬矩形槽，其側壁與底面電位均為0，頂蓋電位為100。則求解場域內電位?的方程為泊松方程(退化為拉普拉斯方程)：

2 二維靜電場泊松方程的并行算法
當今國外的電磁粒子模擬軟件[6-7]并行版本大都是基于消息傳遞機制[8](MPI)的。MPI被當前所有高性能并行機所支持，程序設計方便，并具有良好的擴展性，非常適合于機群系統。
通用的求解泊松方程的并行模塊大都采用Jacobi并行迭代算法[8-9]，因為Jacobi迭代算法中各個更新操作是完全并行的，可以采用分塊策略。一般有一維分塊和二維分塊兩種，二維分塊的優越性主要在于更好的擴展性。由于在通常的實際問題中網格數非常巨大，而PC機比較有限，目前的通用電磁粒子模擬軟件中采用一維分塊。SOR迭代算法每次計算第n+1次的U[i][j]時，都需要n+1次的U[i?1][j]和U[i][j?1]，初略看不適合分塊并行迭代。目前關于SOR的并行迭代算法主要有著色法[10]，但著色法可擴展性差，不適合通用的電磁粒子模擬軟件，因此有必要開發出基于SOR分塊并行迭代算法。