Superfast Fourier Transform Using QTT Approximation

By Sergey V. Dolgov, Boris N. Khoromskij, Dmitry V. Savostyanov. 2012

89 citations recorded by the source corpus.

Subfields: Computational Mathematics, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

1. Boris N. Khoromskij
2. Sergey V. Dolgov
3. Ivan V. Oseledets
4. Dmitry V. Savostyanov
5. Venera Khoromskaia
6. V. Dolgov
7. Reinhold Schneider
8. Christine Tobler

In Computational Mechanics

1. Boris N. Khoromskij
2. Sergey V. Dolgov
3. Dmitry V. Savostyanov
4. Ivan V. Oseledets
5. V. Dolgov
6. Venera Khoromskaia
7. Reinhold Schneider
8. Andrzej S. Cichocki

In Signal Processing

1. Boris N. Khoromskij
2. Sergey V. Dolgov
3. Dmitry V. Savostyanov
4. Venera Khoromskaia
5. V. Dolgov
6. Qibin Zhao
7. Reinhold Schneider
8. Ivan V. Oseledets

Citations in the corpus

• A literature survey of low‐rank tensor approximation techniques (2013, neutral): “QTT has been applied to the solution of PDEs and eigenvalue problems [144, 154, 162], evaluation of boundary integrals in BEM [164], convolution [107] and the FFT [63, 108, 230].”
• Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions (2013, unknown): “, algorithms for the solution of linear systems [51, 21, 47, 38, 34, 31, 39, 2, 8, 4, 3], partial eigenproblems [41, 40, 24, 20], and Fourier transform [11].”
• ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS∗ (2014, methodology): “, algorithms for the solution of linear systems [51, 21, 47, 38, 34, 31, 39, 2, 8, 4, 3], partial eigenproblems [41, 40, 24, 20], and Fourier transform [11].”
• Tensor Ring Decomposition (2016, methodology): “At the same time, new tensor formats have been proposed, e.g. the quantized tensor train (QTT) [42], [43] and the QTT-Tucker [44], which have been also applied to large-scale optimization problems [41], [45], [46].”
• Fast Solution of Parabolic Problems in the Tensor Train/Quantized Tensor Train Format with Initial Application to the Fokker-Planck Equation (2012, methodology): “There are also algorithms which exploit the binary QTTstructure heavily, such as the super-fast data-sparse Fourier transform [9].”
• Tensor-product approach to global time-space-parametric discretization of chemical master equation (2012, methodology): “One may use also the diagrammatic notations, introduced by White and then used in [28, 37, 38] as especially convenient to demonstrate tensor networks: a multiindex array (block) is represented by a rectangle, its indices by lines, and if a line connects two rectangles, the new array is computed by ”
• TT-GMRES: on solution to a linear system in the structured tensor format (2012, unknown): “In practice this formula can be accelerated (giving the complexity O(n logn)) by using Fast Trigonometric transforms (in our case of Dirichlet boundary conditions the appropriate transform is DST-I) with all TT ranks equal to 1 [32], and compressing only the diagonal matrix with inversed eigenvalues”
• Tensor-Structured Factorized Calculation of Two-Electron Integrals in a General Basis (2013, background): “We point out, however, that the super-fast 1D QTT-convolution and QTT-FFT of complexity O(log n) proposed in [10, 18] outperform the full-grid 1D-FFT based tensor algorithm [25] only in asymptotical regime, i.”