FAST MULTIRESOLUTION ALGORITHMS FOR MATRIX-VECTOR MULTIPLICATION

In this paper the authors present a class of multiresolution algorithms for fast application of structured dense matrices to arbitrary vectors, which includes the fast wavelet transform of Beylkin, Coifman. and Rokhlin and the multilevel matrix multiplication of Brandt and Lubrecht. In designing these algorithms the authors first apply data compression techniques to the matrix and then show how to compute the desired matrix-vector multiplication from the compressed form of the matrix. In describing this class special attention is paid to an algorithm that is based on discretization by cell-averages as it seems to be suitable for discretization of integral transforms with integrably singular kernels.