第一章 并行计算环境 1
1.1 引言 1
1.2 并行计算机的分类 3
1.2.1 SISD型计算机 3
1.2.2 SIMD型并行机 4
1.2.3 共享存储MIMD并行多处理机 6
1.2.4 分布存储MIMD并行多处理机 7
1.2.5 分布共享存储MIMD并行机 9
1.3 并行计算机的发展 10
1.3.1 应用需求 10
1.3.2 发展概况 12
1.4 并行程序设计 19
1.4.1 向量程序设计 19
1.4.2 共享存储并行程序设计 20
1.4.3 数据并行程序设计 22
1.4.4 消息传递并行程序设计 23
第二章 并行算法设计与分析 26
2.1 并行算法 26
2.1.1 并行算法的概念、分类和术语 26
2.1.2 发展数值并行算法 31
2.2 并行与向量计算的基本概念 33
2.2.1 并行算法的复杂性 33
2.2.2 并行度 34
2.2.3 加速比与相容性 36
2.3 并行算法设计的基础与主要策略 39
2.3.1 计算无关性 39
2.3.2 分而治之 41
2.4 线性递推问题并行计算 43
2.4.1 倍增法 43
2.4.2 循环加倍法 47
2.5 并行矩阵-向量乘法 50
2.6 矩阵乘积并行计算 53
2.6.1 内积、中积、外积算法 53
2.6.2 Strassen算法 57
2.6.3 Winograd算法 60
2.7 并行矩阵求逆 62
2.7.1 一般稠密矩阵求逆的消去法 62
2.7.2 分块递推法 63
第三章 线性方程组的并行直接解法 66
3.1 三角形方程组的并行求解 66
3.2 稠密线性方程组的LU分解法 70
3.2.1 Gauss消去法 70
3.2.2 列主元消去法 74
3.2.3 LU分解的矩阵向量形式 75
3.2.4 LU分解矩阵与多重右端项 77
3.3 三对角方程组的并行直接解法 79
3.3.1 Stone算法 79
3.3.2 循环约化法 82
3.3.3 分裂法 84
3.3.4 分段追赶并行算法 88
3.4 实对称方程组的Cholesky分解法 90
3.4.1 对称正定方程组的Cholesky分解法 90
3.4.2 ijk型向量算法 91
3.4.3 Cholesky分解的并行实现 91
3.5 正交约化法 93
3.5.1 Givens约化法 93
3.5.2 Givens约化法的向量与并行实现 95
3.5.3 Householder约化法 100
3.5.4 Householder约化法的向量与并行实现 103
4.1.1 迭代法的一般概念 107
4.1 基本迭代法 107
第四章 线性方程组的并行迭代解法 107
4.1.2 Jacobi迭代法 111
4.1.3 Gauss-Seidel迭代法与SOR迭代法 113
4.2 Gauss-Seidel法与SOR法并行与向量计算 117
4.2.1 红-黑排序 117
4.2.2 多色排序 126
4.2.3 多色LSOR法和SSOR法 130
4.3 ADI方法与半迭代法 134
4.3.1 ADI方法 134
4.3.2 半迭代法 136
4.4 预处理共轭梯度法 141
4.4.1 共轭梯度法及其并行与向量计算 141
4.4.2 预处理共轭梯度法及其并行与向量计算 145
4.5.1 多分裂迭代法的概念 155
4.5 多分裂迭代法 155
4.5.2 收敛性定理与收敛速度的估计 156
4.5.3 松驰型多分裂迭代法 159
4.5.4 二级多分裂迭代法 161
4.5.5 数值算例 166
4.6 异步迭代法 168
4.6.1 CR方法和BCR方法 169
4.6.2 一般异步迭代法 172
4.6.3 异步块迭代法 174
4.6.4 多分裂迭代法的混乱模式 176
4.6.5 异步块二级多分裂迭代法 179
第五章 有限差分并行计算 183
5.1 有限差分方法基本知识 183
5.2 抛物型方程的分组显式方法 188
5.2.1 引言 188
5.2.2 Saul yev非对称格式 189
5.2.3 分组显式(GE)方法 192
5.2.4 交替分组显式(AGE)方法 197
5.2.5 交替三点组显式(AGE-3)方法 199
5.3 抛物型方程的显-隐交替法 205
5.3.1 交替分段显-隐式(ASE-I)方法 205
5.3.2 ASE-I方法的一种特殊情形 210
5.3.3 交替分段Crank-Nicolson方法 212
5.3.4 变系数和间断系数方程新解法 216
5.4 双曲型方程的一个分组显式格式 223
5.5 对流扩散方程的并行解法 227
5.5.1 引言 227
5.5.2 交替分组显式方法 228
5.5.3 交替分段显-隐式方法 234
5.6 二维问题 240
5.6.1 引言 240
5.6.2 AGE方法 242
5.6.3 ABE-I方法 257
5.6.4 块ADI方法 260
5.6.5 交替差分块方法及其差分图 269
第六章 有限元法及区域分裂法 276
6.1 有限元方法的基本知识 276
6.1.1 区域的剖分 276
6.1.2 单元形状函数的确定 278
6.1.3 有限元方程的形成 282
6.2 有限元方法并行实现基本问题 287
6.3 区域分裂法 290
6.3.1 区域分裂法概述 290
6.3.2 Schwarz交替法 294
6.3.3 Schwarz型混乱松驰法 298
6.3.4 区域分裂法简例 304
参考文献 315