A Sparse Spectral Method for Homogenization Multiscale Problems

We develop a new sparse spectral method, in which the Fast Fourier Transform (FFT) is replaced by RA‘SFA (Randomized Algorithm of Sparse Fourier Analysis); this is a sublinear randomized,algorithm that takes time O(B log N) to recover a B-term Fourier representation for a signal of length N , where we assume B N . To illustrate its potential, we consider the parabolic homogenization,problem,with a characteristic ne,scale size ". For x ed tolerance the sparse method has a computational cost of O(j log "j) per time step, whereas standard methods,cost at least O(" ,). We present a theoretical analysis as well as numerical results; they show the advantage of the new method,in speed over the traditional spectral methods when," is very small. We also show some,ways to extend the methods,to hyperbolic and elliptic problems.