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

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

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

1.1 中小型计算机的模型2

1.2 大型计算机的模型3

1.3 并行处理机的模型5

§2 计算复杂性12

2.1 算法的计算复杂性12

2.2 随机访问机14

1.4 Strassen算法16

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.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 快速直接法161

第四章 特征值问题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