19 Adaptive Interpolation, TT-Decomposition and Sparse …
277
F =
r
i=1
⎛
⎜
⎜
⎝
u i (x 0 )
u i (x 1 )
. . .
u i (x p )
⎞
⎟
⎟
⎠
v i (y 0 ) v i (y 1 ) . . . v i (y p )
= U V.
Important fact is the following. If the matrix has a rank r, then if knowing rows r
and columns r, we can completely restore the entire matrix. A number of questions
arise. Which rows and columns to take? How to determine the rank of r? Of course,
without any information about function F, it is impossible to answer these questions without calculating all the elements of the matrix; therefore, to some extent,
all algorithms are heuristic. In practice, the transition from exact decomposition to
approximation is performed with some accuracy ε:
F − U V < ε.
A number of works dedicated to methods for constructing such decomposition
are known [8, 9]. The following methods such as skeletal decomposition, cross
approximation, and low-rank approximation are found in the literature.
In its simplest form, the pseudo-code of the algorithm is presented in Fig. 19.2.
The input is a matrix F of size n × m, as well as, the required absolute accuracy
of the approximation eps. The output is two matrices U and V of size n × r and r
× m respectively, where r is the matrix rank, which is determined in the process of
computing. The algorithm begins by selecting an arbitrary column (for example, with
a number m/2). Next, the zeroing of a certain column or a certain row is alternately
performed until the module of the maximum element becomes smaller than eps.
Consider the ODE system:
⎧
⎨
⎩
x
= y, y
= − sin(x),
x(0) = x 0 ∈ [−1.0, 1.0],
y(0) = y 0 ∈ [0.0, 1.0].
A regular grid is introduced over the set formed by the interval initial conditions:
x
i
0 = −1 + 0.02i, y
j
0 = 0.01 j, 0 ≤ i ≤ 100, 0 ≤ j ≤ 100. Let the matrix F
101×101
consist of the values of the phase variable x at a time t = 30:
f i, j = x i, j (30) | x 0 = −1 + 0.02i, y 0 = 0.01 j.
In Fig. 19.3, lines show those rows and columns that were needed in the process
of constructing the decomposition. If the entire matrix consists of 10,201 elements,
then it was necessary to calculate a total of 2101 elements (11 rows and 11 columns:
2101 = 2 × 11 × 101–11 × 11) that is a fifth of the entire matrix to construct an
approximation with eps = 10
−5 .
If we assume that all elements of the matrix are known, then the question of the
existence of the decomposition and its finding is resolved: the SVD decomposition
277
F =
r
i=1
⎛
⎜
⎜
⎝
u i (x 0 )
u i (x 1 )
. . .
u i (x p )
⎞
⎟
⎟
⎠
v i (y 0 ) v i (y 1 ) . . . v i (y p )
= U V.
Important fact is the following. If the matrix has a rank r, then if knowing rows r
and columns r, we can completely restore the entire matrix. A number of questions
arise. Which rows and columns to take? How to determine the rank of r? Of course,
without any information about function F, it is impossible to answer these questions without calculating all the elements of the matrix; therefore, to some extent,
all algorithms are heuristic. In practice, the transition from exact decomposition to
approximation is performed with some accuracy ε:
F − U V < ε.
A number of works dedicated to methods for constructing such decomposition
are known [8, 9]. The following methods such as skeletal decomposition, cross
approximation, and low-rank approximation are found in the literature.
In its simplest form, the pseudo-code of the algorithm is presented in Fig. 19.2.
The input is a matrix F of size n × m, as well as, the required absolute accuracy
of the approximation eps. The output is two matrices U and V of size n × r and r
× m respectively, where r is the matrix rank, which is determined in the process of
computing. The algorithm begins by selecting an arbitrary column (for example, with
a number m/2). Next, the zeroing of a certain column or a certain row is alternately
performed until the module of the maximum element becomes smaller than eps.
Consider the ODE system:
⎧
⎨
⎩
x
= y, y
= − sin(x),
x(0) = x 0 ∈ [−1.0, 1.0],
y(0) = y 0 ∈ [0.0, 1.0].
A regular grid is introduced over the set formed by the interval initial conditions:
x
i
0 = −1 + 0.02i, y
j
0 = 0.01 j, 0 ≤ i ≤ 100, 0 ≤ j ≤ 100. Let the matrix F
101×101
consist of the values of the phase variable x at a time t = 30:
f i, j = x i, j (30) | x 0 = −1 + 0.02i, y 0 = 0.01 j.
In Fig. 19.3, lines show those rows and columns that were needed in the process
of constructing the decomposition. If the entire matrix consists of 10,201 elements,
then it was necessary to calculate a total of 2101 elements (11 rows and 11 columns:
2101 = 2 × 11 × 101–11 × 11) that is a fifth of the entire matrix to construct an
approximation with eps = 10
−5 .
If we assume that all elements of the matrix are known, then the question of the
existence of the decomposition and its finding is resolved: the SVD decomposition