272
A. Yu. Morozov and D. L. Reviznikov
Often, the complexity of existing methods is exponential in relation to the number
of interval parameters. In this chapter, the adaptive interpolation algorithm [2–4]
for modeling dynamic systems with interval parameters and approaches directed to
reducing the curse of dimensionality are considered The main assumption, on which
these approaches are based, is that not all interval parameters make a significant
contribution to solve the problem. As a result, during the operation of the algorithm,
data structures that have hidden dependencies and redundancy appear. Eliminating
these structures can significantly reduce computational complexity.
The main idea of the adaptive interpolation algorithm is to build an adaptive hierarchical grid based on the kd-tree, in which each cell contains an interpolation grid,
over the set formed by the interval initial conditions and parameters of the problem.
For each time moment, an adaptive reconstruction of the partition is performed
depending on the features of the solution. The result of the algorithm at each step
is a piecewise polynomial function that interpolates the dependence of the solution
on the parameter values with a given accuracy. Each vertex of a tree corresponds to
a multidimensional array (or, according to the terminology in [5, 6], a tensor), for
storage of which various effective representations can be used, under the assumption
that the data have redundancy.
One of the effective representations of tensors is Tensor Train (TT) decomposition
[5], which allows one to significantly reduce the amount of stored data in practice.
This decomposition can be constructed using TT-cross algorithm [6] without calculating all the elements of the tensor. An important property is that all arithmetic (and
not only) operations on tensors can be performed in this form.
The sparse grid method appeared in the 1960s [7] for solving multi-parameter
problems in economics. It is used to interpolate the functions of many variables.
Interpolation on sparse grids requires a significantly smaller number of nodes than
conventional interpolation on a full grid. In this approach, instead of one dense grid,
a linear combination of several sparse grids is used.
The chapter has the following organization. In Sect. 19.2, an interval statement of
the Cauchy problem for a system of ODEs is presented. Section 19.3 is devoted to the
adaptive interpolation algorithm for solving dynamic systems with interval parameters. In Sect. 19.4, we describe the problem of large dimensions and outline a way to
a solution. In Sect. 19.5, the cross approximation of matrices is considered, which is
the basis of tensor trains decomposition described in Sect. 19.6. This approach allows
us to effectively deal with large dimensions. A modification of the adaptive interpolation algorithm using tensor trains is given in Sect. 19.7. Section 19.8 of the chapter
is devoted to another approach to solving the problem of large dimensions—sparse
grids. In Sect. 19.9, the main results are formulated.
19.2 Formulation of the Problem
We consider the Cauchy problem with interval initial conditions in the form of a
system (Eq. 19.1).
A. Yu. Morozov and D. L. Reviznikov
Often, the complexity of existing methods is exponential in relation to the number
of interval parameters. In this chapter, the adaptive interpolation algorithm [2–4]
for modeling dynamic systems with interval parameters and approaches directed to
reducing the curse of dimensionality are considered The main assumption, on which
these approaches are based, is that not all interval parameters make a significant
contribution to solve the problem. As a result, during the operation of the algorithm,
data structures that have hidden dependencies and redundancy appear. Eliminating
these structures can significantly reduce computational complexity.
The main idea of the adaptive interpolation algorithm is to build an adaptive hierarchical grid based on the kd-tree, in which each cell contains an interpolation grid,
over the set formed by the interval initial conditions and parameters of the problem.
For each time moment, an adaptive reconstruction of the partition is performed
depending on the features of the solution. The result of the algorithm at each step
is a piecewise polynomial function that interpolates the dependence of the solution
on the parameter values with a given accuracy. Each vertex of a tree corresponds to
a multidimensional array (or, according to the terminology in [5, 6], a tensor), for
storage of which various effective representations can be used, under the assumption
that the data have redundancy.
One of the effective representations of tensors is Tensor Train (TT) decomposition
[5], which allows one to significantly reduce the amount of stored data in practice.
This decomposition can be constructed using TT-cross algorithm [6] without calculating all the elements of the tensor. An important property is that all arithmetic (and
not only) operations on tensors can be performed in this form.
The sparse grid method appeared in the 1960s [7] for solving multi-parameter
problems in economics. It is used to interpolate the functions of many variables.
Interpolation on sparse grids requires a significantly smaller number of nodes than
conventional interpolation on a full grid. In this approach, instead of one dense grid,
a linear combination of several sparse grids is used.
The chapter has the following organization. In Sect. 19.2, an interval statement of
the Cauchy problem for a system of ODEs is presented. Section 19.3 is devoted to the
adaptive interpolation algorithm for solving dynamic systems with interval parameters. In Sect. 19.4, we describe the problem of large dimensions and outline a way to
a solution. In Sect. 19.5, the cross approximation of matrices is considered, which is
the basis of tensor trains decomposition described in Sect. 19.6. This approach allows
us to effectively deal with large dimensions. A modification of the adaptive interpolation algorithm using tensor trains is given in Sect. 19.7. Section 19.8 of the chapter
is devoted to another approach to solving the problem of large dimensions—sparse
grids. In Sect. 19.9, the main results are formulated.
19.2 Formulation of the Problem
We consider the Cauchy problem with interval initial conditions in the form of a
system (Eq. 19.1).