二维泊松方程和扩散方程的一类显式并行算法

摘要

诸多物理现象都可用泊松方程和扩散方程来描述,泊松方程是数学中一个常见于静电学,机械工程和理论物理的偏微分方程；扩散方程常见于化学扩散,热传导,医学,生化方面和一定的生物反应过程.由许多偏微分方程的标准离散化得到的用于求解这两类方程的若干快速计算方法,受到了人们的密切关注.目前,大规模的科学工程计算需要高速度,大容量的并行机和有效的数值并行方法和并行算法.考虑到成本与速度,并行机的使用起到了非常重要的作用.同时,区域分解方法是一个很有力的工具,可将整个问题化为各个子域问题,然后并行求解,由于其构造简单,速度快,得到了广泛应用.
　　 在现代数值方法中,有限差分方法是最早且很完美的求解方法,所以对于研究抛物型和椭圆型问题的有限差分方法,备受人们的关注和重视.
　　 有限差分方法对于椭圆型问题的逼近往往需要求解较大的稀疏矩阵问题[1],随着现代计算机的发展,迭代方法如Jacobi,Gauss-Seidel,SOR方法[2,3]常被用在此大型计算中,也是解此大型方程组的一类很好的方法.众所周知,泊松方程的并行单元是利用Jacobi并行迭代算法[4]来解决的,因其有明显的并行性.[5]中冯慧等通过不同点的隐式差分格式之间的相互约化来建立新型迭代(Stencil)方法,此方法和Jacobi方法同样具有并行性,却比Jacobi收敛快.超松弛(SOR)迭代方法是很有效的方法,却没有本质的并行性.目前,仅有较少的方法可以实现并行迭代,如着色法[6]和点并行SOR方法[7]等,但很难拓展.
　　 而对于求解时间依赖的扩散问题的数值方法,主要有两种类型,显式和隐式差分方法.显式差分方法很容易在并行机上实现,有好的并行性,但由于稳定性限制[8],对时间步长的限制相当苛刻.隐式差分方法是绝对稳定的,但在每一时间步都需要去求解较大的线性或非线性代数方程组,计算效率不高.因此需要构造具有良好稳定性,并行性和计算精度的新的差分方法.八十年代初,Evans和Abdullah[9-11]设计了分组显式方法保证了数值计算的稳定性,同时由于显式求解而使该方法具有很好的并行性质,它是不同类型Saul'yev非对称格式[12]的恰当组合.在此基础上,张宝琳等在[13-15]中提出利用Saul'yev非对称格式构造分段隐式格式的思想,并恰当的使用交替技术建立了多种显-隐式和纯隐式交替并行方法,取得了稳定性和并行兼顾的研究结果.另外,Peaceman与Rachford在[16]中提出的交替方向隐式方法(ADI)具有一些相当好的性质,但是对于多指令流多数据流(MIMD)并行机来说,由于每个并行处理器在奇数时间层计算一列或若干列的数值,而在偶数时间层计算一行或若干行的数值,或者是相反,因而在每个时间层大部分数据需要从一个处理器传送到另一个处理器,这是很不经济的.
　　 在导师王文洽教授的悉心指导下,本文作者基于并行计算,区域分解和交替分组显式思想,对二维泊松方程和扩散方程构造了一类有效的显式并行算法,对方法进行了理论分析并给出了数值算例,均证实了我们在本文中所提的算法是有效的,实用的.全文共分四章,下面几段将简要介绍一下各章的主要内容.
　　 第一章,基于区域分解思想,对二维泊松方程提出了一种新的有限差分并行迭代(FDPI)算法.首先将求解区域划分为四个子区域,并从经典的五点差分格式构造出四个新的迭代格式.然后,在迭代次数为奇数或偶数时,分别给出新算法的实现过程,且证明了其收敛性.最后给出了数值算例以验证此迭代算法的有效性和精确性,而且也适用于二维变系数椭圆型问题.此章内容已发表在《Numerical Methods for PartialDifferential Equations》.
　　 本章内容的创新之处在于虽然迭代格式是半隐式的,但可结合边界条件和分组显式思想,显式地,并行地计算.特别地,格式中添加了松弛因子ω并理论分析得到最佳松弛因子ωopt,大大的提高了收敛速率,减少了迭代次数.在与Jacobi,Gauss-Seidel迭代算法和数学Stencil[5]方法的数值结果比较中发现,我们所提出的FDPI算法具有更少的迭代次数,更短的计算时间和更快的收敛速率.
　　 第二章,给出了求解二维泊松方程的另一种新的并行超松弛(P-SOR)迭代算法.利用四个超松弛(SOR)迭代格式完成算法,实现过程类似于第一章,最后数值试验说明此算法的优越性.本章内容已投到《International Journal of Computer Mathemat-ics》.
　　 此章内容的创新之处在于,众所周知的SOR算法并没有明显的并行性,而我们给出的新算法(P-SOR)具有本质并行性,并且通过与Jacobi,Gauss-Seidel,数学Stencil[5]及第一章中的FDPI算法关于时间的消耗,速度及空间复杂性的比较,表明本节提出的算法更为有效.
　　 第三章,基于区域分解和分组显式思想,给出了求解二维扩散方程的一种新的有限差分并行算法.首先构造了逼近扩散方程的四个新的差分格式,然后将求解域划分为四个子域,在奇数或偶数时间层上算法的实现过程类似于第一章,并证明了格式的无条件稳定性,且误差阶为O(τ+h2).最后数值试验说明算法的适用性,并且时间步长充分小的前提下误差关于空间达到2阶.本章内容已投到《Applied Mathematicsand Computation》.
　　 第四章,提出了求解二维扩散方程一种新的交替分组(N-AGE)算法.采用显式方法[10],使用第三章中构造的四个差分格式在奇数或偶数时间层上交替使用,来完成新的显式算法.最后数值试验通过与第三章中的并行算法和分组显式方法[10]在同时间和不同空间参数下误差的比较,表明了此算法的有效性和精确性.本章内容已投到《计算数学》.
　　 第三,四章的创新之处在于,构造的新的差分格式虽是隐式的,但利用分组显式思想可显式求解.并且,差分格式的交替使用导致截断误差中的主要项符号相反,从而抵消.数值试验也验证了此类算法的有效性,且关于空间的收敛速率达到2阶,以及也适用于二维变系数扩散问题.

目录

文摘

英文文摘

插图目录

表格目录

符号

第一章 泊松方程的一种新的有限差分并行迭代算法

§1.1引言

§1.2有限差分并行迭代(FDPI)算法

§1.3收敛性分析

§1.4最佳松弛因子与渐近收敛率

§1.4.1最佳松弛因子

§1.4.2渐近收敛率

§1.5数值算例

§1.6结论

第二章 求解泊松方程的并行SOR迭代算法

§2.1引言

§2.2有限差分格式

§2.3算法实现

§2.3.1区域分解

§2.3.2并行SOR算法

§2.4数值算例

第三章 二维扩散方程的有效的并行差分算法

§3.1引言

§3.2问题

§3.3并行差分算法

§3.3.1有限差分格式

§3.3.2区域分解

§3.3.3并行差分算法

§3.4稳定性分析

§3.5截断误差分析

§3.6数值算例

§3.7结论

第四章 扩散方程的一种新的交替分组方法

§4.1引言

§4.2差分格式

§4.3新的交替分组显式算法(N-AGE)

§4.4稳定性分析

§4.5数值算例

参考文献

致谢

攻读博士学位期间完成论文情况

作者简介

学位论文评阅及答辩情况表