Preprint 55/2009

O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 07. Sep. 2009 (revised version: August 2010)
Pages: 23
published in: Constructive approximation, 34 (2011) 2, p. 257-280 
DOI number (of the published article): 10.1007/s00365-011-9131-1
MSC-Numbers: 65F30, 65F50, 65N35, 65F10
Keywords and phrases: high-dimensional problems, quantics folding of vectors, rank structured tensor approximation, fem, matrix valued functions, material sciences, stochastic modeling
Download full preprint: PDF (289 kB)

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high dimensional applications. We describe the multi-folding or quantics based tensor approximation method of formula13-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set formula15, or briefly N-d tensors of size formula21, and to the respective discretised differential-integral operators in formula23. As the basic approximation result, we prove that complex exponential sampled on equispaced grid has quantics rank 1. Moreover, the Chebyshev polynomial sampled over Chebyshev Gauss-Lobatto grid, has separation rank 2 in quantics tensor format, while for the polynomial of degree m the respective quantics rank is at most m+1. For N-d tensors generated by certain analytic functions, we give the constructive proof on the formula37-complexity bound for their approximation by low rank 2-formula41 quantics tensors up to the accuracy formula43. In the case formula45, formula47, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity formula51. >From numerics presented, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional FEM/BEM--the tool apparently works.

19.04.2013, 01:42