高复杂度矩阵计算问题及其应用

项目名称： 高复杂度矩阵计算问题及其应用

项目编号： No.10871115

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 白峰杉

作者单位： 清华大学

项目金额： 28万元

中文摘要： 积和式、积和多项式是重要的数学问题，在很多重要的研究领域有本质性的应用，例如统计物理中的Ising 模型和Monomer-dimer 覆盖模型。与我们熟悉的矩阵计算问题不同，计算矩阵积和式、积和多项式都是指数难度的问题。本项目有效利用矩阵的结构性质，对这类高复杂度矩阵计算问题的确定性和随机型算法进行了比较系统的研究，使得上述问题的可计算规模和计算精度均得到较大提高。 本项目的研究在稀疏结构矩阵有效近似算法设计方面取得多方面进展，并应用于两个状态的自旋模型，3维dimer常数以及 monomer-dimer系统配分函数的计算，给出了度数有界图上的两状态自旋模型的配分函数的完全多项式时间近似算法(FPTAS)，以及monomer- dimer常数最好的数值近似。 利用图的划分，我们对稀疏矩阵进行有效的分解，构造了稀疏矩阵积和式与积和多项式更有效的算法，并实现并行化。对富勒烯类结构，积和式与积和多项式的可计算规模分别从60，90阶提高到90,120阶。利用算法优势，我们发现了一些化学家感兴趣的新的富勒烯结构特征。 在本项目资助下，我们还在计算统计、多项式方程组数值解等方面开展了研究。

中文关键词： Ising模型；矩阵积和式；稀疏矩阵；近似算法；计算复杂度

英文摘要： Permanent and permanental polynomial of matrix are important mathematical problems. They have critical applications in various fields, such as Ising model and monomer-dimer covering models in statistical physics. It is different from the classical matrix computation problems that the permanent and the permanental polynomial are #P-hard in complexity. This implies that there would be no algorithms running in polynomial time for those problems by the fundamental conjecture in computational complexity theory. In this project, the special structure properties of the problems are intensively used so that some problems from practical applications are efficiently solved. Breakthroughs both in computable scale and computational precise are achieved. Improvements are made in approximate algorithms of sparse structural matrices. They are applied to two states spin model, the computations of 3-dimentianal dimer constant and partition function of monomer-dimer model. An FPTAS for the partition function of two states spin model is constructed and the best known estimation of monomer-dimer constant is obtained. Based on the graph partition, the sparse matrix is decomposed efficiently in the sense of permanent computation. Hence improved permanent and permanental polynomial algorithms are constructed. For fullerene structure, the algorithms improve the ability of computation of permanent and permanental polynomials from n=60,90 to n=90,120 respectively. Some new meaningful graph properties of fullerenes are discovered. Supported by the project, we extend our research into fields, such as computational statistics and the numerical solution of polynomial systems.

英文关键词： Ising model；permanent；sparse matrix； approximate algorithm；computational complexity