Parallel Algorithms For Computing Permanents And Permanental Polynomials Of Sparse Matrices

Since 1970's, important scientific problems emerge with the progress of wireless communication, molecular chemistry and statistical physics, which are closely related to the computation of permanents. Hence the theory and the computation of permanents attract extensive attention. The computation of permanents is proved to be a #P-Complete problem in counting, which is no easier than an NP-Complete problem in combinatorial optimization. Thus the permanent is essentially very hard in computation. It is remarkable to notice that most of matrices, which arise commonly in application, have special structural properties. It is only possible to design more efficient algorithms aiming at special problems. Fullerenes and their ramifications, which are of great importance in Nano science, are the focus of this thesis. One of the important research problems in the molecule structure of fullerenes is the properties of the permanents and the permanental polynomials of its adjacency matrices. The adjacency matrices are symmetric and sparse.A parallel method for computing permanents of sparse matrices is developed in this thesis, and the permanents and the permanental polynomials of the fullerenes are computed by this method. The load balancing strategies for the permanental polynomial computation is further improved with the help of the properties of the problem itself and the theory of offline unrelated parallel machine. Very high parallel efficiency is acquired. The algorithms of this thesis improved the ability of computation of the permanental polynomials from C50 to C60 and even larger fullerenes. Fullerenes C≥60 are of interest in real-world applications.All permanents and permanental polynomials of the adjacency matrices of fullerenes C20～50 are computed in this thesis, and meaningful data are gained for molecular chemistry. Using statistical methods, the structural properties of the coefficients and the zeros of the permanental polynomials of fullerenes are studied. Some supports to the conclusions of the former researches are obtained, and some new properties are also discovered.In order to solve the problem of the clustering of the zeros of permanental polynomials of the fullerenes, a multi-dimensional stable marriage model is proposed, relevant algorithms are given, and the clustering problem is solved.The main academic productions of this thesis are: (1) the parallel algorithms of computing permanents and permanental polynomials of sparse matrices are designed and implemented; (2) an efficient balancing straggles of parallel load is proposed using the theory of scheduling; (3) valuable data for the research of the molecule structure of fullerenes are obtained; (4) the multi-dimensional stable marriage model and its numerical methods give a new path to solve the clustering problems.