tailieunhanh - Numerical tensor techniques for multidimensional convolution products

In order to treat high-dimensional problems, one has to find data-sparse representations. Starting with a six-dimensional problem, we first introduce the low-rank approximation of matrices. One purpose is the reduction of memory requirements, another advantage is that now vector operations instead of matrix operations can be applied. | Vietnam Journal of Mathematics (2019) 47:69–92 Numerical Tensor Techniques for Multidimensional Convolution Products Wolfgang Hackbusch1 Received: 23 August 2017 / Accepted: 9 March 2018 / Published online: 5 September 2018 © The Author(s) 2018 Abstract In order to treat high-dimensional problems, one has to find data-sparse representations. Starting with a six-dimensional problem, we first introduce the low-rank approximation of matrices. One purpose is the reduction of memory requirements, another advantage is that now vector operations instead of matrix operations can be applied. In the considered problem, the vectors correspond to grid functions defined on a three-dimensional grid. This leads to the next separation: these grid functions are tensors in Rn ⊗ Rn ⊗ Rn and can be represented by the hierarchical tensor format. Typical operations as the Hadamard product and the convolution are now reduced to operations between Rn vectors. Standard algorithms for operations with vectors from Rn are of order O(n) or larger. The tensorisation method is a representation method introducing additional data-sparsity. In many cases, the data size can be reduced from O(n) to O(log n). Even more important, operations as the convolution can be performed with a cost corresponding to these data sizes. Keywords Tensorisation · Convolution · Tensor representation · Hierarchical representation Mathematics Subject Classification (2010) 15A69 · 15A99 · 44A35 · 65F99 · 65T99 1 Introduction In this paper, we recapitulate the numerical techniques which are needed to handle highdimensional problems. As discussion starter, we use an example from quantum chemistry. The following function h is to be determined: h(x, z) = f (x, x − y) g(y, z) dy (x, z ∈ R3 ) (1) R3 In memory of Eberhard Zeidler. Wolfgang Hackbusch wh@ 1 Max-Planck-Institut Mathematik in den Naturwissenschaften, Inselstr. 22, D-04103, Leipzig, Germany W. .