A fast algorithm for multilinear operators (Q427081): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.acha.2012.03.010 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2026315028 / rank | |||
Normal rank |
Revision as of 23:32, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A fast algorithm for multilinear operators |
scientific article |
Statements
A fast algorithm for multilinear operators (English)
0 references
13 June 2012
0 references
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\).
0 references
multilinear operators
0 references
fast Fourier transform
0 references
multiscale decomposition
0 references
low-rank approximation
0 references
multilinear integrals
0 references
algorithm
0 references
convolution
0 references
complexity
0 references
numerical results
0 references