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