论文部分内容阅读
现实中的许多科学问题往往需要大规模计算,并且需要极高的精度.这就要求我们能够设计出新的更有效的算法来解决这些问题.随着并行计算机的出现,并行计算成为解决这类问题的一种相当重要的手段.同时随着科学技术和并行计算能力的提高,我们可以解决诸如约束条件为非线性偏微分方程组的优化问题和由障碍问题,自由边界问题等得到的互补问题.这种计算复杂性的上升趋势要求我们设计可扩展的并行数值算法和现代软件工程技术,以便于发展数字实验室.区域分解法是上世纪八十年代崛起的新算法.其思想是将计算区域分为若干子区域,将原问题的求解转化为相应子区域上子问题的求解.区域分解法是一类功能强大的算法,广泛应用于大规模稀疏的线性和非线性方程组.在众多不同的区域分解法中,我们主要侧重于一类Schwarz算法.本论文测试的线性Schwraz预处理条件子是建立在两类具有挑战性的问题上的：在计算流体力学中由边界控制的非定常不可压缩流问题和由障碍问题,自由边界问题等得到的互补问题.本文介绍了几类鲁棒的,可扩展的并行算法来解这两类复杂的问题,并且包括了以下三部分：首先,我们考虑了一类代数的乘性Schwarz迭代法用来解带H+-矩阵的线性互补问题.证明了由乘性Schwarz算法所产生的序列在没有任何限制初始点的情况下收敛于线性互补问题的唯一解.对于不同的重叠尺度,我们分析了算法的收敛率.当线性互补问题中的矩阵A是—M-矩阵且初始点在上解集时,算法所产生的序列是一个单调序列.数值试表明了乘性Schwarz迭代法的有效性.接下来,我们考虑了一类并行的区域分解法来解由障碍问题,自由边界问题等所产生的互补问题.对于此类问题,半光滑牛顿法是一个好的选择,但是这类方法对于大规模计算是不合适的,因为牛顿迭代次数对于网格尺寸是不可扩展的：即,随着网格的加细,非线性迭代次数以两倍的形式增长.因此我们考虑了一类并行两网格半光滑Newton-Krylov-Schwarz (NKS)算法来解这类互补问题.这类算法包含了非精确半光滑牛顿法,磨光的网格序列法和两水平的限制Schwarz预处理技术.从数值方面,我们的算法相对于牛顿迭代次数和线性迭代次数来说是可扩张的.此外,该方法对通常和障碍问题相关的不连续性问题也是不敏感的.最后,我们考虑了一类并行的Lagrange-Newton-Krylov-Schwarz (LNKSz)算法来解带时间项的二维的Navier-Stokes方程的优化问题.此算法是全隐格式的并且允许大的时间步长.在LNKSz算法中,我们首先得到Lagrangian函数和KKT条件,然后带线搜索的非精确牛顿法可以应用在KKT条件上.在每个牛顿步,KKT条件所对应的雅可比系统可以用Schwarz预处理的Krylov子空间方法来解.我们证实了LNKSz是一类有效的算法来解决这类难题.为了说明算法的可扩展性和鲁棒性,我们在不同雷诺数和时间步长的范围中计算了几个实际问题,并且在多达一千多个处理器且未知量的数目多于几百万的情况下测试了大规模计算的数值结果.