论文摘要
矩阵是数值代数中的一个基本概念,许多科学计算问题往往归结为对矩阵的操作,如数值天气预报、三维图像处理、地震分析等。由于矩阵的运算,特别是大规模矩阵相乘,矩阵的特征值求解等需要大量内存并且耗时的处理过程,单处理机已经无法承受,因此有效地实现大型的矩阵并行算法在实际应用中是非常重要的。并行计算主要是完成各处理机之间的任务分配,即任务划分、处理机映射,也就是如何将任务合理地分配到计算机系统的多个处理机上,使各处理机的工作负载保持相对均衡,并且获得较好的并行性,使整个计算机系统在较短的时间内完成处理任务。此外,并行计算还应包括使各处理机间的交互尽量达到最小,以减少处理机间的数据交换,降低数据通信的成本。本文以并行算法及其应用为研究对象,重点研究了并行算法在矩阵乘法中的应用,并在IBM x3500四核服务器上对算法进行了实现。首先概述了并行计算的基本知识,详细阐述了并行算法性能优劣的评价因子,并介绍了本文的MPI并行编程环境,主要工作如下:(1)实现了矩阵运算的并行计算。分别对矩阵运算中的矩阵向量乘法和矩阵乘法进行详细的算法描述和并行分析,并在MPI的并行环境下实现了并行算法,对其实验结果进行了比较分析,表明在大规模矩阵运算中使用并行计算的必要性。(2)研究了矩阵特征值的求解。在许多实际问题中有时只需要计算绝对值最大的特征值,而不需要求矩阵的全部特征值,本文还给出了实现求解最大特征值的并行算法,并对算法进行了实现,对结果进行了分析。(3)应用矩阵并行算法到图论中。最短路径算法是图论中的一个经典问题,本文对单源最短路径并行算法和改进的全部顶点最短路径并行算法进行了并行化分析,给出了并行化的实现方法和步骤,理论和实验表明并行算法具有较高的并行效率。