电子计算器并行算法的设计与分析PDF电子书下载

第一章 并行算法设计基础 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