Tensor numerical methods of logarithmic complexity for multi-dimensional applications

Boris N. Khoromskij
Max-Planck-Institute for Mathematics in the Sciences, Leipzig, Allemagne
bokh@mis.mpg.de
Lundi 26 Novembre 2012, 11^h00
bibliothèque LCT, tour 12 - 13, 4e étage

Tensor numerical methods provide the efficient representation of multivariate functions and operators on large n^×d -grids, that allows the solution of d-dimensional PDEs with linear complexity scaling in the dimension, O(dn). Modern methods of separable approximation combine the canonical, Tucker, as well as the general matrix product state (MPS) formats in the framework of DMRG-MPS optimization methods in FCI calculations in quantum chemistry.
The recent quantized tensor train (QTT) approximation [1] is proven to provide the logarithmic datacompression for a wide class of functions and operators [1, 2]. It makes possible to solve highdimensional steady-state and dynamical problems in quantized tensor spaces with the log-volume complexity scaling in the full-grid size, O(d log n), instead of O(n^d).
We show how the approximation in quantized tensor spaces applies to hard problems arising in electronic structure calculations, such as multi-dimensional convolution [3], many-electron integrals [4] and FFT(d) [5]. The QTT method also applies to high-dimensional time-dependent models [6, 7], for example, to molecular Schrödinger, Fokker-Planck and master equations. Numerical tests indicate the logarithmic complexity of the QTT tensor methods with respect to both spacial and temporal grid-sizes.

http://personal-homepages.mis.mpg.de/bokh

[1] B. N. Khoromskij, Constr. Approx. 2011, 34, 257.
[2] B. N. Khoromskij, Lecture Notes, Preprint 06-2011, University of Zuerich, Institute of Mathematics, 2011, pp. 1-238.
http://www.math.uzh.ch/fileadmin/math/preprints/06-11.pdf.
[3] B. N. Khoromskij , J. Comp. Appl. Math. 2010, 234, 3122.
[4] V. Khoromskaia, B. N. Khoromskij, and R. Schneider, Preprint 29/2012, MPI MIS, Leipzig, 2012 (SIAM J. Sci. Comput., submitted).
[5] S. V. Dolgov, B. N. Khoromskij, and D. Savostianov, J. Fourier Anal. Appl., 2012, 18, 915.
[6] B. N. Khoromskij and I. Oseledets , Preprint 68/2010, MPI MIS, Leipzig, 2010 (Math. Comp., submitted).
[7] S. V. Dolgov and B. N. Khoromskij , Preprint 68/2012, MPI MIS, Leipzig, 2012.