A general scheme for log-determinant computation of matrices via stochastic polynomial approximation. (15th February 2018)

• Record Type: Journal Article
• Authors: Peng, Wei; Wang, Hongxia
• Is Part Of: Computers & mathematics with applications. Volume 75:issue 4(2018)
• Page Start: 1259
• Page End: 1271
• Publication Date: 2018-02-15
• Subjects: Log-determinant -- Orthogonal polynomial expansions -- Stochastic algorithm -- Counting spanning trees; Electronic data processing -- Periodicals; Mathematics -- Data processing -- Periodicals; 510.28541
• DOI: 10.1016/j.camwa.2017.11.001
• Languages: English
• ISSNs: 0898-1221

Abstract

Abstract: 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.