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