并行算法PDF电子书下载

目录 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