发展方程的重叠型区域分解并行算法

论文摘要

区域分解算法是上世纪八十年代崛起的新方向.由于该方法能将大型问题分解为小型问题、复杂边值问题分解为简单边值问题、串行问题分解为并行问题等其它方法无可比拟的优越性,而一举成为计算数学的热门领域.尤其是近些年,随着并行计算机和并行算法的迅速发展,区域分解算法正成为解决具有复杂区域或复杂过程的现实生活问题的强有力的工具.区域分解算法大致可以分为两类:重叠型区域分解算法和非重叠型区域分解算法.子区域的选择主要考虑区域形状的可计算性以及问题的物理背景.尤其是后者,特别适用于在不同物理子区域上有不同控制方程的复合问题.非重叠型区域分解算法实现起来比较直观易用,而重叠型区域分解法的理论分析较为容易些.本文我们的研究重点就是重叠型区域分解算法.重叠型区域分解算法是一种重要的求解偏微分方程的数值方法,在工程领域中有着广泛的应用.最早的重叠型区域分解算法源于经典的Schwarz交替法.近年来建立在Schwarz交替法基础上的区域分解法在理论分析和实际应用中取得令人注目的发展,已成为一种有效的迭代方法.对于椭圆型问题,许多基于重叠型区域分解的数值方法已经建立;Lions对热传导方程提出了的一类建立在两个子区域基础上的Schwarz交替算法,给出了收敛性结果,但没有给出误差估计;X.C.Cai构建了一类加性Schwarz算法和乘积性Schwarz算法,并证明了算法的收敛性,但作者没有详细讨论收敛率对离散参数的依赖性;芮洪兴教授和羊丹平教授论证了在每一时间层上收敛性及误差估计对子区域长度、空间网格步长、时间步长和迭代次数的依赖性.经典的Schwarz交替法不是并行的,随着并行计算的发展,出现了多种可完全并行化的加性Schwarz算法.M.Dryja,O.B.Wildund,T.M.Shih等皆独立提出不同的算法,这些算法可克服交替方法的串行性,更利于并行处理.J.Xu系统地介绍了求解对称正定问题的各种迭代方法,主要是利用区域分解和子区域校正法从理论上建立了并行子区域校正和串行子区域校正这两类算法.关于此类方法X.C.Tai也做了大量的研究工作文献[44]中,结合一般Galerkin有限元方法,杨建华和羊丹平教授将并行子区域校正算法应用于抛物型方程,并得到了收敛阶O(δ~m),其中0＜δ＜1.在导师羊丹平教授的悉心指导下,本文作者对重叠型区域分解并行算法做了部分研究工作.基于徐进超教授提出的并行子区域校正算法(PSC)思想,结合一些熟知的数值方法,如经典混合有限元方法、分裂正定混合元方法、最小二乘方法等等,利用单位分解函数的特性,合理地分配重叠区域上的校正量,对抛物问题、双曲问题、时间依赖的对流扩散问题及多孔介质中相容驱动问题等分别构建一类新的区域分解并行算法.从理论上分析了算法的收敛性,论证了在每一时间层上的误差收敛阶对于区域重叠度、空间网格步长、时间步长及迭代次数的依赖性.理论分析和数值算例都表明,算法具有高度的并行性,并且在每一时间层上只需迭代一次或两次就能达到收敛的最优阶.全文共分四章.第一章,对一般的二阶抛物型方程提出一类新的区域分解并行算法.首先,运用羊丹平教授提出的分裂正定混合元方法(SPDFME)思想,我们构造了抛物方程的全离散分裂正定混合元格式,此格式方程系数矩阵是对称正定的.其次,基于此混合元格式,结合徐进超教授提出的并行子空间校正算法,我们建立抛物问题的并行混合有限元算法Ⅰ(PMFE algorithmⅠ).分析了全离散分裂正定混合元格式及并行混合元算法Ⅰ的收敛性,并给出相应的误差估计.对于并行混合元算法Ⅰ,一些算例被给出.从这些数值结果中可以看出,在每一时间层上只需要迭代一次或两次就能达到理论最优阶,这正和理论分析的结果一致.此外,基于抛物问题的一般混合元格式,在本章最后一部分,我们还提出了抛物问题的另一并行算法:并行混合有限元算法Ⅱ(PMFEalgorithmⅡ).运用前面的一些理论分析结果,研究了此并行算法的收敛性并给出相应的误差估计.第二章,着重研究多孔介质中的相容驱动问题区域分解并行算法.我们知道,对于对于多孔介质中的相容驱动问题,羊丹平教授提出了分裂正定混合元方法.此方法中,方程的系数矩阵对称正定,并且压力方程与流函数方程分离.这样使得我们能够不依赖于压力方程而单独求解流函数和饱和度.本章算法的思想就是基于与压力无关的流函数方程和饱和度方程,运用第一章中抛物型方程的并行混合有限元算法Ⅰ的思想,建立一种新的并行混合有限元算法,从而并行地求解流函数及饱和度.研究了此算法的收敛性并给出了误差结果.从误差估计中我们能够看出在每一时间层上只需要迭代二次就能达到收敛的最优阶.在§2.1中介绍了问题的物理背景以及研究的目的和动机.在§2.2中我们给出多孔介质中的相容驱动问题的全离散分裂正定混合元格式,并形成一个并行混合有限元算法.在§2.3中我们给出用以证明并行算法收敛性定理的一些重要引理.在§2.4中,我们证明并行算法的收敛性定理.本章的一些结果已经发表在《山东大学学报》(理学版)上(见[58]).第三章,主要研究时间依赖的对流扩散方程的区域分解并行最小二乘算法.目前,已经有大量的文献是关于最小二乘有限元格式及它们在椭圆边值问题的应用,一些椭圆问题的对称理论和逼近解的收敛性理论被建立,见文献[62,63,64,65,66、67,68,69,72,74,76,77,78].最小二乘有限元方法也被扩展到时间依赖的问题,如[71,73,75,79,80,81].本章中,运用羊丹平教授在文献[79]中提出的时间依赖的对流扩散方程的最小二乘格式Ⅰ和格式Ⅲ,我们提出了两种并行最小二乘算法:并行最小二乘算法Ⅰ和并行最小二乘算法Ⅱ.算法基于重叠区域分解和子空间校正,通过引入单位分解函数,合理地分配重叠区域的校正量.算法在每个子域上分别进行残量校正,各子域之间可以并行计算.分别分析了并行最小二乘算法Ⅰ和并行最小二乘算法Ⅱ的收敛性,并给出相应的误差估计.本章的最后,给出了数值算例,对最小二乘格式与并行最小二乘算法进行了比较,分析了收敛率对离散参数及迭代次数的依赖性.本章的部分主要结果已经投递刊物(见[60]).第四章,研究了二阶双曲方程的区域分解并行混合有限元算法.我们知道,双曲方程描述了自然界中的波动现象,在物理、化学、生物等不同领域都有着非常重要的意义.对于二阶的双曲方程,已建立了大量的数值求解方法.对于双曲方程的并行算法,目前也有大量研究工作.Y.H.Wu,X.C.Cai和David E.Keyes研究了一阶双曲问题的加性Schwarz方法;田敏在其博士论文[46]中研究了二阶双曲方程的并行有限差分算法,论证了在每一时间层上的收敛性及对子区域重叠度、空间网格步长、时间步长及迭代次数的依赖性.本章我们研究的目的是,运用第一章提出的抛物方程的重叠区域并行混合元算法的思想,构建一种新的并行算法求解双曲方程.分析了此并行算法的收敛性并给出相应的误差估计.在§4.1中,我们陈述了本章的研究目的和动机.在§4.2中,运用羊丹平教授在[15]中提出的分裂正定混合元思想,我们给出双曲方程的一个分裂正定混合元格式,并依此为基础构造该问题并行混合元算法.在§4.3中,给出一些重要的引理,我们将用来分析双曲方程并行混合元算法的收敛性。在§4.4中,我们分析并行算法的收敛性,并给出相应的误差估计.本章的部分结果已经被《Numerical Methods for Partial Differential Equations》接受(见[59]).

论文目录

• 中文论文
• 中文摘要
• 英文摘要
• 第一章 抛物问题的并行混合有限元方法
• §1.1 引言
• §1.2 并行混合有限元算法Ⅰ
• §1.2.1 并行混合有限元算法Ⅰ的形成
• §1.2.2 预备知识
• §1.2.3 收敛性分析
• §1.2.4 数值算例
• §1.3 并行混合有限元算法Ⅱ
• §1.3.1 并行混合有限元算法Ⅱ的形成
• §1.3.2 收敛性分析
• 第二章 多孔介质中可压缩相容驱动问题的并行分裂正定混合元方法
• §2.1 引言
• §2.2 并行算法的形成
• §2.3 一些引理
• §2.4 收敛性分析
• 第三章 时间依赖的对流-扩散问题的并行最小二乘方法
• §3.1 引言
• §3.2 并行最小二乘算法的形成
• §3.3 一些引理
• §3.4 并行最小二乘算法Ⅰ的收敛性分析
• §3.5 并行最小二乘算法Ⅱ的收敛性分析
• §3.6 数值算例
• 第四章 二阶双曲方程的并行混合有限元方法
• §4.1 引言
• §4.2 并行算法的形成
• §4.3 一些重要引理
• §4.4 收敛性分析及误差估计
• 参考文献
• 致谢
• 攻读博士学位期间完成论文情况
• 作者简介
• 学位论文评阅及答辩情况表
• 英文论文
• Abstract（in English）
• Abstract（in chinese）
• 1 Parallel Mixed Finite Element Methods for Parabolic Problems
• 1.1 Introduction
• 1.2 Parallel Mixed Finite Element Algorithm Ⅰ
• 1.2.1 Formulation of Parallel Mixed Finite Element Algorithm Ⅰ
• 1.2.2 Preliminaries and Some Lemmas
• 1.2.3 Convergence Analysis
• 1.2.4 Numerical Experiments
• 1.3 Parallel Mixed Finite Element Algorithm Ⅱ
• 1.3.1 Formulation of Parallel Mixed Finite Element Algorithm Ⅱ
• 1.3.2 Convergence Analysis
• 2 Parallel Splitting Positive Definite Mixed Element Method for Compressible Miscible Displacement in Porous Media
• 2.1 Introduction
• 2.2 Formulation of Parallel Algorithm
• 2.3 Some Lemmas
• 2.4 Convergence Analysis
• 3 Parallel Least-Squares Finite Element Methods for Time-Dependent Convection-Diffusion System
• 3.1 Introduction
• 3.2 Formulations of Parallel Least-Squares Finite Element Algorithms
• 3.3 Some Lemmas
• 3.4 Convergence Analvsis of PLS Algorithm Ⅰ
• 3.5 Convergence Analysis of PLS Algorithm Ⅱ
• 3.6 Numerical Examples
• 4 Parallel Mixed Finite Element Method for Hyperbolic Equations
• 4.1 Introduction
• 4.2 Formulation of Parallel Mixed Element Algorithm
• 4.3 Some Lemmas
• 4.4 Convergence Analysis
• Bibliography
• Acknowledgement
• List of Publications
• Curriculum Vitae
• 学位论文评阅及答辩情况表