A Sparse Spectral Method for Homogenization Multiscale Problems

A new sparse spectral method is developed, in which the fast Fourier transform is replaced by RA$\mathcal{\ell}$SFA (randomized algorithm of sparse Fourier analysis), a sublinear randomized algorithm that takes time $O(B \log N)$ to recover a B-term Fourier representation for a signal of length N.

Abstract

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 fine scale size ε. For fixed tolerance the sparse method has a computational cost of O( | log ε|) per time step, whereas standard methods cost at least O(ε −d). 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.