  The main goal of this paper is to define and study new methods for the
computation of effective coefficients in the homogenization of divergence-form
operators with random coefficients. The methods introduced here are proved to
have optimal computational complexity, and are shown numerically to display
small constant prefactors. In the spirit of multiscale methods, the main idea
is to rely on a progressive coarsening of the problem, which we implement via a
generalization of the Green-Kubo formula. The technique can be applied more
generally to compute the effective diffusivity of any additive functional of a
Markov process. In this broader context, we also discuss the alternative
possibility of using Monte-Carlo sampling, and show how a simple one-step
extrapolation can considerably improve the performance of this alternative
method.
