Fast Wavelet Based Algorithms for Linear Evolution Equations
Bjorn E. Engquist, Stanley Osher, Sifen Zhong · SIAM Journal on Scientific Computing · 1994
The authors devise a class of fast wavelet based algorithms for linear evolution equations whose coefficients are time independent. The method draws on the work of Beylkin, Coifman, and Rokhlin [Comm. Pure Appl. Math., 44 (1991), pp. 141–184], which they applied to general Calderon–Zygmund type integral operators. The authors apply a modification of their idea to linear hyperbolic and parabolic equations, with spatially varying coefficients. The complexity for hyperbolic equations in one dimension is reduced from $O(N^2 )$ to $O(N\log ^3 N)$. There are somewhat better gains for parabolic equations in multidimensions.