稀疏矩阵积和式与积和多项式的并行算法

论文摘要

二十世纪七、八十年代以来,无线通讯、分子化学和统计物理等领域出现了很多与矩阵积和式计算有关的问题,使得积和式的计算和理论研究引起了广泛的关注。精确计算积和式是一个#P-完全的问题,复杂度不低于NP-完全问题,因此计算上有本质的困难。如何充分利用所研究问题的特殊性质,是构造算法的关键。而实际中遇到的积和式,所需计算的矩阵往往具有特殊的结构性质可以利用。本文所主要讨论的富勒烯及其衍生物有许多优异的性能,因而受到高度重视。富勒烯分子结构的一个重要研究课题就是其邻接矩阵的积和式与积和多项式的性质。富勒烯分子邻接矩阵具有对称、稀疏的结构。本文发展了一种计算稀疏矩阵积和式的并行算法,并将它应用于富勒烯的积和式与积和多项式的计算。在计算积和多项式时,再深入利用问题本身的性质,借助平行加工的排序理论,进一步改进了并行计算的负载平衡策略,取得了相当高的并行效率。本文的算法研究将富勒烯积和多项式的计算能力从C50提高到了现实世界中真正具有实际应用意义的富勒烯C≥60。本文计算了所有的富勒烯C20～50邻接矩阵的积和式与积和多项式,获得了有应用意义的数据,利用统计的方法,对富勒烯积和多项式系数和零点的结构性质进行了研究,对前人取得的一些结果提供了进一步的支持,同时也发现了一些新的结构特点。为解决富勒烯积和多项式的零点聚类问题。本文提出了多维稳定婚姻问题的模型,同时相应地给出了算法,并成功地应用于富勒烯积和多项式零点的聚类问题。本文的主要学术贡献是:（1）设计并实现了稀疏矩阵积和式与积和多项式的并行算法;（2）利用排序理论给出了有效的负载平衡策略;（3）为富勒烯分子结构的研究提供了有价值的数据支持;（4）多维稳定婚姻模型及计算方法,为聚类问题的求解提供了新途径。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 积和式概述
• 1.2 富勒烯
• 1.3 研究内容
• 第2章 稀疏矩阵积和式与积和多项式
• 2.1 基于容斥原理的算法
• 2.2 稀疏矩阵的直接展开算法
• 2.3 双元素展开算法和局部保结构算法
• 2.4 稀疏矩阵积和多项式的一种有效算法
• 2.5 数值结果
• 2.6 本章小结
• 第3章 稀疏矩阵积和式与积和多项式的并行算法
• 3.1 混合算法的并行化
• 3.2 并行计算负载平衡策略
• 3.3 数值结果
• 3.4 本章小结
• 第4章 富勒烯的积和多项式计算结果与分析
• 4.1 本章引论
• 4.2 C≤36 的积和多项式
• 4.3 C≤50 的积和多项式
• 4.4 本章小结
• 第5章 积和多项式零点聚类的多维稳定婚姻模型及算法
• 5.1 富勒烯积和多项式零点聚类问题
• 5.2 经典稳定婚姻模型及其变型
• 5.3 多维稳定婚姻模型
• 5.4 数值结果
• 5.5 本章小结
• 第6章 结论
• 6.1 研究总结
• 6.2 进一步的工作目标
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果