  This paper introduces the multidimensional butterfly factorization as a
data-sparse representation of multidimensional kernel matrices that satisfy the
complementary low-rank property. This factorization approximates such a kernel
matrix of size $N\times N$ with a product of $\O(\log N)$ sparse matrices, each
of which contains $\O(N)$ nonzero entries. We also propose efficient algorithms
for constructing this factorization when either (i) a fast algorithm for
applying the kernel matrix and its adjoint is available or (ii) every entry of
the kernel matrix can be evaluated in $\O(1)$ operations. For the kernel
matrices of multidimensional Fourier integral operators, for which the
complementary low-rank property is not satisfied due to a singularity at the
origin, we extend this factorization by combining it with either a polar
coordinate transformation or a multiscale decomposition of the integration
domain to overcome the singularity. Numerical results are provided to
demonstrate the efficiency of the proposed algorithms.
