Analysis And Application Of Approximation Algorithms Of Permanent

The permanent of matrix is a measure of matrix, and the definition of the permanentis similar to the determinant of matrix, but computing the permanent is much harderthan computing the determinant. Even for0-1matrix which contains only three non-zeroelements in each row and each column, i.e.3-regular matrix, the permanent calculationof which is a#P-Complete problem, and this problem is no easier than a NP-Completeproblem in combinatorial optimization. In recent three decades, with the application ofpermanent in many fields, such as wireless communication, statistical physics, chemicalgraph theory, multi-target tracking, polynomial equations and so on, it has made greatprogress in the theory and computation.This thesis focuses on approximation algorithms and parallel methods of permanentof matrix with sparse structure. Numerical results of fullerene structure in chemical graphtheory and that of Dimer covering model in statistical physics are also given.Theoretical analysis of Rasmussen method with pivoting is given first. RandomizedLaplace expansion strategy was proposed by Rasmussen in1994. The simplest expan-sion strategy is called Rasmussen method. In the calculation of the practical problems, itneeds to improve Rasmussen method with pivoting to obtain more desirable calculationresults. However, it has been lack of theoretical analysis of pivoting strategy improvementfor a long time. Learned from theoretical analysis of pivoting strategy that Frieze usedin analyzing maximum matching decision algorithm for3-regular structure. A Markovtransition probability model of Rasmussen method with pivoting for3-regular matrix isestablished. Some probabilistic interpretations on pivoting strategy improvement are giv-en for such special structure with practical significance. Numerical results are given for3-regular matrix,4-regular matrix and random sparse matrix, which verifies our analysis.The core of randomized Laplace expansion algorithms is to give appropriate expan-sion probability, and the ideal expansion probability can be given by m-balance matrix.However, accurate calculation of m-balance matrix is equivalent to compute the perma-nent, so researchers designed a variety of approximation strategies. This thesis constructsa double loop iteration strategy, adaptively determining whether to use approximationalgorithm to get a more accurate estimate of expansion probability of m-balance matrix at each step of the expansion. An adaptively randomized Laplace expansion method isproposed, which is an internal and external iteration algorithm with mutual correctionand improvement. This thesis validates the efectiveness of this algorithm using fullerenestructure matrix, Dimer covering matrix and random sparse matrix.For very sparse0-1matrix, hybrid algorithm based on double elements expansionis an efcient exact algorithm, and the parallelization of this algorithm provides a pow-erful tool for fullerene chemistry. Experimental results show that the permanent value ofsparse0-1matrix has a strong correlation relationship with its computation time whenusing hybrid algorithm based on double elements expansion. According to parallel ma-chine scheduling theory, parallel tasks arrange in the non-increasing order of approximatepermanent values sequence, it will be closer to the approximate optimal load balancingstrategy, which efectively improves the original load balancing strategy.