A Sparse Spectral Method for Homogenization Multiscale Problems
Ingrid C. Daubechies, Olof Runborg, Jing Zou · Multiscale Modeling and Simulation · 2007
We develop a new sparse spectral method, in which the fast Fourier transform (FFT) is replaced by RA$\mathcal{\ell}$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 \ll N$. To illustrate its potential, we consider the parabolic homogenization problem with a characteristic fine scale size $\varepsilon$. For fixed tolerance the sparse method has a computational cost of $O(|{\log\varepsilon}|)$ per time step, whereas standard methods cost at least $O(\varepsilon^{-1})$. 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 $\varepsilon$ is very small. We also show some ways to extend the methods to hyperbolic and elliptic problems.