Superfast Fourier transform using QTT approximation (Q1759431): Difference between revisions

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

Revision as of 21:27, 5 July 2024

scientific article
Language Label Description Also known as
English
Superfast Fourier transform using QTT approximation
scientific article

    Statements

    Superfast Fourier transform using QTT approximation (English)
    0 references
    20 November 2012
    0 references
    Algorithms for the discrete Fourier transform of one- and high-dimensional data represented or approximated in the quantum tensor train (QTT) format are proposed. The approach is based on a radix-2 recursion formula which reduces the Fourier transform to the one of half size and lies behind the well-known Cooley-Tukey fast-Fourier transform (FFT) algorithm. Each step of the proposed QTT-FFT algorithm includes an approximation to reduce the storage size of the intermediate vectors adaptively to the prescribed level of accuracy. The complexity of \(m\)-dimensional \(n\times n\times\dots\times n\) transform with \(n=2^d\) is bounded by \(O(md^2R^3)\), where \(R\) is the maximum QTT-rank of the input, all intermediate vectors and output of the QTT-FFT algorithm. For the vectors with moderate \(R\) and large \(n\) and \(m\) the proposed algorithm outperforms the \(O(n^m\log n)\) fast Fourier transform algorithm and has asymptotically the same log-squared complexity as the superfast quantum Fourier transform algorithm. The authors compare the proposed method with the sparse Fourier transform algorithm.
    0 references
    algorithms
    0 references
    discrete Fourier transform
    0 references
    radix-2 recursion formula
    0 references
    Cooley-Tukey fast Fourier transform algorithm
    0 references
    complexity
    0 references
    quantum Fourier transform
    0 references
    quantum tensor train format
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers