A fast algorithm for multilinear operators (Q427081): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / 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 \[ \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\). | |||
Property / 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 \[ \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\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Yuri A. Farkov / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65T40 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65T50 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65Y20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6045879 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multilinear operators | |||
Property / zbMATH Keywords: multilinear operators / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
fast Fourier transform | |||
Property / zbMATH Keywords: fast Fourier transform / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multiscale decomposition | |||
Property / zbMATH Keywords: multiscale decomposition / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
low-rank approximation | |||
Property / zbMATH Keywords: low-rank approximation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multilinear integrals | |||
Property / zbMATH Keywords: multilinear integrals / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algorithm | |||
Property / zbMATH Keywords: algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
convolution | |||
Property / zbMATH Keywords: convolution / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complexity | |||
Property / zbMATH Keywords: complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
numerical results | |||
Property / zbMATH Keywords: numerical results / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
Property / cites work | |||
Property / cites work: Fast Runge-Kutta methods for nonlinear convolution systems of Volterra integral equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Commutators of Singular Integrals and Bilinear Singular Integrals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4338833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A fast directional algorithm for high frequency acoustic scattering in two dimensions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A theory of pseudoskeleton approximations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Numerical Solution of Nonlinear Volterra Convolution Equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Convolution for Nonreflecting Boundary Conditions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast and Oblivious Convolution Quadrature / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Introduction to Numerical Analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sparse Fourier Transform via Butterfly Algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Computation of Partial Fourier Transforms / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 08:50, 5 July 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
0 references