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

矩阵的积和式、积和多项式是重要的数学问题。它们在很多重要的研究领域有实质性的应用，典型的如统计物理中具有重要理论意义和科学价值的Ising 模型和Monomer-dimer 覆盖模型。已经证明，这两个模型的求解与稀疏矩阵积和式的计算有内在和本质的联系。与我们熟悉的矩阵计算问题不同，计算矩阵积和式、积和多项式是#P-难问题，也就是说按照复杂性理论的基本猜想，它们不存在多项式时间的算法，所以研究主要集中在近似算法。尽可能有效利用结构性质，是科学计算研究中的基本原则。因此无论确定性算法还是随机算法，充分有效地利用结构特征，针对具体问题背景设计更有效的算法，是本问题研究的基本原则。本项目针对几类重要的物理和应用模型，借鉴传统矩阵计算中的成功经验，研究并利用矩阵的特殊结构性质，设计快速有效算法或比较大幅度地提高现有算法的效率，解决有实际意义的科学计算问题。