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

作者：Khoromskij B N^*

来源：Constructive Approximation, 2011, 34(2): 257-280.

DOI：10.1007/s00365-011-9131-1

• FEM
• High-dimensional problems
• Material sciences
• Matrix-valued functions
• Quantics folding of vectors
• Rank-structured tensor approximation
• Stochastic modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,N}⊗d, or briefly N-d tensors of size Nd, and to the respective discretized differential-integral operators in ℝd. As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss-Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε-1)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N-α), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog 2ε-1). From numerical examples presented here, 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 finite element method/boundary element method (FEM/BEM). The tool apparently works.