A sparse spectral method for homogenization multiscale problems
2007 (English)In: Multiscale Modeling & simulation, ISSN 1540-3459, E-ISSN 1540-3467, Vol. 6, no 3, 711-740 p.Article in journal (Refereed) Published
We develop a new sparse spectral method, in which the fast Fourier transform (FFT) is replaced by RAlSFA (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 epsilon. For fixed tolerance the sparse method has a computational cost of O(vertical bar log epsilon vertical bar) per time step, whereas standard methods cost at least O(epsilon(-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 epsilon is very small. We also show some ways to extend the methods to hyperbolic and elliptic problems.
Place, publisher, year, edition, pages
2007. Vol. 6, no 3, 711-740 p.
multiscale methods, sublinear algorithm, homogenization, spectral methods, sparse Fourier representation, finite-element-method, elliptic problems, coefficients
IdentifiersURN: urn:nbn:se:kth:diva-17200DOI: 10.1137/060676258ISI: 000252254800001ScopusID: 2-s2.0-51149113295OAI: oai:DiVA.org:kth-17200DiVA: diva2:335243
QC 201005252010-08-052010-08-05Bibliographically approved