19 Adaptive Interpolation, TT-Decomposition and Sparse …
275
Fig. 19.1 Illustration of the working algorithm
error =
max
(ˆ x 0 , x k+1 )∈X
k+1
0
x
k+1
− P
k+1
(ˆ x
0
)
.
The adaptive interpolation algorithm consists of three elements: transferring decisions to the next time layer, estimating the interpolation error for each vertex, and
splitting the vertices. The considering approach is invariant in relation to specific
implementations. It is not necessary, for example, to store explicitly multidimensional arrays at each vertex of the kd-tree, instead, it is enough to store only their
TT-decomposition and implement all the necessary actions within TT-format. Also,
it is not necessary to use the dense regular grids.
19.4 Large Dimensions
The described adaptive interpolation algorithm with all its advantages (universality,
robustness, accuracy, and the possibility of parallelization) has one significant drawback: with an increase in the number of interval parameters, its complexity grows
exponentially. Each vertex of the kd-tree contains a grid with the number of nodes
( p +1)
m , where p is the degree of interpolation polynomial in each dimension and m
is the number of interval initial conditions. Already with the parameters p = 4 and
275
Fig. 19.1 Illustration of the working algorithm
error =
max
(ˆ x 0 , x k+1 )∈X
k+1
0
x
k+1
− P
k+1
(ˆ x
0
)
.
The adaptive interpolation algorithm consists of three elements: transferring decisions to the next time layer, estimating the interpolation error for each vertex, and
splitting the vertices. The considering approach is invariant in relation to specific
implementations. It is not necessary, for example, to store explicitly multidimensional arrays at each vertex of the kd-tree, instead, it is enough to store only their
TT-decomposition and implement all the necessary actions within TT-format. Also,
it is not necessary to use the dense regular grids.
19.4 Large Dimensions
The described adaptive interpolation algorithm with all its advantages (universality,
robustness, accuracy, and the possibility of parallelization) has one significant drawback: with an increase in the number of interval parameters, its complexity grows
exponentially. Each vertex of the kd-tree contains a grid with the number of nodes
( p +1)
m , where p is the degree of interpolation polynomial in each dimension and m
is the number of interval initial conditions. Already with the parameters p = 4 and