论文摘要
积和式的数学定义与行列式很相似,而且历史同样悠久,但它的计算远比行列式要困难,其计算复杂度是#P?难的。直到二十世纪七、八十年代,由于无线通讯、计算机网络、分子化学、统计物理、碳纳米结构模拟、代数方程组全部解的计算等领域一些重要问题的推动,积和式的理论和计算引起了大批学者的广泛关注,其中包括多位Wolf奖、Turing奖、Nevanlinna奖、Dannie Heineman奖得主,出现了一些突破性的理论成果,开始解决实际应用中的重要问题。本文研究以统计物理中Monomer-Dimer模型和化学图论中Fullerene问题为背景的积和式计算,通过有效利用矩阵结构的特殊性质改进积和式算法,使得可以计算问题的规模大大提高。本文提出了Monomer-Dimer系统的积和式模型,得到了Dimer常数和Monomer-Dimer常数更好的计算结果;将现有针对Fullerence积和式的最好算法与快速Fourier变换结合得到了新的Fullerene积和多项式的精确算法,从而将计算Fullerene积和多项式的规模从C40提高到C56。本文的主要贡献有:1.将现有的积和式重要度采样算法,纳入到随机Laplace展开这个统一的框架下来理解,从而得到了这类算法的更有效改进。2.系统研究了随机Laplace展开算法,指出这类算法存在计算结果偏小的缺陷,初步分析了该现象的机理,并通过概率密度拟和等手段进行抽样数据的后续处理,提高了算法的精度。3.通过构造辅助图,将Monomer-Dimer常数和Momoner-Dimer系统的配分函数问题转化为邻接矩阵积和式的计算问题,并给出了三维Dimer常数和Monomer-Dimer常数现有最好的数值结果。4.结合快速Fourier变换得到更好的针对Fullerene结构的积和多项式算法,数值实验表明算法是快速和稳定的。算法给出Fullerene积和多项式计算中C56问题的计算结果。