  Estimating the trace of the inverse of a large matrix is an important problem
in lattice quantum chromodynamics. A multilevel Monte Carlo method is proposed
for this problem that uses different degree polynomials for the levels. The
polynomials are developed from the GMRES algorithm for solving linear
equations. To reduce orthogonalization expense, the highest degree polynomial
is a composite or double polynomial found with a polynomial preconditioned
GMRES iteration. Added to some of the Monte Carlo pieces is deflation of
eigenvalues that reduces the variance. Deflation is also used for finding a
reduced degree deflated polynomial. The new Multipolynomial Monte Carlo method
can significantly improve the trace computation for matrices that have a
difficult spectrum due to small eigenvalues.
