《电子计算机 并行算法的设计与分析》

第一章并行算法设计基础1

1 各类计算机的主要特征1

1.1 中小型计算机的模型2

1.2 大型计算机的模型3

1.3 并行处理机的模型5

2 计算复杂性12

2.1 算法的计算复杂性12

2.2 随机访问机14

2.3 RAM 程序的计算复杂性17

2.4 高级语言程序的计算复杂性20

2.5 算法的设计和分析21

3 浮点运算的舍入误差分析22

3.1 向后误差分析和算法的数值稳定性23

3.2 浮点四则运算的误差分析24

3.3 常用浮点运算的误差分析25

4 并行算法的计算复杂性27

4.1 独立运算和向量型运算28

4.2 并行算法的评价标准29

4.3 分析树及 n 个数的求和算法32

4.4 并行算法的分类与设计35

第二章基本算法41

1 矩阵乘法41

1.1 环和域的基本性质41

1.2 内积算法43

1.3 外积算法45

1.4 Strassen 算法46

1.5 Winograd 算法47

1.6 布尔矩阵的乘法50

2 递推计算53

2.1 递推倍增算法54

2.2 分段并行法60

2.3 三角形方程组的并行求解66

3 多项式的并行计算81

3.1 向量机上多项式的几种并行算法82

3.2 多项式并行算法的复杂性85

4 算术表达式的并行计算87

4.1 无除法运算的算术表达式88

4.2 一般算术表达式94

4.3 处理机台数固定的情形99

4.4 数值稳定性101

5 快速傅里叶变换105

5.1 串行的快速傅里叶变换105

5.2 快速傅里叶变换的并行处理112

第三章线性代数方程组116

1 等价性定理116

2 稠密方程组120

2.1 高斯消去法121

2.2 正交三角分解方法122

2.3 迭代法126

3.1 基于 LDU 分解的并行算法130

3 三对角方程组130

3.2 加速并行高斯消去法132

3.3 解一般三对角方程组的并行算法142

4 块三对角方程组147

4.1 循环奇偶约化算法148

4.2 快速直接法155

第四章特征值问题161

1 耶可比方法161

2.1 算法165

2 对称三对角矩阵的并行 QR 算法165

2.2 时间和处理机台数的界169

2.3 误差分析176

2.4 数值经验178

3 流水线计算机上的 QR 算法和 Hyman 方法179

3.1 QR 迭代的时间估计180

3.2 基于用 Hyman 方法迭代的时间估计183

3.3 两种方法的比较185