On the numerical solution of the heat equation in unbounded domains

Many problems in applied mathematics require the solution of the heat equation in unbounded domains. Integral equation methods are particularly appropriate for the solution of such problems for several reasons: they are unconditionally stable, they are insensitive to the complexity of the geometry, and they do not require the artificial truncation of the computational domain as do finite difference and finite element techniques. Methods of this type, however, have not become widespread due to the high cost of evaluating heat potentials. When M points are used in the discretization of the boundary and N time steps are computed, an amount of work of the order {dollar}O(Nsp2Msp2){dollar} has traditionally been required. We present an algorithm which requires an amount of work of the order {dollar}O(NMlog M){dollar} and which is based on the evolution of the continuous spectrum of the solution. The central idea is to split the solution into a history part and a local part and compute each separately. The history part is smooth and well approximated by a small number of points in Fourier domain while the local part is singular but easily computed via product integration. The method generalizes a technique developed by Greengard and Strain.