A general scheme for log-determinant computation of matrices via stochastic polynomial approximation

作者：Peng, Wei; Wang, Hongxia^*

来源：Computers & Mathematics with Applications, 2018, 75(4): 1259-1271.

DOI：10.1016/j.camwa.2017.11.001

• Log-determinant
• Orthogonal polynomial expansions
• Stochastic algorithm
• Counting spanning trees

We study the approximation of determinant for large scale matrices with low computational complexity. This paper develops a generalized stochastic polynomial approximation frame as well as a stochastic Legendre approximation algorithm to calculate log-determinants of large-scale positive definite matrices based on the prior eigenvalue distributions. The generalized frame is implemented by weighted L-2 orthogonal polynomial expansions with an efficient recursion formula and matrix-vector multiplications. So the proposed scheme is efficient both in computational complexity and data storage. Respective error bounds are given in theory which guarantee the convergence of the proposed algorithms. We illustrate the effectiveness of our method by numerical experiments on both synthetic matrices and counting spanning trees.

• 出版日期2018-2-15
• 单位中国人民解放军国防科学技术大学