A fast algorithm for multilinear operators

详细信息	查看全文 | 推荐本文 |

• 作者：Haizhao Yang^a ; Lexing Ying^b ; ^{lexing@math.utexas.edu}
• 关键词：Multilinear operators ; Fast Fourier transform ; Multiscale decomposition ; Low-rank approximation
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2012
• 期刊代码：119_10635203
• 类别：cp
• 出版时间：July, 2012
• 卷：33
• 期：1
• 页码：148-158
• 文件大小：232 K

摘要

This paper introduces a fast algorithm for computing multilinear integrals which are defined through Fourier multipliers. The algorithm is based on generating a hierarchical decomposition of the summation domain into squares, constructing a low-rank approximation for the multiplier function within each square, and applying an FFT based fast convolution algorithm for the computation associated with each square. The resulting algorithm is accurate and has a linear complexity, up to logarithmic factors, with respect to the number of the unknowns in the input functions. Numerical results are presented to demonstrate the properties of this algorithm.