学位论文 > 优秀研究生学位论文题录展示

积和式近似算法的分析及应用

作　者: 王磊
导　师: 白峰杉
学　校: 清华大学
专　业: 数学
关键词: #P-完全随机Laplace展开转移概率自适应近似算法负载平衡
分类号: O151.21
类　型: 博士论文
年　份: 2013年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

矩阵积和式是与矩阵行列式定义类似的一种矩阵度量，但积和式计算的难度远远高于行列式。即使每行、每列均仅含3个非零元的0-1矩阵（称为3-正则矩阵），其积和式的计算也是#P-完全的，难度不低于组合优化中的NP-完全问题。近三十年来，随着积和式在诸多领域的深入应用，比如无线通讯、统计物理、化学图论、多目标跟踪和多项式方程组等，积和式的理论和计算都取得了长足进步。本文着重研究了稀疏结构矩阵积和式近似算法和并行策略，并将其应用于化学图论中富勒烯结构和统计物理中Dimer覆盖模型的计算。本文首先给出了主元Rasmussen方法的一些理论分析。随机Laplace展开的策略由Rasmussen在1994年提出，其中展开策略最简单的被称为Rasmussen方法。在实际问题的计算中，需要对Rasmussen方法进行选主元的改进才能得到较为理想的计算效果。但一直以来，选主元策略的改进缺乏理论分析。本文借鉴Frieze对3-正则结构最大匹配判定算法选主元策略的理论分析，建立了主元Rasmussen方法针对3-正则矩阵实现过程的Markov转移概率模型，对这类具有实用意义的特殊结构给出了选主元改进的一些概率解释，并对于3-正则矩阵、4-正则矩阵和随机稀疏矩阵做了数值验证。随机Laplace展开算法的核心是给出适当的展开概率，最理想的展开概率可由m-平衡矩阵得到。但精确计算该矩阵等同于积和式的计算，研究人员设计了多种策略对其进行近似。本文构造了双层循环迭代策略，在展开的每一步自适应地判断是否需要花更多的代价，即利用近似算法得到m-平衡矩阵展开概率更精确的估计，提出了内外迭代相互校正、改善的自适应随机Laplace展开方法。并通过富勒烯结构矩阵、Dimer覆盖矩阵以及随机稀疏矩阵验证了算法的有效性。对于非常稀疏的0-1矩阵，基于双元素展开的混合算法是一种有效的精确算法，其并行化实现为富勒烯化学提供了有力工具。大量的实验结果显示稀疏0-1矩阵的积和式值与其利用双元素展开混合算法的计算时间具有强相关的关系。利用平行机排序的理论，本文提出了并行任务按照近似积和式值序列的非增顺序排列，可以得到接近近似最优的负载平衡策略，有效改进了原有的负载平衡策略。

全文目录

摘要  3-4
Abstract  4-8
主要符号对照表  8-9
第1章引言  9-18
  1.1 积和式的背景介绍  9-10
  1.2 积和式的性质  10-11
  1.3 积和式的理论意义与应用举例  11-16
    1.3.1 二部图完美匹配的判定与计数  11-12
    1.3.2 富勒烯化学  12-13
    1.3.3 Monomer-Dimer覆盖模型和Dimer覆盖模型  13-16
  1.4 论文的主要结构  16-18
第2章积和式计算与估计  18-26
  2.1 积和式计算的精确算法  18-20
    2.1.1 Laplace展开算法  18-19
    2.1.2 R-NW算法  19
    2.1.3 混合算法  19-20
  2.2 积和式计算的近似算法  20-24
    2.2.1 行列式规约类方法  21-22
    2.2.2 随机Laplace展开类方法  22-23
    2.2.3 Markov链蒙特卡洛类方法  23-24
    2.2.4 迭代均衡方法  24
  2.3 积和式界的估计  24-26
第3章主元Rasmussen方法的效率分析  26-46
  3.1 主元Rasmussen方法  26-30
  3.2 算法的图表示  30-32
  3.3 算法分析的Markov转移模型  32-35
  3.4 理论结果  35-41
  3.5 数值结果  41-46
第4章自适应的随机Laplace展开方法  46-66
  4.1 展开概率分布  46-49
  4.2 收敛速度和临界比的比较  49-53
  4.3 展开概率分布的比较  53-59
  4.4 双层自适应算法  59-62
  4.5 数值实验  62-66
    4.5.1 富勒烯分子图邻接矩阵的计算  62-63
    4.5.2 Dimer常数的估计  63
    4.5.3 随机稀疏矩阵积和式的计算  63-66
第5章积和式并行计算中的负载平衡策略  66-79
  5.1 积和式的并行计算方法  66-68
    5.1.1 并行混合算法  66-67
    5.1.2 平行机排序  67-68
  5.2 改进的负载平衡策略  68-72
    5.2.1 积和式计算时间的线性回归分析  68-70
    5.2.2 Kendall序列相关分析  70-71
    5.2.3 改进的负载平衡策略  71-72
  5.3 数值结果  72-79
    5.3.1 C100积和式数值结果  72-74
    5.3.2 C60积和多项式数值结果  74-76
    5.3.3 稀疏矩阵积和式数值结果  76-79
第6章结论与展望  79-82
  6.1 研究工作总结  79-80
  6.2 未来工作展望  80-82
参考文献  82-87
致谢  87-89
附录 A 富勒烯结构的数据  89-94
个人简历、在学期间发表的学术论文与研究成果  94

积和式近似算法的分析及应用

内容摘要

全文目录

相似论文