Preliminary list of abstracts

Note: We are using the fantastic MathJax JavaScript library to typeset the mathematics on this web page. You can right-click on a formula to zoom in or to select the rendering engine you like (all under 'Settings'). Under Firefox the default renderer turns out to be MathML (which is quick), but you might prefer the HTML-CSS renderer for more faithful LaTeX rendering. If you encounter any problems with this setup: then please email us!

Click here to go back to the list of abstracts.

TT-approach to the solution of high-dimensional problems
Keywords: Tensor trains; High-dimensional approximations
Wed, 15:45--16:10
  • Oseledets, Ivan (Institute of Numerical Mathematics, Russian Academy of Sciences, Russia)

Solution of high-dimensional problems requires low-parametric representation of multivariate functions and their discrete representations – multidimensional arrays, or tensors. By tensor we mean an array with $d$-indices, $A(i_1,\ldots,i_d)$ Such tensors appear naturally from discretization of multivariate function on a tensor grid. I will discuss, how to approximate such tensors by tensors in Tensor Train format, or simply TT-format. Tensor $\mathbf{A}$ is said to be in the TT-format, if $$A(i_1,\ldots,i_d) = G_1(i_1) G_2(i_2) \ldots G_d(i_d),$$ where $G_k(i_k)$ is an $r_{k-1} \times r_k$ matrix for each fixed $i_k$, and $r_0 = r_d$ to make matrix-by-matrix product a number. Numbers $r_k$ are called TT-ranks TT-format comes with fast linear algebra: addition, matrix-by-vector multiplication, etc, thus it looks promising for the approximation of high-dimensional tensors. The result of such operations is also in the TT-format, but the rank may grow, i.e. certain rounding, i.e. approximation of a given tensor by another one with smaller TT-ranks but with prescribed accuracy. Such procedure can be implemented by a sequence of QR and SVD decompositions, is fast and robust. With the help of it one can already implement standard iterative methods for the solution of high-dimensional equations and eigenvalue problems.

TT-format is based on the matrix SVD, which is connected with low-rank approximation. Low-rank approximation, in turn, is connected to the so-called skeleton decomposition, which is able to reconstruct low-rank matrix form $r$ its rows and columns, where $r$ is the rank. Effective algorithms for the computation of the skeleton decomposition are based on the cross algorithms. TT-format has direct generalization of this beautiful formula: a rank-$r$ tensor can be recovered exactly from $dnr^2$ entries of it. Obvious applications are black-box approximation of "difficult" multivariate functions, since TT-interpolation is a nonlinear interpolation scheme, which is based on the assumption that separable approximation to the function exists. However, such approximation, also known as canonical, is not computable numerically, while TT-approximant is computable.

There are several important applications for tensor method: approximation of multiparametric functions and the solution of stochastic PDEs (here comparison with QMC methods is surely very important), approximation of potential energy surfaces (PES) in quantum chemisty, solution of high-dimensional eigenvalue problem coming from second quantization approach to the FCI method, solution of molecular Schroedinger equation in quantum molecular dynamics. These are "truly" high-dimensional problems. A major breakthrough of recent years is that high-dimensional approximation can be applied to formally low-dimensional objects through quantization (tensorization). The simplest way to illustrate this approach is to consider a univariate function, $f(x)$, on a uniform grid with $2^d$ points. Then, vector of values on such grid can be considered as $d$-dimensional tensor with mode sizes equal to $2$. Thanks to the stability of the TT-format, TT-decomposition of such tensor can be computed fast for $d \leq 24$ even on a laptop, and numerical experiments show, that for many functions QTT-ranks (QTT stands for Quantized TT format) are really small. The storage of the QTT-representation is logarithmic in the number of grid points. Such technique can be generalized to higher dimensions. QTT-format has deep connection with wavelets and non-stationary subdivision schemes, and I will illustrate that by examples.

There exists a MATLAB Toolbox that implements several discussed algorithms – TT-Toolbox (current version 2.0). It can be obtained from the author or at the website http://spring.inm.ras.ru/osel.