在实际的工程计算中,经常会遇到求n阶方阵A的特征值(Eigenvalue)与特征向量 Eigenvector)的问题。对于一个方阵A,如果数值λ使方程组 Ax=x 即(A-In)x=0有非零解向量(Solution Vector)x,则称λ为方阵A的特征值,而非零向量x为 特征值λ所对应的特征向量,其中In为n阶单位矩阵

在阶数较大、系数阵为稀疏阵的情况下,可以采用迭代法求解线性方程组。用迭代法 (Iterative Method)求解线性方程组的优点是方法简单,便于编制计算机程序,但必须选取合 适的迭代格式及初始向量,以使迭代过程尽快地收敛。迭代法根据迭代格式的不同分成雅 可比(Jacobi)迭代、高斯塞德尔(Gauss-Seidel-)迭代和松弛(Relaxation)法等几种

在求解线性方程组(System of Linear Equations)的算法中,有两类最基本的算法,一类 是直接法,即以消去为基础的解法。如果不考虑误差的影响,从理论上讲,它可以在固定 步数内求得方程组的准确解。另一类是迭代解法,它是一个逐步求得近似解的过程,这种 方法便于编制解题程序,但存在着迭代是否收敛及收敛速度快慢的问题

矩阵运算是数值计算中最重要的一类运算特别是在线性代数和数值分析中它是一种最 基本的运算。本章讨论的矩阵运算包括矩阵转置、矩阵向量相乘、矩阵乘法、矩阵分解以 及方阵求逆等。在讨论并行矩阵算法时分三步进行:①算法描述及其串行算法;②算法的 并行化及其实现算法框架以及简单的算法分析;③算法实现的MP源程序,以利于读者实 践操作

计算几何是计算机科学中的一个分支,是专门研究有关几何对象问题的。它在图像分 析、模式识别、计算机图形学等中应用甚广。本章主要介绍几个基本计算几何问题的简单 并行算法和它们的MPI编程实现,包括包含问题、相交问题和凸壳问题等

组合优化问题在实践中有着广泛的应用,同时也是计算机科学中的重要研究课题。本 章对于八皇后问题、SAT问题、装箱问题、背包问题及TSP问题等五个经典的组合优化问 题,给出其定义、串行算法描述、并行算法描述以及并行算法的MPI源程序

图论在计算机科学、信息科学、人工智能网络理论、系统工程、控制论、运筹学和 经济管理等领域有着广泛的应用。但很多图论问题虽易表达,却难以求解,其中有相当多 的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MP 编程实现,包括传递闭包、连通分量、最短路径和最小生成树等

串匹配(String Matching)问题是计算机科学中的一个基本问题,也是复杂性理论中研 究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物 学等领域有着广泛的应用。而且,串匹配是这些应用中最耗时的核心问题,好的串匹配算 法能显著地提高应用的效率。因此,研究并设计快速的串匹配算法具有重要的理论价值 实际意义

1排序 排序是数据处理中经常使用的一种重要运算,如何进行排序,特别是如何进行高效的 排序,是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件,而记录则是 由若干数据项组成,其中的一项可用来标志一个记录,称为关键字项,该数据项的值称为 关键字 所谓排序,就是要整理文件中的记录,使得它按关键字递增(或递减)的次序排列起来

第一章小结本章从并行计算的角度出发,着重讨论当代科学和工程计算问题所要求的高 性能并行计算系统,包括并行计算机系统的互连技术、并行计算机的系统结构模型、存储 访问模型和存储结构组织等