并行算法是计算机科学的一个重要分支,本书分别从基础理论、基础应用和实际应用等方面简明扼要地介绍了并行算法。基础理论部分主要介绍并行计算平台、并行算法概论、并行程序开发环境等；基础应用部分包含矩阵运算、快速傅里叶变换、卷积运算、数字滤波、离散余弦变换、哈达玛变换、2D离散小波变换、数字图像处理等方面的并行算法设计、分析与测试；实际应用部分主要介绍并行算法在电磁散射中的应用和无线电波中的应用。
本书结合了作者参加“九五”期间的一项国家重点科研项目的成果，着重介绍数字信号处理中常用算法的并行处理；注重理论和实验相结合，大部分内容都有相应的实验数据和结果作为依据，极具实用价值。本书可作为计算机及相关专业的本科生和研究生的教材，也可供从事计算机科学研究与教学的人员参考。
无
最近几年，人们学习、设计和分析并行算法的兴趣日渐浓厚。这部分是由于用新技术制造的计算机使得运算成本比较合理，主要还是由于对信息处理能力的需求日益复杂。本书用四部分讲解并行算法的设计：第一部分给出并行算法设计的基础概念。其中对流水线、多处理、分时和共享存储器模型进行重点介绍。由于数据结构是并行算法设计很重要的组成部分，本书专门用一章进行介绍。基于信息处理的重要性，在本书中重点强调图模型算法。对并行算法设计中重要的环境则给出大量的例子进行解释。
本书第二部分介绍图理论问题常用的并行算法。对各种图问题进行研究，并给出相应的并行算法。专门用一章对弦图进行讲解，其中主要介绍弦图判别算法和一些优化问题算法。第三部分介绍对数组进行处理的算法，并用两章对排序、搜索与合并算法进行介绍。
第四部分对数值计算的并行算法进行介绍。其中用一章介绍代数方程并行算法。详细给出了微分、积分和微分方程（包括偏微分方程）的相关算法。另外还对内插值和外插值并行算法进行了介绍。
本书的显著特色是：
●用详细的例子一步一步讲解并行算法的设计；
●详尽的并行算法分析与实现；
●用大量的实例对每一个概念进行解释；
●每一章都在最后给出了参考文献。
本书是我们两位共同合作的结果，对本书内容负有同等责任。我们欢迎并感谢读者提出评价和意见。
C. Xavier
S.S. Iyengar
(印)C.Xavier,(美)S.S.lyengar：C.Xavier: C. Xavier博士曾获得数学专业理科硕士和哲学硕士学位，以及计算机科学专业的博士学位。他的博士论文是关于并行算法设计的。目前任教于印度Tirunelveli的圣Xavier学院（私立）计算机科学系。他在国际期刊和会议录上发表了多篇并行算法方面的研究论文，并出版了十多部计算机科学教材。印度的新时代国际出版公司（前Wiley东方公司）出版了其中的两本书：《FORTRAN 77 and Numerical Methods》和《Introduction to Computers and BASIC Programming》。同时，该出版公司即将出版另外一本书《C Language and Numerical Methods》。Xavier博士是印度计算机协会的高级终身会员。他是印度大学拨款委员会和印度科学技术部资助的多个项目的首席研究员，曾任1996年8月在印度Tirunelveli举行的关于数学建模和计算机虚拟现实的全国研讨会论文集的主编。他是那次研讨会的联合召集人之一。
S.S.lyengar: S.S.Iyengar 博士是美国路易斯安那州立大学计算机科学系的教授和系主任。自从1970年和1974年在印度理工大学分别获得硕士和博士学位后，他主要从事高性能算法和数据结构的研究工作，并在路易斯安那州立大学指导了超过27篇博士论文。曾担任过海军研究局（the Office of Naval Research）、国家航空航天管理局(NASA)、国家科学基金会（NSF）、加州理工学院喷气推进实验室、海军部—NORDA、美国能源部、LEQFS董事会和美国陆军部的研究员。他在高性能并行与分布式算法、图像处理和模式识别数据结构、自动导航及分布式传感器网络等领域出版了多本专著（由Prentice-Hall、CRC、IEEE计算机协会等出版社出版），并发表了250余篇研究论文。他还是喷气推进实验室、橡树岭国家实验室和印度科学院的客座教授。 Iyengar博士是《Neuro Computing of Complex Systems》丛书的编辑和《Journal of Computer Science and Information》的编辑。他还曾担任《IEEE Transactions on Knowledge and Data Engineering》、《IEEE Transcations and SMC》、《IEEE Transcations on Software Engineering》、《Journal of Theoretical Computer Science》、《Journal of Computer and Electrical Engineering》和《Journal of the Franklin Institute》等学术刊物的特邀编辑。 Iyengar博士还是IEEE的高级成员和IEEE计算机协会杰出访问者（1995～1998年）。另外，他从1985年就担任ACM全国讲师，并且是纽约科学院院士。曾担任多个全国和国际会议的程序委员会主席。在医学信息学领域，他是久负盛名的NIH-NLM评审委员会的成员。 1997年，Iyengar博士由于在图像处理数据结构和算法以及传感器融合问题上的杰出贡献而获得著名的IEEE技术成就奖。 1996年，Iyengar博士由于其出色的研究工作获得路易斯安那州立大学杰出教员奖和路易斯安那州立大学老虎运动（Tiger Athletic）基金教学奖。他还是一些工业机构和政府组织（如JPL、NASA等）的顾问。
张云泉 陈英：张云泉: 男，1995年获北京理工大学计算机科学技术系计算机应用专业工学学士学位；2000年获中科院软件所计算机软件与理论专业工学博士学位（硕、博连读）。现为中科院软件所并行计算实验室副研究员，中科院计算机科学开放重点实验室兼职副研究员，中科院软件所并行计算实验室副主任，中国软件行业协会数学软件分会秘书长。主要研究兴趣是：高性能并行计算特别是大规模并行数值软件包的设计与性能优化，性能建模与评价，并行计算模型，并行数据挖掘等。曾获得2000年度中科院院长奖学金优秀奖；2000年度国家科技进步奖二等奖。
陈英: 女，分别于1992年和1995年获南京师范大学学士学位和计算数学专业硕士学位。2001年于中科院数学与系统科学研究院获计算数学专业博士学位。主要研究兴趣是：数值分析、数值计算方法、并行计算及其应用等。目前，她是中科院计算所智能中心助理研究员。
近年来，随着社会众多行业信息化带来的对计算机信息处理能力和计算能力需求的不断提高，以及高性能计算机特别是高性能机群系统的普及和发展，并行计算机越来越多地开始被广大普通计算机专业人员以及其他专业的人员使用。然而，仅仅有并行计算机的硬件平台是不够的，还需要有配套的能充分发挥机器性能的并行计算应用软件。广大并行计算机用户和相关专业的学生迫切需要了解并行算法设计和分析的基础知识。我们翻译此书的目的是推动高性能计算在中国的进一步普及和发展，尤其是在高等院校中的普及和发展。
本书的两位作者C. Xavier 博士和S.S. Iyengar博士都是多年从事并行算法设计研究的资深教授，有多年的教学经验，并发表了大量的学术论文，出版了多部学术专著。其中Iyengar 博士是IEEE的高级成员和IEEE计算机协会杰出访问者（1995～1998年），由于其对图像处理数据结构和算法以及传感器融合（sensor fusing）问题的杰出贡献而于1997年获得著名的IEEE技术成就奖。
本书分四个部分介绍共享存储器计算模型PRAM下的并行算法设计，第一部分介绍并行计算、并行计算机和并行算法设计的基本概念，并行计算机分类、共享存储器并行计算模型、并行算法设计中的数据结构和并行算法常用设计环境，以及几个简单的并行算法；第二部分首先介绍图的基本概念，随后介绍树算法、图算法和弦图的NC算法，以及相关的并行算法；第三部分介绍搜索与合并、排序等数组处理并行算法；第四部分介绍有关数值计算的并行算法，包括线性代数方程组求解并行算法，以及微分、积分、插值和偏微分方程求解的并行算法。
由于时间仓促，再加上有些专业术语目前国内没有统一的译法，故翻译中的错误或不妥之处在所难免，恳请广大读者不吝指正。
张云泉
中科院软件所并行计算实验室
2003年8月12日
出版者的话
专家指导委员会
译者序
前言
致谢
作者简介
第一部分 并行计算基础
第0章 引言 1
0.1 计算机简介 1
0.2 并行计算机 5
0.3 并行处理的概念 6
0.4 高性能计算机 8
0.5 本书的结构和内容 9
参考文献 10
第1章 并行计算要素 11
1.1 并行的层次 11
1.2 并行计算机分类 12
1.2.1 Flynn分类 12
1.2.2 Erlangen分类（Handler分类） 14
1.2.3 Giloi分类 15
1.2.4 Hwang-Brigg分类 15
1.2.5 Duncan分类 15
1.3 并行计算模型 18
1.3.1 二叉树模型 18
1.3.2 网络模型 20
1.3.3 超立方体（k-立方体） 21
1.3.4 网格网络 26
1.3.5 金字塔网络 26
1.3.6 星形图 27
1.4 PRAM模型 28
1.5 一些简单算法 32
1.6 并行算法的性能 34
1.7 小结 37
参考文献 37
习题 38
第2章 并行计算数据结构 40
2.1 数组和列表 40
2.2 链接列表 41
2.3 图与树 44
2.3.1 预备知识 44
2.3.2 欧拉图与哈密顿图 48
2.3.3 树 49
2.3.4 图的遍历 57
2.3.5 连通性 58
2.3.6 可平面图 62
2.3.7 染色与独立集 64
2.3.8 团覆盖 65
2.3.9 交图 65
2.3.10 弦图 66
2.3.11 更多的交图 70
2.3.12 图的匹配问题 70
2.3.13 图的中心 71
2.3.14 控制理论 72
2.3.15 图论中的一些问题 73
参考文献 74
第3章 并行算法设计环境 76
3.1 二叉树设计环境 76
3.2 二倍增长 79
3.3 指针跳转 79
3.4 分而治之 82
3.5 划分 83
3.6 小结 86
参考文献 86
习题 86
第4章 简单并行算法 88
4.1 向量内积 88
4.2 矩阵乘法 88
4.3 部分和 90
4.4 二项式系数 94
4.5 范围内最小值问题 98
参考文献 101
习题 101
第二部分 图模型算法
第5章 树算法 103
5.1 欧拉圈 103
5.2 给树加根 104
5.3 后序编号 105
5.4 后代个数 107
5.5 顶点层数 107
5.6 最低公共祖先 108
5.7 树收缩 110
5.8 算术表达式的计算 114
5.9 森林求根问题 117
5.10 到根的路 119
5.11 树变为二叉树 123
5.12 顶点直径 125
5.13 最远邻居 128
参考文献 130
习题 131
第6章 图算法 132
6.1 简单图算法 132
6.2 并行连通度算法 135
6.2.1 广度优先搜索（BFS） 135
6.2.2 利用BFS搜索连通支 139
6.2.3 传递闭包矩阵 141
6.2.4 顶点收缩 141
6.3 2-连通支 145
6.4 支撑树 146
6.5 最短路问题 148
参考文献 151
习题 152
第7章 弦图的NC算法 154
7.1 弦图判别 154
7.2 弦图的极大团 161
7.3 CV图的特征 163
7.4 路图判别 164
7.4.1 一些概念和事实 164
7.4.2 算法概述 168
7.4.3 两个UV图的并 169
7.4.4 正确性和复杂度 175
参考文献 177
第三部分 数组处理算法
第8章 搜索与合并 179
8.1 串行搜索 179
8.2 CREW PRAM模型下的并行搜索 180
8.3 更多数据的并行搜索 181
8.4 无序数组搜索 182
8.5 秩合并 182
8.6 双调合并 184
参考文献 187
第9章 排序算法 188
9.1 串行排序算法 188
9.1.1 冒泡排序 188
9.1.2 插入排序 189
9.1.3 Shell递减步长排序 190
9.1.4 堆排序 191
9.2 合并排序 193
9.3 排序网络 194
参考文献 195
习题 196
第四部分 数值算法
第10章 代数方程和矩阵 197
10.1 代数方程 197
10.1.1 几何解释 197
10.1.2 对分法 198
10.2 矩阵的行列式 199
10.3 线性方程组 202
10.3.1 高斯消元法 205
10.3.2 Givens旋转 206
10.4 傅里叶变换 208
10.5 多项式乘法 215
10.6 矩阵求逆 217
10.7 Toeplitz矩阵 219
10.8 三对角方程组 222
10.8.1 高斯消元法 222
10.8.2 奇偶约化法 223
参考文献 226
习题 227
第11章 微分与积分 228
11.1 微分 228
11.2 偏微分 229
11.3 定积分 233
11.4 插值 235
11.4.1 线性插值 235
11.4.2 二次插值 236
11.4.3 拉格朗日插值 236
参考文献 237
习题 238
第12章 微分方程 239
12.1 欧拉公式 239
12.2 偏微分方程 239
12.3 抛物方程 240
12.3.1 施密特法（求解抛物方程） 242
12.3.2 Laasonen法（求解抛物方程） 246
12.3.3 Crank Nickolson法 248
12.3.4 三层差分法 249
参考文献 251
部分习题解答 252
索引 258
