FAST WAVELET-BASED ALGORITHMS FOR LINEAR EVOLUTION-EQUATIONS

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-1841, 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(N2) to O(N log3 N). There are somewhat better gains for parabolic equations in multidimensions.