《并行算法》求取 ⇩

目录1

第一篇 绪论1

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

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

§1.1 并行计算机应用4

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

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

§2 并行计算机的发展19

§3 并行计算机模型25

§3.1　SISD计算机模型27

§3.2　MISD计算机模型28

§3.3　SIMD计算机模型29

§3.4　MIMD计算机模型45

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

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

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

§1.2 阶的表示65

§1.3 运行时间65

§1.4 并行度68

§1.5 加速比与效率70

§1.6 处理机台数77

§1.7 成本（Cost）78

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

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

§2.1 各种计算问题的分类83

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

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

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

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

§2.6 死锁104

§2.7 多处理机上任务调度105

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

§3.1 算法复杂性108

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

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

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

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

第二篇 数值并行算法121

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

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

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

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

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

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

§2 迭加问题并行计算157

§2.1 迭加问题一158

§2.2 迭加问题二164

§3 多项式并行计算166

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

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

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

§4.1 对角线消去法183

§4.2 Sameh-Brent算法186

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

§1 矩阵乘法199

§1.1 内积算法200

§1.2 外积算法200

§1.3 ijk算法202

§1.4 对角线算法206

§1.5 Strassen算法208

§1.6 Winograd算法210

§2 矩阵求逆211

§2.1 一般稠密矩阵求逆212

§2.2 三对角矩阵求逆215

§2.3 Toeplitz矩阵求逆219

§3 多项式乘法与除法229

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

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

§4 多项式求值232

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

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

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

§6 多项式插值241

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

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

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

§1.1 行列扫描法249

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

§1.3 乘积法253

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

§2.1 LU分解与Gauss消去法255

§2.2 正交三角分解法261

§2.3 蝴蝶分解算法267

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

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

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

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

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

§4 Toeplitz方程组的并行解法291

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

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

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

§5.1 Jacobi迭代法304

§5.2 Gauss-Seidel迭代法307

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

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

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

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

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

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

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

§2.1 Jacobi方法341

§2.2 Householder算法347

§2.3 Givens算法349

§2.4 QIF迭代算法354

§2.5 初等变换法357

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

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

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

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

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

§1.1 常用FFT算法370

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

§2 FFT的并行计算399

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

§3.1 多项式变换410

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

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

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

§4.1 维DFT的行列算法427

§4.2 维DFT的FPT算法433

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

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

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

§5.3 DCT的并行计算463

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

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

§2 一维卷积的并行计算476

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

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

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

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

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

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

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

§3.3 多维卷积的嵌套算法505

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

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

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

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

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

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

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

§1 块隐含一步法528

§1.1 二点块隐含一步法529

§1.2 四点块隐含一步法530

§1.3 八点块隐含一步法531

§1.4 块隐含一步法收敛性533

§2 Runge-Kutta法的并行计算534

§2.1 并行三阶Runge-Kutta法535

§2.2 并行四阶Runge-Kutta法537

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

§3 迭代法541

§4.1 交替组显式法543

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

§4.2 并行打靶法550

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

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

§1.1 左右偏心格式554

§1.2 交替方向组显式格式555

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

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

§3 有限元法的并行计算568

§3.1 有限元法569

§3.2 有限元法的并行计算571

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

§4 区域分裂法575

§4.1 重叠区域分裂法576

§4.2 不重叠区域分裂法584

§5.1 MG方法的基本原理592

§5 多重网格法592

§5.2 二重网格法593

§5.3 多重网格法597

§5.4 完全多重网格法599

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

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

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

§6.2 FFT法605

§6.3 块循环约化法（BCR）606

§6.4 FACR（l）法615

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

§1 一维搜索619

§1.1 Bolzano方法619

§1.2 Arriel序列法620

§1.3 黄金分割批寻找法622

§1.4 偶数分批法623

§2 共轭方向法625

§2.1 共轭Gram-Schmidt方法626

§2.2 Sloboda算法627

§2.3 Chazan-Miranker方法629

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

§3 多维搜索632

§4 并行Jacobson-Oksman算法636

§5 并行拟Newton法639

§6 约束优化的分解方法641

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

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

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

§1 素性测试649

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

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

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

§1.4 确定性素性测试法662

§2 大整数因子分解663

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

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

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

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

第三篇　非数值并行算法693

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

§1 基本概念695

§1.1　分类问题及其复杂性695

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

§2 计数分类698

§2.1 计数分类的分类网格699

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

§3 交换分类704

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

§3.2　合并-分裂分类算法706

§4 合并分类709

§4.1　奇偶合并分类709

§4.2　双调合并分类712

§4.3　流水线上的合并分类716

§5　外部分类720

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

§5.2　流水线上的外部分类724

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

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

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

§1.2 Stone并行分类算法732

§1.3 改进的Stone算法736

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

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

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

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

§3.1 最小析取技术745

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

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

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

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

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

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

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

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

§6.1 异步并行的计数分类761

§6.2 异步并行的快速分类763

参考文献767