  Microscopic models of classical degrees of freedom coupled to non-interacting
fermions occur in many different contexts. Prominent examples from solid state
physics are descriptions of colossal magnetoresistance manganites and diluted
magnetic semiconductors, or auxiliary field methods for correlated electron
systems. Monte Carlo simulations are vital for an understanding of such
systems, but notorious for requiring the solution of the fermion problem with
each change in the classical field configuration. We present an efficient,
truncation-free O(N) method on the basis of Chebyshev expanded local Green
functions, which allows us to simulate systems of unprecedented size N.
