A sparse spectral method for homogenization multiscale problems
Journal Article
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(ε-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 ε is very small. We also show some ways to extend the methods to hyperbolic and elliptic problems. © 2007 Society for Industrial and Applied Mathematics.
Full Text
Duke Authors
Cited Authors
- Daubechies, I; Runborg, O; Zou, J
Published Date
- August 1, 2007
Published In
Volume / Issue
- 6 / 3
Start / End Page
- 711 - 740
Electronic International Standard Serial Number (EISSN)
- 1540-3467
International Standard Serial Number (ISSN)
- 1540-3459
Digital Object Identifier (DOI)
- 10.1137/060676258
Citation Source
- Scopus