Analysis And Application Of Importance Sampling Methods Of Permanent

The permanent is a basic kind of measure of matrix,which shares a similar defi-nition with the determinant of matrix[1].However,unlike the determinant,the perma-nent' calculation is a NP-hard problem proved by Valiant in 1978[2].Algorithms of computing the permanent can be divided into two classes,accurate algorithms and approximation algorithms.Due to the complexity of computing the permanent,accu-rate algorithms are effective for only lower order matrix and some sparse matrix with special structures(e.g.k-regular matrix).Thus approximation algorithms receive inten-sive intentions in permanent calculation.Among them,importance sampling methods and determinant reduction methods are two kinds of the most important approximation algorithms in permanent's practical calculationImportance sampling is a form of Monte Carlo sampling designed to reduce the variances with the estimator unbiased.Under the circumstances of permanent,impor-tance sampling methods construct estimators from the perspective of random paths The expansion probabilities of steps in the path are called the importance degrees of the steps.By designing proper importance degrees,we can drastically reduce the vari-ances and critical ratio.The ideal importance degree distribution is given by m-balance matrix A=(aijPer(A(i,j))/Per(AA)).In this distribution,the variances of importance sampling are reduced to 0.However,m-balance matrix's calculation problem is as hard as the per-manent's calculation problem,which makes the estimation of m-balance matrix the key of designing importance sampling methods.This thesis gives a systematic description and analysis of importance sampling methods and several typical examples.We research the estimation of m-balance matrix from three perspectives:using the permanent's bound,using the importance degree ra-tio and using the artificial neural network.We have achieved the following innovations:·Employing the framework of estimating m-balance matrix by the permanent'bound,we compare various improvements of Jurkat and Ryser's bound through numerical experiments and choose the best bound to evaluate Per(A(i,j))in m-balance matrix.·We estimate m-balance matrix by the importance degree ratio and give a new importance sampling method named the ratio sampling method.This method is generalization of the sequential importance sampling method and the Ras-mussen's method.We validate the effectiveness of this method using random sparse matrix and fullerene structure matrix.·We estimate m-balance matrix by the artificial neural network and give a new im-portance sampling method named the ANN sampling method.This thesis uses the method to solve the generation problem of high order samples in ANN's per-manent calculation issues.Finally,We validate the effectiveness of this method using random sparse matrix and fullerene structure matrix.