id: 06045879
dt: j
an: 06045879
au: Yang, Haizhao; Ying, Lexing
ti: A fast algorithm for multilinear operators.
so: Appl. Comput. Harmon. Anal. 33, No. 1, 148-158 (2012).
py: 2012
pu: Elsevier Science (Academic Press), Orlando, FL
la: EN
cc: 
ut: multilinear operators; fast Fourier transform; multiscale decomposition;
    low-rank approximation; multilinear integrals; algorithm; convolution;
    complexity; numerical results
ci: 
li: doi:10.1016/j.acha.2012.03.010
ab: Let $m(ξ_1,\dots,ξ_k)$ with $ξ_i\in {\Bbb 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_{ξ=ξ_1+\dots+ξ_k}m(ξ_1,\dots,ξ_k)\widehat f_1(ξ_1)\dots
    \widehat f_k(ξ_k)\,dξ_1\dots,dξ_{k-1}, $$ where $f_1,\dots,f_k$ are
    functions in the Schwartz space $C({\Bbb 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/ε))$ and $O(N\log^2 N\log (1/ε))$ 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(ξ_1,\dots,ξ_k)$ with $ξ_i\in {\Bbb 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$.
rv: Yuri A. Farkov (Moscow)