MULTILEVEL COMPUTATIONS OF INTEGRAL-TRANSFORMS AND PARTICLE INTERACTIONS WITH OSCILLATORY KERNELS

After a brief overview of multilevel computations in general, algorithms for performing dense-matrix multiplication are described for n x n matrices representing the interaction of n particles or the discretization of integral transforms on n gridpoints. For general asymptotically smooth kernels, possibly multiplied by an oscillatory exponential, the matrix multiplication can be performed in O(n(log n)q) operations, where q depends on the type of the kernel, the underlying spatial dimension, and the relation required between n and the accuracy of the calculation. Relations to, and combination with, Fourier methods are delineated.