Deflation for Monte-Carlo estimation of the trace of a matrix inverse

Jun 27, 2017, 10:15 AM


Mr Eloy Romero Alcalde (College of William and Mary )


In the context of computing disconnected diagrams, we investigate the
efficient estimation of the trace of large-scale matrix inverses. Our approach
is based on the Hutchinson method (Monte-Carlo averaging over matrix
quadratures). Previous work showed that combining deflation against the lowest
part of the spectrum with Hierarchical Probing can accelerate the convergence
significantly. As the size of the matrix grows, however, the computation of
enough singular vectors to achieve a reduction in the variance can be a

In this work we take advantage of the fact that the singular vectors
corresponding to the lowest modes can be represented well in a sparse basis.
This allows us to compute and store efficiently the first 500~1000 lowest modes
of the matrix spectrum, which is enough to obtain a good reduction in the
variance. Moreover we discuss different projectors for deflating and the
performance impact when the matrix is close to singular.

Primary authors

Mr Eloy Romero Alcalde (College of William and Mary ) Dr Andreas Stathopoulos (College of William and Mary )

Presentation materials