Superfast Fourier transform using QTT approximation
From MaRDI portal
Publication:1759431
DOI10.1007/s00041-012-9227-4zbMath1260.65114MaRDI 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
complexity; algorithms; discrete Fourier transform; quantum Fourier transform; Cooley-Tukey fast Fourier transform algorithm; quantum tensor train format; radix-2 recursion formula
65T50: Numerical methods for discrete and fast Fourier transforms
65Y20: Complexity and performance of numerical algorithms
15A69: Multilinear algebra, tensor calculus
Related Items
Numerical tensor calculus, Fast Multidimensional Convolution in Low-Rank Tensor Formats via Cross Approximation, A Semi-Lagrangian Vlasov Solver in Tensor Train Format, Robust Alternating Direction Implicit Solver in Quantized Tensor Formats for a Three-Dimensional Elliptic PDE, Fast preconditioned iterative methods for fractional Sturm–Liouville equations, Tensor product approach to modelling epidemics on networks, 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, QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images, Grid-based lattice summation of electrostatic potentials by assembled rank-structured tensor approximation, Iterative algorithms for the post-processing of high-dimensional data, 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, Direct tensor-product solution of one-dimensional elliptic equations with parameter-dependent coefficients, Solving phase-field models in the tensor train format to generate microstructures of bicontinuous composites, Quasioptimality of maximum-volume cross interpolation of tensors, Tucker tensor analysis of Matérn functions in spatial statistics, A low-rank approach to the computation of path integrals, Superfast solution of linear convolutional Volterra equations using QTT approximation, Numerical tensor techniques for multidimensional convolution products, Tensorized low-rank circulant preconditioners for multilevel Toeplitz linear systems from high-dimensional fractional Riesz equations, Parallel cross interpolation for high-precision calculation of high-dimensional integrals, Regularized Computation of Approximate Pseudoinverse of Large Matrices Using Low-Rank Tensor Train Decompositions, A literature survey of low-rank tensor approximation techniques, Tensor Product Approach to Quantum Control
Uses Software
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