块三对角方程组的可扩展并行算法及其应用研究

摘要

偏微分方程的数值求解是科学与工程计算的重要任务，块三对角线性方程组是偏微分方程离散格式的主要形式之一。本文系统地研究了块三对角线性方程组直接求解方法的可扩展并行算法及其应用，主要工作如下： 1．将三对角线性方程组的RCD(Recursive Doubling)方法，推广到了块三对角线性方程组，得到BRCD(Block Recursive Doubling)方法。该方法将块LU分解的时序性较强的计算转化成矩阵的乘积计算，有利于设计并行算法；同时给出了块LU分解方法、BRCD方法和SBP(Sequential Block Prefix)方法的反向与双向计算公式，在计算中使用不同方向的计算公式可以减少计算量；给出了一个数值稳定的块三对角线性方程组快速BOER(Block Odd-Even Reduction)求解公式，提高了计算精度和速度； 2．对于Larfiba等提出的三对角线性方程组的重叠分割并行方法，一方面将它推广到了块三对角线性方程组，该方法对于强块对角占优块三对角线性方程组的求解有较高的并行效率；另一方面将它与非重叠分割并行方法的缩减方程组结合，提出了块三对角线性方程组的有通信重叠分割并行方法，对于弱块对角占优的块三对角线性方程组，该方法可以用少量通信代替过量的计算，保证了精度和计算效率； 3．对严格块对角占优块三对角线性方程组的两类缩减方程组，提出了近似求解方法和相应的并行算法，该方法的通信次数是可调整的，可以通过它的调整来控制精度； 4．对严格块对角占优的块三对角线性方程组提出了多个可扩展的重叠与非重叠分割并行算法(统称PBDDA算法)，其中基于块LU分解的算法统称PBDDA-LU算法、基于BOER的算法统称PBDDA-OE算法。给出了两种通信模式，其特点是：仅使用局部通信；通信复杂度可调整；每次通信都是具有一定间隔的相邻处理器之间的单向数据传递。给出了相对误差与三个可调整的指标k<,0>(通信复杂度指标)、q+?(子问题规模指标)和p(处理器数量即算法并行度指标)的关系。PBDDA-LU算法是对PDD方法的推广，在推广中使用了反向块LU分解，改进了回代方法，比直接使用PDD方法求解块三对角线性方程组减少了将近30％的计算量； 5．提出了一类Topelitz块三对角线性方程组的PBDDA-OE算法公式；使用这个公式进行高维Poisson方程第一边值问题的数值求解；研究了PBDDA-OE算法的性能，提出了保证精度和并行效率的分治策略； 6．利用以上Topelitz块三对角线性方程组的PBDDA-OE算法公式进行高维抛物型方程初始边值问题的数值求解，研究了PBDDA-OE算法的性能，提出了保证精度和并行效率的分治策略； 7．提出了另一类Topelitz块三对角线性方程组的PBDDA-OE算法公式；使用这个公式进行高维双曲型方程初始边值问题的数值求解；给出了控制精度与并行效率的分治策略。

目录

文摘

英文文摘

声明

第一章绪论

1.1 本文研究的目的和意义

1.2 块三对角线性方程组并行算法的研究概况

1.3 块三对角线性方程组并行算法研究存在的问题

1.4 本文的研究内容和创新性成果

第二章块三对角线性方程组的基本求解方法

2.1 引言

2.2 块LU分解法的公式

2.3 块递推耦合方法的公式

2.4 OER方法的公式

2.5 SBP方法的公式

2.6 本章小结

第三章块三对角线性方程组的分割并行方法

3.1 引言

3.2 块三对角线性方程组分割并行方法的基本思想和算法性能评价方法

3.3 基于块LU分解方法的分割并行方法

3.4 基于BOER方法的分割并行方法

3.5 本章小结

第四章缩减方程组的PBOERA求解方法

4.1 引言

4.2 缩减方程组的PBOERA求解方法

4.3 缩减方程组的PBOERA算法描述

4.4 缩减方程组PBOERA算法的精度分析

4.5 本章小结

第五章块三对角方程组的可扩展PBDDA算法

5.1 引言

5.2 块三对角方程组的PBDDA算法

5.3 PBDDA算法的精度分析

5.4 PBDDA算法的通信模式

5.5 本章小结

第六章椭圆型方程边值问题的并行求解

6.1 引言

6.2 一类Toeplitz块三对角方程组PBDDA-OE求解方法

6.3 矩阵的特殊运算与性质

6.4 二维Poisson方程第一边值问题的并行求解

6.5 三维Poisson方程第一边值问题的并行求解

6.6 Poisson方程第一边值问题PBDDA-OE算法的性能分析

6.7 Poisson方程第一边值问题PBDDA-OE算法的分治策略

6.8 Poisson方程第一边值问题PBDDA-OE算法的可扩展性分析

6.9 数值实验结果与分析

6.10 本章小结

第七章抛物型方程初始边值问题的并行求解

7.1 引言

7.2 二维抛物型方程初始边值问题的并行求解

7.3 三维抛物型方程初始边值问题的并行求解

7.4 抛物型方程初始边值问题PBDDA-OE算法的性能分析

7.5 抛物型方程初始边值问题PBDDA-OE算法的分治策略

7.6 抛物型方程初始边值问题PBDDA-OE算法的可扩展性分析

7.7 数值实验结果与分析

7.8 本章小结

第八章双曲型方程初始边值问题的并行求解

8.1 引言

8.2 一类Toeplitz块三对角方程组PBDDA-OE求解方法

8.3 二维双曲型方程初始边值问题的并行求解

8.4 三维双曲型方程初始边值问题的并行求解

8.5 双曲型方程初始边值问题PBDDA-OE算法的分治策略

8.6 数值实验结果与分析

8.7 本章小结

第九章结论与展望

9.1 结论

9.2 展望

参考文献

作者在攻读博士学位期间公开发表的论文

致 谢