Superfast Fourier transform using QTT approximation

DOI10.1007/s00041-012-9227-4zbMath1260.65114OpenAlexW1975720704MaRDI QIDQ1759431

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

Publication date: 20 November 2012

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00041-012-9227-4

zbMATH Keywords

complexityalgorithmsdiscrete Fourier transformquantum Fourier transformCooley-Tukey fast Fourier transform algorithmquantum tensor train formatradix-2 recursion formula

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Multilinear algebra, tensor calculus (15A69)

Related Items

A low-rank approach to the computation of path integrals, Numerical tensor techniques for multidimensional convolution products, Solving phase-field models in the tensor train format to generate microstructures of bicontinuous composites, Møller-Plesset (MP2) energy correction using tensor factorization of the grid-based two-electron integrals, Computation of extreme eigenvalues in higher dimensions using block tensor train format, Tensorized low-rank circulant preconditioners for multilevel Toeplitz linear systems from high-dimensional fractional Riesz equations, A tensor-train accelerated solver for integral equations in complex geometries, Fast iterative solution of the Bethe-Salpeter eigenvalue problem using low-rank and QTT tensor approximation, Fast preconditioned iterative methods for fractional Sturm–Liouville equations, Tensor product approach to modelling epidemics on networks, QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images, Parallel cross interpolation for high-precision calculation of high-dimensional integrals, Tensor Product Approach to Quantum Control, Direct tensor-product solution of one-dimensional elliptic equations with parameter-dependent coefficients, Quasioptimality of maximum-volume cross interpolation of tensors, Grid-based lattice summation of electrostatic potentials by assembled rank-structured tensor approximation, Numerical tensor calculus, Superfast solution of linear convolutional Volterra equations using QTT approximation, Regularized Computation of Approximate Pseudoinverse of Large Matrices Using Low-Rank Tensor Train Decompositions, Tucker tensor analysis of Matérn functions in spatial statistics, Iterative algorithms for the post-processing of high-dimensional data, A Semi-Lagrangian Vlasov Solver in Tensor Train Format, Fast Multidimensional Convolution in Low-Rank Tensor Formats via Cross Approximation, Robust Alternating Direction Implicit Solver in Quantized Tensor Formats for a Three-Dimensional Elliptic PDE, A literature survey of low-rank tensor approximation techniques

Uses Software

• cross2D
• AAFFT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor Decompositions and Applications
• Tensor-Train Decomposition
• TT-cross approximation for multidimensional arrays
• QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images
• Fast and accurate 3D tensor calculation of the Fock operator in a general basis
• Tensorisation of vectors and their efficient convolution
• \(O(d \log N)\)-quantics approximation of \(N\)-\(d\) tensors in high-dimensional numerical modeling
• Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators I. Separable approximation of multi-variate functions
• Tensor decomposition in electronic structure calculations on 3D Cartesian grids
• A new tensor decomposition
• Combinatorial sublinear-time Fourier algorithms
• Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension
• A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing
• Constructive representation of functions in low-rank tensor formats
• Low-rank quadrature-based tensor approximation of the Galerkin projected Newton/Yukawa kernels
• Computation of the Hartree-Fock exchange by the tensor-structured methods
• QTT representation of the Hartree and exchange operators in electronic structure calculations
• Fast evaluation of trigonometric polynomials from hyperbolic crosses
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
• Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity
• Wedderburn Rank Reduction and Krylov Subspace Method for Tensor Approximation. Part 1: Tucker Case
• The Alternating Linear Scheme for Tensor Optimization in the Tensor Train Format
• Approximate multiplication of tensor matrices based on the individual filtering of factors
• Approximation of $2^d\times2^d$ Matrices Using Tensor Decomposition
• QTT approximation of elliptic solution operators in higher dimensions
• Cross approximation in tensor electron density computations
• Numerical Solution of the Hartree–Fock Equation in Multilevel Tensor-Structured Format
• Algebraic Wavelet Transform via Quantics Tensor Train Decomposition
• Tensor Spaces and Numerical Tensor Calculus
• Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
• Verification of the cross 3D algorithm on quantum chemistry data
• Fast Revealing of Mode Ranks of Tensor in Canonical Form
• Multigrid Accelerated Tensor Approximation of Function Related Multidimensional Arrays
• Quantum algorithms: entanglement–enhanced information processing
• The Discrete Cosine Transform
• Low-Rank Tensor Structure of Solutions to Elliptic Problems with Jumping Coefficients
• Low-Rank Explicit QTT Representation of the Laplace Operator and Its Inverse
• Fast Solution of Parabolic Problems in the Tensor Train/Quantized Tensor Train Format with Initial Application to the Fokker--Planck Equation
• Fast truncation of mode ranks for bilinear tensor operations
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Nearly optimal sparse fourier transform