A fast algorithm for multilinear operators

DOI10.1016/J.ACHA.2012.03.010MaRDI QIDQ427081zbMATH OpenOpenAlexFDO

Authors Haizhao Yang, Lexing Ying

Publication date 13 June 2012

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.acha.2012.03.010

zbMATH Keywords

algorithmcomplexityconvolutionfast Fourier transformlow-rank approximationmultilinear integralsmultilinear operatorsmultiscale decompositionnumerical results

Mathematics Subject Classification ID

Numerical methods for trigonometric approximation and interpolation (65T40) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20)

Review text

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 NEWLINE\[NEWLINE \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}, NEWLINE\]NEWLINE 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\).

Recommendations

• A fast butterfly algorithm for the computation of Fourier integral operators
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• Fast adaptive algorithms in the non-standard form for multidimensional problems
• Fast Multipole Method for Multivariable Integrals
• Fast Algorithms for Boundary Integral Equations

Cites work

• A fast directional algorithm for high frequency acoustic scattering in two dimensions
• A theory of pseudoskeleton approximations
• An Introduction to Numerical Analysis
• Fast and Oblivious Convolution Quadrature
• Fast computation of partial Fourier transforms
• Fast Convolution for Nonreflecting Boundary Conditions
• Fast Numerical Solution of Nonlinear Volterra Convolution Equations
• Fast Runge-Kutta methods for nonlinear convolution systems of Volterra integral equations
• scientific article; zbMATH DE number 1015091 (Why is no real title available?)
• On Commutators of Singular Integrals and Bilinear Singular Integrals
• Sparse Fourier Transform via Butterfly Algorithm

Cited in

(8)

• Multidimensional butterfly factorization
• scientific article; zbMATH DE number 1136270 (Why is no real title available?)
• Fast computation of common left multiples of linear ordinary differential operators
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• Butterfly factorization
• scientific article; zbMATH DE number 5066284 (Why is no real title available?)
• Interpolative butterfly factorization
• Solving PDEs on unknown manifolds with machine learning

This page was built for publication: A fast algorithm for multilinear operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q427081)