积和式是一种对矩阵的基本度量[1],虽然拥有与行列式类似的定义,但是计算积和式却被证明至少为NP-难的[2]。积和式计算的算法主要分为精确算法和近似算法。由于积和式计算固有的复杂度(#P-完全),精确算法只能对阶数较小以及具有特殊结构的稀疏矩阵(例如k正则矩阵)进行计算,所以近似算法成为积和式计算研究的重点。重要度采样和行列式规约是最重要的两类积和式实用近似算法。重要度采样算法是一种在保持估计量无偏性前提下,用于减小方差的蒙特卡洛算法。在积和式情形中,重要度采样算法从矩阵随机路径的角度来设计估计量,路径中每一步的展开概率称为此步的重要度。通过设计好的重要度,我们能够大幅减小估计量的方差,降低临界比。理想的重要度分布由矩阵的m-平衡(m-balance)矩阵A=(aijPer(A(i,j))/Per(A))给出。在该重要度分布下,重要度采样算法的方差为0,但是计算m-平衡矩阵等价于计算原矩阵积和式,因此,如何有效地估计m-平衡矩阵是设计重要度采样算法的关键。本文系统地介绍和分析了重要度采样算法的设计框架以及常见的几种重要度采样算法,并从积和式界的估计、重要度的比值以及神经网络三个角度对m-平衡矩阵的估计进行了研究。本文的主要贡献有·采用积和式界估计m-平衡矩阵的框架,我们通过数值实验比较了各种对Jurkat和Ryser上界的改进,并将其用于m-平衡矩阵中Per(A(i,j))的估计。·我们从重要度比值的角度来估计m-平衡矩阵,提出了比值重要度采样算法。该算法是Rasmussen方法和顺序重要度采样方法的推广。通过随机0-1矩阵以及富勒烯结构矩阵的数值实验,我们说明了该方法是一种有效的加速手段。·我们利用神经网络来估计m-平衡矩阵,提出了神经网络重要度采样算法,并用该算法解决神经网络计算积和式的高阶样本生成问题,最后通过数值实验验证了该算法的有效性。