280
A. Yu. Morozov and D. L. Reviznikov
elements of the tensor is in replacing SVD-decomposition with decomposition with
a lower computational cost which does not require full knowledge of all elements of
the tensor.
In addition to not being subject to the curse of dimensionality, an important property of TT-decomposition is that most arithmetic operations, and not only arithmetic,
can be performed on tensors, being in this format. This is, for example, finding
the sum of all elements, determination of maximum/minimum, element-wise addition/subtraction/multiplication/division of two tensors, and so on. There are several
implementations of TT-decomposition. We designed the main library ttpy using
Python programming language. This library has all the necessary operations and
methods for working with tensors in TT-format.
With the benefit of such tensors’ representation, it became possible to work on
ordinary computers with objects containing more elements than atoms in the Solar
system. Of course, the important point is that the source data have tremendous
redundancy, which is eliminated by this method.
19.7 Adaptive Interpolation Algorithm
and TT-Decomposition
A multidimensional array (tensor) is stored at each vertex of the tree. The number of
elements in the tensor depends on the number of interval parameters ( p + 1)
m . The
main idea of practical improvement of this situation is to find TT-decomposition that
can be constructed using the TT-cross algorithm without calculating all the elements
of the tensor.
The adaptive interpolation algorithm conditionally consists of three actions: transferring all the solutions contained in the vertices of the kd-tree to the next time layer,
interpolating along the grid, and splitting the vertex into two. The first action within
each vertex can be considered as constructing a tensor consisting of the values of
some function. This action can be effectively performed using TT-cross algorithm.
The interpolation operation is reduced to elementwise multiplication of two tensors,
one of which is composed of the values of the basic Lagrange polynomials, and
the second is composed of the values of the interpolated function, followed by the
summation of all elements. If we assume that the split of vertices is always performed
by a hyperplane perpendicular to one of the coordinate axes, then one-dimensional
interpolation is used to construct new vertices. In general, all the actions that make
up the algorithm can be represented as compositions of several operations available
in TT-format.
In the original version of the algorithm, the order p and, accordingly, the size of
the interpolation grid was determined from specific considerations regarding stability
and computational complexity. Here, in some cases, it is advisable to create a grid,
where there will be more nodes than it is required for a given order p. Splitting a
A. Yu. Morozov and D. L. Reviznikov
elements of the tensor is in replacing SVD-decomposition with decomposition with
a lower computational cost which does not require full knowledge of all elements of
the tensor.
In addition to not being subject to the curse of dimensionality, an important property of TT-decomposition is that most arithmetic operations, and not only arithmetic,
can be performed on tensors, being in this format. This is, for example, finding
the sum of all elements, determination of maximum/minimum, element-wise addition/subtraction/multiplication/division of two tensors, and so on. There are several
implementations of TT-decomposition. We designed the main library ttpy using
Python programming language. This library has all the necessary operations and
methods for working with tensors in TT-format.
With the benefit of such tensors’ representation, it became possible to work on
ordinary computers with objects containing more elements than atoms in the Solar
system. Of course, the important point is that the source data have tremendous
redundancy, which is eliminated by this method.
19.7 Adaptive Interpolation Algorithm
and TT-Decomposition
A multidimensional array (tensor) is stored at each vertex of the tree. The number of
elements in the tensor depends on the number of interval parameters ( p + 1)
m . The
main idea of practical improvement of this situation is to find TT-decomposition that
can be constructed using the TT-cross algorithm without calculating all the elements
of the tensor.
The adaptive interpolation algorithm conditionally consists of three actions: transferring all the solutions contained in the vertices of the kd-tree to the next time layer,
interpolating along the grid, and splitting the vertex into two. The first action within
each vertex can be considered as constructing a tensor consisting of the values of
some function. This action can be effectively performed using TT-cross algorithm.
The interpolation operation is reduced to elementwise multiplication of two tensors,
one of which is composed of the values of the basic Lagrange polynomials, and
the second is composed of the values of the interpolated function, followed by the
summation of all elements. If we assume that the split of vertices is always performed
by a hyperplane perpendicular to one of the coordinate axes, then one-dimensional
interpolation is used to construct new vertices. In general, all the actions that make
up the algorithm can be represented as compositions of several operations available
in TT-format.
In the original version of the algorithm, the order p and, accordingly, the size of
the interpolation grid was determined from specific considerations regarding stability
and computational complexity. Here, in some cases, it is advisable to create a grid,
where there will be more nodes than it is required for a given order p. Splitting a