A fast algorithm for multilinear operators (Q427081)

Let \(m(\xi_1,\dots,\xi_k)\) with \(\xi_i\in {\mathbb R}^d\) be a bounded multiplier function that is smooth away from the origin. This paper introduces a fast algorithm for computing multilinear integrals of the type \[ \int_{\xi=\xi_1+\dots+\xi_k}m(\xi_1,\dots,\xi_k)\widehat f_1(\xi_1)\dots \widehat f_k(\xi_k)\,d\xi_1\dots,d\xi_{k-1}, \] where \(f_1,\dots,f_k\) are functions in the Schwartz space \(C({\mathbb R}^d)\). For the \(1D\) bilinear case (i.e., \(d=1\) and \(k=2\)), the algorithm starts by constructing a hierarchical decomposition of the summation domain in Fourier space into squares, and then performs fast Fourier transform-based convolutions to speed up the computation associated with each individual square. The complexity of the algorithm is of order \(O(N\log N\log (1/\varepsilon))\) and \(O(N\log^2 N\log (1/\varepsilon))\) for smooth and piecewise symbols of order 0, respectively. Numerical results are provided to demonstrate the efficiency and accuracy of the algorithm. For the case \(k>3\), the authors prove the existence of low-rank approximation of the symbol \(m(\xi_1,\dots,\xi_k)\) with \(\xi_i\in {\mathbb R}^d\) restricted to a hypercube. It is noted that the randomized procedure, which gives good practical results for the bilinear case, does not have a direct generalization for \(k>3\).