稀疏矩阵积和式的算法研究及其在物理、化学中的应用

二十世纪七、八十年代以来，无线通讯、分子化学和统计物理等领域蓬勃发展，相继出现一些重要的科学问题，均与计算矩阵（尤其是0,1矩阵）的积和式密切相关，从而使得积和式的理论和计算引起了更加广泛的关注。计算积和式是一个#P完全的计数问题，几乎不可能存在多项式时间的算法。而实际应用中出现的积和式计算问题，矩阵大多具有特殊的结构性质。针对具体问题的背景和特点设计更有效的算法，无疑是该领域发展并产生新突破的重要生长点。本项目组在已有研究成果的基础上，首次将图论中(0,1)矩阵可转化问题的最新理论成果，及数值代数中Gauss消去法主元选取的经典理论和求解线性方程组预处理的思想，引入积和式的算法设计，针对具有重大理论意义和应用价值的3维dimer覆盖问题和大团簇富勒烯的化学图论计算问题的结构特点，一定会在计算规模和精度上有较大突破。