第1章 引言
1.1 背景介绍
在一些文献中积和式的概念经常出现, 有重要的数学意义。它与组合计数问题有很重要的联系。可以见如下的例子：
完美匹配的个数 考虑一个二部图G(V,E)(如图1.1), 如果行和列分别代表二部图的顶点集, 那么二部图的邻接矩阵A的积和式等于二部图完美匹配的个数。假设邻接矩阵A的行代表男士, 列代表女士, 那么矩阵A的积和式代表所有的男士都找到配偶的可能数。
非定点排列的个数 A是一个n阶方阵, 它的主对角元是0, 其他元素都是1, 那么Per(A)等于1,2,...,n所有非定点排列的个数。
多齐次同伦算法中分组B′ezout数计算 考虑多元多项式方程组
防领域和交通路口监管等民用领域起着非常重要的作用，近年来它的算法研究逐渐成为一个有着巨大实际价值的热点问题。
多目标跟踪算法中基础的一环是多目标匹配。举个例子来说，第一时刻一架空中预警飞机监测到海面有n 艘军舰，并记录下它们的位置；在第二时刻这架飞机又对海面进行了监察，记录下了n艘军舰第二时刻的位置，通过计算将两个时刻军舰的位置两两匹配起来，这就是多目标匹配。
1.2 积和式的性质
积和式的定义与行列式很相似，有些行列式的基本性质，积和式也成立；同时也有行列式的性质，积和式不成立。积和式的基本性质不仅对积和式计算，而且对积和式理论研究也是很重要的。
性质 1.2(规范性)： Per(I) = 1,其中I是单位阵。
性质 1.3(转置不变性)： Per(A) = Per(AT), 其中AT表示矩阵A的转置。
性质 1.4(交错不变性)： 交换矩阵的两行或两列，矩阵的积和式不变。
积和式的这四条性质，只需要按照积和式定义1.1进行展开即可得到。
行列式也满足性质1.1-1.3三条性质，对于性质1.4行列式需要加负号。此外行列式还满足:
性质 1.5： 把矩阵一行乘以某个数加到另外一行得到新矩阵，原矩阵行列式与新矩阵行列式值相等。
因为积和式不满足性质1.5，导致了积和式的计算复杂度比行列式大得多，在随后的几节我们简要回顾积和式与积和多项式计算的研究现状及主要方法。
第2章 积和式的随机算法及Dimer模型计算
在第一章中我们已经综述了积和式计算的一些标准算法。现在已知关于积和式最好的精确算法是Nijenhuis 和Wilf提出的基于容斥原理的算法, 它的复杂度为O(n2n-1)。在Dimer模型的计算中，因为矩阵的维数很高，通常有上千阶，所以对于这个问题而言，精确算法是行不通的。研究和发展一些有理论保证的近似算法成为了一种现实可行的选择。
2.1Dimer模型
Dimer模型是统计物理的基本模型。人们对它的研究已经有很长的历史。令m,d为正整数，大小为m、维数为d的晶格V定义为Md, 其中
M = {1, 2, · · · , m}.
我们通常可以把它认为是空间中的离散点x = (x1, · · · , xd) ∈ Rd构成的集合, 如图2.2(a)所示。
一个具有周期边条件的Dimer是V的一个二元子集合{x,y}, 它满足(|x1-y1|, · · · , |xd-yd|)只有一个非零元, 并且这个非零元等于1 或m ? 1。一个Dimer 覆盖是Dimer构成的一个集合，并且这个集合把集合V覆盖住，见图2.2 (b)。显然，如果m是奇数，那么不存在Dimer覆盖。所以我们假定今后的讨论中m是偶数。
所有Dimer覆盖构成的集合叫做Dimer模型的组态空间，在Dimer模型理论中一个基本问题是：
组态空间的基数是多少？
2.2二维Dimer问题的数值计算
注意到二维Dimer模型有解析解。所以可以把它作为一个很好的平台来测试算法的性能。考虑简单的情况m = 8，矩阵A的规模不大，这样很少的抽样就能得到不错的数值近似。图2.3给出周期边条件模型的数值结果。在图形中横轴是四种算法的抽样数目，纵轴是误差。Ras (Rasmussen[30]提出的方法), Liu (Liu[31]等人提出的方法),B-S(Beichl和Sullivan[8]提出的方法)和Improved(基于Br′egman界的改进算法)一起放在图中进行比较。可以看出，对规模较小的问题这四种算法在效果上并没有本质性的差异。
这四种算法都应用于Dimer常数λ2(m)的计算中，其中m代表晶格的大小，表2.1列出了计算结果。表的最后一列给出了改进算法的抽样值取对数值后得到的抽样标准差。
表2.1中的结果说明，当问题规模增大时，基于Br′egman界的改进算法确实比其他三种算法效果好。但是，当晶格的规模m增大时，所有算法的抽样均值总要比真实值小。一个自然的想法是增大抽样的数目。表2.2说明，对于大规模问题为了得到足够的数值精度，抽样的数目在可能接受的计算时间内达到要求几乎是不可能的。
本节的数值结果表明，当晶格的规模m增大时，随机Laplace展开算法的误差也随之增大。特别是当m增大到一定程度时，得到的数值近似结果一致的要比精确解小。在下一节中我们解释产生这种现象的原因。
图 2.3 四种随机Laplace算法收敛速度的比较，横轴是抽样数目，纵轴是算法近似值λ2(8)的误差.
第 3章 Monomer-Dimer的积和式模型及计算 ................. 39
3.1 Monomer-Dimer模型 ................. 39
3.2 k匹配的积和式公式 ....................... 40
3.3 所有匹配的积和式公式....................... 42
第 4章 积和多项式计算 .............. 52
4.1 背景介绍 ............... 52
4.2 积和多项式算法 .................... 53
第 5章 结论与展望 ............. 65
5.1 研究总结 ............. 65
5.2 下一步工作展望 ................ 66
第4章 积和多项式计算
在第二章和第三章中我们详细的讨论了以统计物理为背景的积和式计算，特别是随机Laplace展开算法，在本章我们以Fullerene为应用背景，研究积和多项式算法。本章我们按照如下顺序来安排内容：第一节给出化学图论中Fullerene模型的描述; 第二节首先给出针对特殊稀疏结构矩阵的积和式精确算法, 进而结合快速Fourier变换(以下都简称FFT)算法给出积和多项式的一种新算法; 第三节给出数值结果。
4.1 背景介绍
Buckmister Fullerene是由若干个六元环和十二个五元环构成的笼状全碳分子。1985年，H.W. Kroto, R.E. Smally和R.F. Curl三位教授脉冲激光蒸发石墨产生并发现了Fullerene。三位教授因其在这方面的杰出贡献，共同获得了1996年的诺贝尔化学奖。这一发现成为当今纳米科学与技术的基石性工作。
可以用化学图论的方法来研究Fullerene的分子结构。分子中每个原子可以看成图的一个顶点，如果两个原子间有化学键存在，那么图中的相应顶点就有边相连。这样就可以构造一个分子图G(V,E)。对于分子图给每个顶点编号，存在一个对称的邻接矩阵A = (ai j), 它的定义为
在给出了与图相关的邻接矩阵后，我们就可以讨论几种与图密切联系的图多项式了。最主要的有三种：特征多项式，匹配多项式，积和多项式。匹配多项式定义为：
这里n为图中顶点的个数，m = n/2 , mk表示从图G中取出k条互不相连的边的可能数，换句话说就是图G的k匹配数。
这三种图的多项式可被应用于研究芳香性化合物的结构特征、碳氢化合物的相对稳定性、分子的Dewar化合价结构数和kekul′e化合价结构数等，关于它们在化学和化学图论中的更多应用，可以参考。本章的主要工作集中在BuckmisterFullerene邻接矩阵的积和多项式的计算上。
第5章 结论与展望
5.1 研究总结
本文综合利用数值代数、图论、统计计算等工具，给出了积和式的随机近似算法和积和式多项式的精确算法,并利用构造的算法来解决统计物理和化学图论中的实际问题。本文有如下几个主要结果
1. 系统的研究了完美匹配计数的随机Laplace展开算法族，并将算法应用于Dimer模型 具体的要点为：
（1）作为一个算法族，将现有的一些重要算法统一纳入到这个框架下来理解。基于积和式Br′egman估界，我们提出了一个新的算法。
（2）随机Laplace展开算法应用于Dimer模型，计算了相应二部图完美匹配的数目。数值试验表明，当矩阵的规模变大时，计算的误差也随之增大，并且近似值比真实值要小。我们从小概率事件（即具有大值的抽样比较难得到）的角度，分析和理解了该现象。
（3）提出了一种概率密度拟合的方法，并结合Bootstrap和加权最小二乘法两种统计方法，修正了Dimer常数λ2和λ3计算结果。拟合修正后的λ2与现有的解析解符合得很好；λ3数值结果更可信。
2. 提出了所有匹配计数问题的积和式模型，并应用于Monomer-Dimer问题具体的要点为：
（1）对于给定一个二部图，我们在该图的基础上构造了一个扩展的二部图，原图的所有匹配个数等于扩展图的完美匹配数除以一个常数。
（2）形式上扩展图的顶点数是原图的二倍，所以扩展图的邻接矩阵的规模是原邻接矩阵规模的二倍。但扩展图的邻接矩阵结构特殊，针对该结构设计的随机Laplace算法，计算过程中不会抽到非支撑的元素，从而完全避免了算法抽到数值为零的无效样本。
（3）将积和式模型和相应的随机Laplace展开算法应用到Monomer-Dimer常数的计算中，得到了二维和三维问题物理常数的近似值。
参考文献（略）