【作者】 许秋燕；

【导师】 王文洽；

【作者基本信息】 山东大学 ， 计算数学， 2010， 博士

【摘要】 诸多物理现象都可用泊松方程和扩散方程来描述,泊松方程是数学中一个常见于静电学,机械工程和理论物理的偏微分方程；扩散方程常见于化学扩散,热传导,医学,生化方面和一定的生物反应过程.由许多偏微分方程的标准离散化得到的用于求解这两类方程的若干快速计算方法,受到了人们的密切关注.目前,大规模的科学工程计算需要高速度,大容量的并行机和有效的数值并行方法和并行算法.考虑到成本与速度,并行机的使用起到了非常重要的作用.同时,区域分解方法是一个很有力的工具,可将整个问题化为各个子域问题,然后并行求解,由于其构造简单,速度快,得到了广泛应用.在现代数值方法中,有限差分方法是最早且很完美的求解方法,所以对于研究抛物型和椭圆型问题的有限差分方法,备受人们的关注和重视.有限差分方法对于椭圆型问题的逼近往往需要求解较大的稀疏矩阵问题[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 Partial Differential 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 Mathematics and Computation》.第四章,提出了求解二维扩散方程一种新的交替分组(N-AGE)算法.采用显式方法[10],使用第三章中构造的四个差分格式在奇数或偶数时间层上交替使用,来完成新的显式算法.最后数值试验通过与第三章中的并行算法和分组显式方法[10]在同时间和不同空间参数下误差的比较,表明了此算法的有效性和精确性.本章内容已投到《计算数学》.第三,四章的创新之处在于,构造的新的差分格式虽是隐式的,但利用分组显式思想可显式求解.并且,差分格式的交替使用导致截断误差中的主要项符号相反,从而抵消.数值试验也验证了此类算法的有效性,且关于空间的收敛速率达到2阶,以及也适用于二维变系数扩散问题.更多还原

【Abstract】 Several physical phenomena are modeled by diffusion equations and poisson equa-tions. The former usually exist in electrostatics, mechanical engineering and theoreti-cal physics, and the latter include chemical diffusion, heat conduction, medical science, biochemistry and certain biological process etc.. A lot of attention has been devoted to the introduction of several fast computational methods for solving these equations, which are derived from the discretization of many standard PDE’s. At present, the large scale scientific and engineering computations need the parallel computer with massively parallel processors of higher speed and large memory and also need effective parallel numerical methods and parallel algorithms. The utilization of parallel com-puters offers a significant advantage in terms of cost and speed. Meanwhile, domain decomposition is a powerful tool, which can be used to divide the global problem into smaller sub-domains that can be solved in parallel, and also it is paid more attention due to their simpler construction and larger speed-up.Among modern numerical methods, the finite difference method is the earliest and most perfect method. So the finite difference method for solving parabolic and elliptic problems is always a focal which peoples are care about.The application of finite difference approximations to elliptic partial differential equations often results in a large set of simultaneous linear equation[1]. It is well known that iterative methods such as Jacobi, Gauss-Seidel, SOR methods [2,3], ultilizing the great speeds of mordern-day computers, are extensively used in large-scale computa-tions, which are normally considered as suitable approach for solving such system of equations. As we known, the parallel modules for Poisson equation are often solved by Jacobi iterative algorithm[4], since it has obvious parallelization. Fenhui et al.[5] constructed the new iteration method for elliptical equation by elimination between difference scheme of different nodes, and the method had same parallelism as Jacobi method and higher convergence rate. The successive overrelaxation (SOR) iterative algorithm can not be iterated in parallel obviously, at present there is a few of meth-ods, such as coloring method[6] and Parallel Point SOR method[7], which are weak to extend.And for numerical solution of time-dependent diffusion problems, there are two types of finite difference method, explicit and implicit difference methods. The ex-plicit method is easy to implement on parallel computer, and parallel efficiencies are higher, but it has severe time step restriction due to stability constraint [8]. The im-plicit method is not any time step restriction, but in each time step one has to solve a global linear or nonlinear algebraic system of equations which implementation on parallel computer is not straightforward. So it is worthy to constructing other new difference methods which have better stability, parallelism and high-precision. In the early eighties, Evans and Abdullah [9-11] proposed the idea which constructed group explicit method by appropriate combination of different Saul’yev asymmetric schemes. The group explicit method keeps the stability of numerical computing, and has bet-ter parallelism because it can be solved explicitly. Based on this, Zhang Baolin et al. [13-15] give out the idea which constructed the segment implicit schemes by using the Saul’yev [12] asymmetric schemes, and set up a variety of explicit-implicit and pure implicit alternating parallel methods by making use of alternate technology. These methods can keep the stability and parallelism. In addition, Peaceman and Rachford provide the Alternating Direction Implicit (ADI) method [16] which has some good properties. But for multiple instruction and multiple data stream (MIMD) parallel computer, since each parallel processor Layer in the calculation of an odd time or number of column values, and in even time line or number line layer calculated values, or is the opposite, and therefore most of the data at each time layer needs to send a processor to another processor, which is not very economical.Under the aborative guidance of Professor Wenqia Wang, the author constructed some efficient explicit and parallel difference algorithms for two-dimensional Poisson problem and diffusion problem which contain parallel computing, domain decompo-sition and alternating group explicit method. And the stability of these methods are proved to unconditionally stable and some numerical experiments indicate their applicability. Both theoretical analysis and numerical experiments show that these algorithms proposed in this dissertation are effective and reliable. The dissertation is divided into three chapters.In Chapter 1, a new finite difference parallel iterative (FDPI) algorithms for solv-ing 2D Poisson equation based on domain decomposition strategy are introduced. First the domain is divided into four sub-domains and four iterative schemes are constructed from the classical five-point difference scheme. Then the new algorithm is implemented differently with the number of iterations of odd or even. The convergence of the pre-sented algorithm is proved. Finally several numerical experiments are performed to examine the efficiency and accuracy of the iterative algorithm. And the algorithm is applicable to 2D variable coefficient elliptic problems. The work about Chapter 1 is published in《Numerical Methods for Partial Differential Equations》.The new idea of Chapter 1 is that although the iterative schemes are semi-implicit, they can be computed explicitly and in parallel in combining with the boundary condi-tions. Particularly, a relaxation factorωis added into the iterative schemes to improve the convergence rate and decrease the iteration number, in which the optimal relaxation factorωopt is obtained. The comparison between the numerical results that are derived from Jacobi, Gauss-Seidel iterative algorithms, Mathematics Stencil [5] method and the presented algorithm demonstrates that the presented algorithm has smaller num-ber of iterations, shorter computational time and faster convergence rate.Chapter 2 gives a new parallel SOR iterative (P-SOR) algorithm for solving 2D Poisson equation. The four successive overrelaxation (SOR) iterative schemes are used to implement the algorithm differently with the number of iterations of odd or even. Several numerical experiments are presented to examine the superior of the algorithm. The work about Chapter 2 has been submitted to《International Journal of Computer Mathematics》.The new idea of Chapter 2 is that, the well-known SOR iterative algorithm can not be iterated in parallel obviously, while this new algorithm (P-SOR) has intrinsic paral-lelization. Moreover, the results of numerical experiments show that P-SOR iterative algorithm should be adopted by comparing the time complexity, speedup and space complexity with Jacobi, Gauss-Seidel, Stencil [5] and FDPI in Chapter 1 algorithms. In Chapter 3, ar. efficient finite difference parallel algorithm for solving 2D diffusion equation are given, which are based on domain decomposition. First we constructs four new difference schemes to approximate the diffusion equation. Then the solution domain is divided into four sub-domains. Using the idea in Chapter 1 to implement the algorithm differently at odd or even time levels. The algorithm is unconditionally stable and has an accuracy of O(τ+h2). Finally, several numerical experiments indicates the applicability and the rate of convergence is nearly of order 2. The work about Chapter 3 has been submitted to《Applied Mathematics and Computation》.Chapter 4 provides a new alternating group explicit algorithm for 2D diffusion equation. Due to explicit method [10], the four difference schemes constructed in Chapter 3 are used to implement this new explicit algorithm differently in odd or even time levels. Numerical experiments show the efficiency and accuracy of the new algorithm by comparing the errors with the algorithm in Chapter 3 and explicit method in [10] under the same time and space parameters. The work about Chapter 3 has been submitted to《Chinese Journal of Computational Mathematics》. The new idea of Chapter 3 and 4 is that the new difference schemes constructed are implicit, but they can be computed explicitly mainly using explicit group strategy. Moreover, the alternate use of different schemes with truncation errors of opposite signs can lead to the cancelation of error terms at most points on the mesh lines. By numerical experiments, the efficiency of the new algorithms are confirmed and the ratio of convergence is of order 2 in space. And also show that the new algorithms is applicable to 2D variable coefficient diffusion problems.更多还原