The Algorithms Of Permanent With Application In Statistical Physics And Chemical Graph

The permanent of matrix is similar to the determinant in the mathematical defini-tion, as well as the long history of investigation. However the computation of perma-nent is a #P?hard problem in counting, which is much harder than the computation ofdeterminant. Motivated by the applications in the wireless communication, computernetworks, molecular chemistry, statistical physics, carbon nano-structure simulationand the computation of polynomial systems, intensive attentions have been received inthis field during the last two decades from many scholars, including Wolf prize, Turingprize, Nevanlinna prize and Dannie Heineman prize owners. There have been fruitfultheoretical results and progress in solving problems in applications in the recent years.In this thesis we focus on the numerical computation of permanent arising fromthe Monomer-Dimer model in statistical physics and the Fullerene problems in chemi-cal graph. By e?ectively using the special properties of the matrix structure, the size ofthe computable problems is increased. We propose a model of Monomer-Dimer systemwith the permanent of matrix, so that the improved estimations of the Monomer-Dimerand Dimer constants are obtained. An e?cient numerical method for computing per-manental polynomials of graphs is proposed, which adapts FFT with the multi-entryexpansion of permanent. It works for the C56, while the largest Fullerene whose per-manental polynomial is computed before is C40.The main contribution of the thesis are:1. Several well known importance sampling algorithms for permanents are inte-grated into a general framework, randomized Laplacian expansion. An e?cientalgorithm is proposed naturally with this framework.2. The numerical experiments of the two-dimensional models show that the approx-imations produced by all of randomized Laplacian algorithms are smaller thanthe analytic solution uniformly as the size of the lattice gets large. A probabilitydensity fitting method for the simulation data is introduced and the accuracy of the computation is improved dramatically.3. An auxiliary graph is constructed, so that the computation of Monomer-Dimerconstant and the partition function of the system are transformed to the com-putation of permanents of matrices. The numerical results of three-dimensionalDimer constants and Monomer-Dimer constant are obtained which are betterthan the known results.4. An e?cient numerical method for permanental polynomials of graphs is pro-posed. It adapts FFT with the multi-entry expansion of permanent. Extensivenumerical computations show that the algorithm is fast and stable. This algo-rithm works for C56 well.