目录

第一篇 绪论

第一章 并行计算机模型与并行算法

§1 并行计算机与并行算法的研究

§1.1 并行计算机应用

§1.2 并行处理与并行算法的研究

§1.3 并行算法研究的方法与对象

§2 并行计算机的发展

§3 并行计算机模型

§3.1　SISD计算机模型

§3.2　MISD计算机模型

§3.3　SIMD计算机模型

§3.4　MIMD计算机模型

§1.1 并行算法的定义与分类

§1 并行算法度量的若干基本概念

第二章 并行算法的设计与分析

§1.2 阶的表示

§1.3 运行时间

§1.4 并行度

§1.5 加速比与效率

§1.6 处理机台数

§1.7 成本（Cost）

§1.8 并行算法加速比的进一步分析

§2 并行算法的设计与MIMD算法分类

§2.1 各种计算问题的分类

§2.2 并行算法设计应注意的几个问题

§2.3 阵列处理机并行算法的设计

§2.4 MIMD计算机上并行算法设计

§2.5 MIMD计算机上进程通信和同步化

§2.6 死锁

§2.7 多处理机上任务调度

§3 算法复杂性及其实例剖析

§3.1 算法复杂性

§3.2 MIMD计算机上算法复杂性分析

§4 并行算法性能评价的n1/2方法和s1/2方法

§4.1 SIMD计算机算法分析的n1/2方法

§4.2 MIMD计算机算法分析的s1/2方法

第二篇 数值并行算法

第三章 相关问题的并行算法

§1 递归问题的并行计算及效能分析

§1.1 一阶递归问题的并行计算

§1.2 一阶递归问题三种并行计算方法效能分析

§1.3 多阶递归问题并行计算

§1.4 一类递归函数并行计算

§2 迭加问题并行计算

§2.1 迭加问题一

§2.2 迭加问题二

§3 多项式并行计算

§3.1 多项式求值的几种并行计算

§3.2 多项式并行计算的复杂性

§4 三角形方程组并行计算

§4.1 对角线消去法

§4.2 Sameh-Brent算法

第四章 矩阵与多项式的并行算法

§1 矩阵乘法

§1.1 内积算法

§1.2 外积算法

§1.3 ijk算法

§1.4 对角线算法

§1.5 Strassen算法

§1.6 Winograd算法

§2 矩阵求逆

§2.1 一般稠密矩阵求逆

§2.2 三对角矩阵求逆

§2.3 Toeplitz矩阵求逆

§3 多项式乘法与除法

§3.1 快速多项式乘法及其并行计算

§3.2 快速多项式除法及其并行计算

§4 多项式求值

§5 多项式最大公因式与中国剩余定理的并行计算

§5.1 多项式最大公因式的并行计算

§5.2 中国剩余定理及其并行计算

§6 多项式插值

§7 多项式零点的并行计算

第五章 线性方程组并行求解

§1 三角形方程组的并行求解

§1.1 行列扫描法

§1.2 多重右端项的方程组求解

§1.3 乘积法

§2 稠密方程组的并行求解

§2.1 LU分解与Gauss消去法

§2.2 正交三角分解法

§2.3 蝴蝶分解算法

§2.4 对称方程组的并行求解

§3 三对角方程组的并行求解

§3.1 三对角线性方程组的几种并行算法

§3.2 块三对角方程组的并行求解

§3.3 拟块三对角方程组的并行求解

§4 Toeplitz方程组的并行解法

§4.1 对称稠密Toeplitz方程组的并行解法

§4.2 三对角Toeplitz方程组的并行解法

§5 基本迭代法的并行计算

§5.1 Jacobi迭代法

§5.2 Gauss-Seidel迭代法

第六章 矩阵特征值的并行算法

§1 几种特殊矩阵特征值的计算

§1.1 对称三对角矩阵特征值带原点位移的并行QR算法

§1.2 对称三对角矩阵特征值的分而治之算法

§1.3 Hessenberg矩阵特征值的并行计算

§1.4 Toeplitz矩阵特征值的并行计算

§2 一般矩阵特征值的并行计算

§2.1 Jacobi方法

§2.2 Householder算法

§2.3 Givens算法

§2.4 QIF迭代算法

§2.5 初等变换法

§3.1 A、B对称且B正定时广义特征值的并行计算

§3 矩阵广义特征值的并行计算

§3.2 一般实矩阵广义特征值的并行计算

第七章 离散变换及其并行算法

§1 离散富里叶变换的快速算法

§1.1 常用FFT算法

§1.2 递归割圆分解算法（RCFA）和分裂基算法（SRFFT）

§2 FFT的并行计算

§3 快速多项式变换的并行计算

§3.1 多项式变换

§3.2 快速多项式变换及其并行计算

§3.3 多项式变换的MIMD并行算法

§4 维离散富里叶变换的并行计算

§4.1 维DFT的行列算法

§4.2 维DFT的FPT算法

§5 离散余弦变换与正弦变换的并行计算

§5.1 各类DCT和DST及其相互关系

§5.2 DCT-Ⅱ及DCT-Ⅲ的快速算法

§5.3 DCT的并行计算

第八章 离散卷积和滤波的并行算法

§1 离散卷积及其等价形式

§2 一维卷积的并行计算

§2.1 用离散余弦和正弦变换计算一维卷积

§2.2 用多项式变换计算一维卷积

§2.3 一维卷积用多维卷积计算

§2.4 一维卷积的并行计算复杂性

§3 二维及多维卷积的并行算法

§3.1 用多道并行FFT计算多维卷积

§3.2 用多项式变换计算二维及多维卷积

§3.3 多维卷积的嵌套算法

§3.4 多维卷积的并行计算复杂性

§4 二进卷积及其并行算法

§5.1 一维FIR滤波的并行计算

§5 FIR及IIR滤波的并行计算

§5.2 一维IIR滤波的并行计算

§5.3 二维FIR滤波的并行计算

第九章 常微分方程的并行解法

§1 块隐含一步法

§1.1 二点块隐含一步法

§1.2 四点块隐含一步法

§1.3 八点块隐含一步法

§1.4 块隐含一步法收敛性

§2 Runge-Kutta法的并行计算

§2.1 并行三阶Runge-Kutta法

§2.2 并行四阶Runge-Kutta法

§2.3 隐式Runge-Kutta法的并行计算

§3 迭代法

§4.1 交替组显式法

§4 两点边值问题的并行计算

§4.2 并行打靶法

第十章 偏微分方程的并行求解

§1 适合并行计算的交替方向组显式格式

§1.1 左右偏心格式

§1.2 交替方向组显式格式

§1.3 组显式格式的并行计算

§2 差分方程迭代法的并行计算

§3 有限元法的并行计算

§3.1 有限元法

§3.2 有限元法的并行计算

§3.3 有限元方程的并行计算

§4 区域分裂法

§4.1 重叠区域分裂法

§4.2 不重叠区域分裂法

§5.1 MG方法的基本原理

§5 多重网格法

§5.2 二重网格法

§5.3 多重网格法

§5.4 完全多重网格法

§5.5 多重网格法在Hypercube上的并行实现

§6 Poisson方程的快速直接解法及其并行计算

§6.1 Poisson方程的五点差分格式的矩阵表示

§6.2 FFT法

§6.3 块循环约化法（BCR）

§6.4 FACR（l）法

第十一章　最优化问题的并行算法

§1 一维搜索

§1.1 Bolzano方法

§1.2 Arriel序列法

§1.3 黄金分割批寻找法

§1.4 偶数分批法

§2 共轭方向法

§2.1 共轭Gram-Schmidt方法

§2.2 Sloboda算法

§2.3 Chazan-Miranker方法

§2.4 一般无约束优化问题的共轭方向法

§3 多维搜索

§4 并行Jacobson-Oksman算法

§5 并行拟Newton法

§6 约束优化的分解方法

§6.1 线性规划的Dantzig-Wolfte分解

§6.2 非线性规划的分解方法

第十二章 素性测试和大整数分解

§1 素性测试

§1.1 伪素数及费马素性测试法

§1.2 并行Solovary-Strassen素性测试法

§1.3 并行Miller-Rabin素性测试法

§1.4 确定性素性测试法

§2 大整数因子分解

§2.1 并行费马分解法及分解基算法

§2.2 并行连分式因子分解法

§2.3 并行二次筛因子分解法

§2.4 椭圆曲线因子分解法及其并行处理

第三篇　非数值并行算法

第十三章　并行分类基本技术

§1 基本概念

§1.1　分类问题及其复杂性

§1.2　并行算法的描述及评价

§2 计数分类

§2.1 计数分类的分类网格

§2.2　线性阵列上的计数分类

§3 交换分类

§3.1　线性阵列上的奇偶交换分类算法

§3.2　合并-分裂分类算法

§4 合并分类

§4.1　奇偶合并分类

§4.2　双调合并分类

§4.3　流水线上的合并分类

§5　外部分类

§5.1　树型结构上的外部分类算法

§5.2　流水线上的外部分类

第十四章　典型结构上的并行分类

§1 完全洗牌连接的SIMD模型上的并行分类

§1.1　完全洗牌连接的SIMD模型上的洗牌特性

§1.2 Stone并行分类算法

§1.3 改进的Stone算法

§2.1 格网连接的SIMD模型的机器特性

§2 格网连接的SIMD模型上的并行分类

§2.2 格网连接的SIMD模型上的双调分类

§3 树型连接的SIMD模型上的并行分类

§3.1 最小析取技术

§3.2 逐层直接合并的并行分类算法

§4 立方体连接的SIMD模型上的并行分类

§4.1 用于分类的立方体连接的SIMD模型

§4.2 立方体连接的SIMD模型上的计数分类

§5 共享存储器的SIMD模型上的并行分类

§5.1 共享存储器的SIMD模型的机器特性

§5.2 共享存储器的SIMD模型上的快速分类

§6 MIMD计算机上的异步并行分类

§6.1 异步并行的计数分类

§6.2 异步并行的快速分类

参考文献