Finite element heterogeneous multiscale methods with near optimal computational complexity

This paper is concerned with a numerical method for multiscale elliptic problems. Using the framework of the heterogeneous multiscale methods (HMM), we propose a micro-macro approach which combines the finite element method (FEM) for the macroscopic solver and the pseudospectral method for the microsolver. Unlike the micro-macro methods based on the standard FEM proposed so far, in the HMM we obtain, for periodic homogenization problems, a method that has almost-linear complexity in the number of degrees of freedom of the discretization of the macro(slow) variable.