论文部分内容阅读
偏微分方程的数值求解问题,是通过使用数值离散方法将其转化为对稀疏线性方程组来求解的.常见的两种求解线性方程组为直接法和迭代法,当求解大型稀疏线性方程组时,迭代法中的Krylov子空间方法是最为重要、最常用的方法.直接将Krylov子空间方法在并行计算机运行,求解问题的效率往往非常低,所以探索能够适合在并行计算环境计算的Krylov子空间方法并行算法就十分有必要.在分布式内存并行计算机中,Krylov子空间方法中的内积计算引起的全局通信制约着并行算法的高效运行.所以成功的设计和实现Krylov子空间方法并行算法的关键方式就是削弱内积计算对全局通信开销的影响.由于内积计算会产生全局通信问题,本文对变预处理子逐次超松驰迭代(SOR)-双共轭残量法(BiCR)和预处理Jacobi一双共轭残量法(简称JBiCR)这两种方法进行了研究,其中变预处理子SOR一双共轭残量法(简称SOR-BiCR)是在双共轭残量法的基础上运用多种预条件技术得到的,JBiCR算法是由预处理BiCR算法中嵌入几步Jacobi迭代自适应构造而成,进一步为了使这两种算法在分布式并行计算环境中能够高效求解,分别改造变预处理子SOR-BiCR算法和JBiCR算法的计算次序,得到了适合求解大型稀疏非对称线性方程组并行化改进的变预处理SOR-双共轭残量算法(简称SOR-IBiCR)和改进的预处理Jacobi一双共轭残量法(简称PJBiCR),SOR-IBICR算法和PJBiCR算法都是将原算法离散的内积计算代替为连续的内积计算,并且将原来的算法两次的全局通信次数降为一次,算法中的内积计算与矩阵向量乘积互相独立,降低了数据相关性,以增加微小的计算量为代价,使得算法的并行效率得到了提高.通过理论分析对比SOR-IBiCR算法和SOR-BiCR算法的并行时间、加速比、可扩展性以及并行性能改进比率,结果说明SOR-IBiCR算法比SOR-BiCR算法有着更少的并行时间、更好的可扩展性和加速比,SOR-IBiCR算法的加速比能达到SOR-BiCR算法的2倍,并行性能改进比率达到了50%;通过理论分析对比PJBiCR算法和JBiCR算法的并行时间、加速比、可扩展性以及并行性能改进比率,结果说明PJBiCR算法比JBiCR算法有着更少的并行时间、更好的可扩展性和加速比,PJBiCR算法的加速比能达到JBiCR算法的2倍,并行性能改进比率达到了 50%.经由并行数值实验结果表明与理论分析一致.数值实验比较了 JBiCR与BiCR、CGS和BiCGSTAB算法收敛时间和收敛稳定性,结果表明JBiCR算法有着比这三种算法更好的收敛稳定性和更短的迭代计算时间.