Computing monomer-dimer systems through matrix permanent.
Computing monomer-dimer systems through matrix permanent.
复制标题
DOI：
10.1103/physreve.77.016706
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
Y. Huo;Heng Liang;Si‐Qi Liu;F. Bai
中科院分区：
文献类型：
--
作者：
Y. Huo;Heng Liang;Si‐Qi Liu;F. Bai
单体-二聚体模型是统计力学的基础。然而，它在计算上是P -完全的，即使是二维问题。通过将二部图的所有匹配数转化为扩展二部图的完美匹配数，给出了一个单二体系统的配分函数的表达式。采用序贯重要抽样算法计算持久式。对于周期性的二维晶格，单-二聚体常数h_{2}=0.662798972834。我们的近似值为0.6627+/-0.0002，这表明了算法的鲁棒性和效率。对于三维问题，我们的数值结果是0.7847+/-0.0014，这与最好的已知界限一致。
The monomer-dimer model is fundamental in statistical mechanics. However, it is #P -complete in computation, even for two-dimensional problems. A formulation for the partition function of the monomer-dimer system is proposed in this paper by transforming the number of all matchings of a bipartite graph into the number of perfect matchings of an extended bipartite graph, which can be given by a matrix permanent. Sequential importance sampling algorithm is applied to compute the permanents. For two-dimensional lattice with periodic condition, the monomer-dimer constant is known as h_{2}=0.662798972834 . We obtain 0.6627+/-0.0002 for our approximation, which shows the robustness and the efficiency of the algorithm. For three-dimensional problem, our numerical result is 0.7847+/-0.0014 , which agrees with the best known bounds.