# Appendices

## A Preconditioner parameter study

In this first appendix the preconditioner firstly introduced in (24) is further investigated. In particular we focus on the effect on the convergence of the number of addends and on the compression accuracy chosen to compute it. As in Subsection 2.2, let $M \in \mathbb{R}^{(n \times n) \times \cdots \times (n \times n)}$ be the $d$-order TT-matrix that approximate the inverse of the discrete Laplacian $\Delta_d$, cf. [11, 12], defined as

$$M = \sum_{k=-q}^{q} c_k \exp(-t_k \Delta_1) \otimes \cdots \otimes \exp(-t_k \Delta_1)$$

where $c_k = \eta t_k$, $t_k = \exp(k\eta)$ and $\eta = \pi/q$. As already mentioned, since $M$ is a sum of tensors, its TT-rank is greater or equal than $2q + 1$. The magnitude of TT-ranks of $M$ conditions the TT-ranks of the Krylov basis vectors and of the final solution. Therefore it is convenient to keep $M$ TT-rank significantly small, either by reducing the number of addends, i.e., choosing a low value for $q$, or by compressing $M$ with an accuracy $\tau$. With the help of a Poisson problem, we illustrate the trade off between number of addends and compression accuracy which leads to the optimal convergence. We consider the Poisson problem, written as

$$\begin{cases} -\Delta u = 1 & \text{in } \Omega = [0, 1]^3 \\ u = 0 & \text{in } \partial\Omega \end{cases}$$

so that the effect of the preconditioner is as much evident as possible. Let $-\Delta_3$ be the discretization of the Laplacian operator over a grid of $n = 63$ points per mode. Similarly let $b \in \mathbb{R}^{n \times n \times n}$ be a tensor with all the entries equal to 1. Then, setting $A = -\Delta_3$, TT-GMRES solves the tensor linear system $Au = b$, preconditioning it on the right as

$$AM_{q,\tau}t = b$$

for $q \in \{2, 8, 16, 32, 64\}$ and $\tau \in \{10^{-2}, 10^{-8}\}$. The parameters of TT-GMRES are tolerance $\epsilon = 10^{-16}$, rounding accuracy $\delta = 10^{-5}$, dimension of the Krylov space $m = 25$ and a maximum of 2 restart. We set TT-GMRES tolerance equal to the machine precision so that the algorithm performs all the 50 iterations. In Table 1, we report the maximal TT-rank of $M_{q,\tau}$ and the $\|AM_{q,\tau}\|_2$ rounded at the third digits for all the combinations of $q$ and $\tau$. Remark that fixed a value for $q$ the L2 norm of the preconditioned linear system is the same up to the third digits for both the values of $\tau$. This seems to suggest that the number of addends plays a key role in determining the quality of the preconditioner, while the rounding accuracy $\tau$ affects more significantly the TT-rank, removing kind of unnecessary information. Indeed for $\tau = 10^{-2}$ and $q \ge 8$, the maximal value of the TT-rank is always 5, but depending for an increasing number of addends, the L2 norm gets closer to 1. Similarly for $\tau = 10^{-8}$ and $q \ge 32$, the maximal TT-rank is 15 and the rounded L2 norm is equal to 1.

<table><caption>Table 1: Preconditioner properties for grid step $n = 63$.</caption><thead><tr><th rowspan="2">q</th><th colspan="5">τ = 10<sup>-2</sup></th><th colspan="5">τ = 10<sup>-8</sup></th></tr><tr><th>2</th><th>8</th><th>16</th><th>32</th><th>64</th><th>2</th><th>8</th><th>16</th><th>32</th><th>64</th></tr></thead><tbody><tr><td>Max TT-rank of M</td><td>2</td><td>5</td><td>5</td><td>5</td><td>5</td><td>2</td><td>7</td><td>13</td><td>15</td><td>15</td></tr><tr><td>L2 norm of AM<sub>q,τ</sub></td><td>0.012</td><td>0.276</td><td>0.949</td><td>1.00</td><td>1.00</td><td>0.012</td><td>0.276</td><td>0.949</td><td>1.00</td><td>1.00</td></tr></tbody></table>
# Appendices

## A Preconditioner parameter study

In this first appendix the preconditioner firstly introduced in (24) is further investigated. In particular we focus on the effect on the convergence of the number of addends and on the compression accuracy chosen to compute it. As in Subsection 2.2, let $M \in \mathbb{R}^{(n \times n) \times \cdots \times (n \times n)}$ be the $d$-order TT-matrix that approximate the inverse of the discrete Laplacian $\Delta_d$, cf. [10, 11], defined as

$$M = \sum_{k=-q}^{q} c_k \exp(-t_k \Delta_1) \otimes \cdots \otimes \exp(-t_k \Delta_1)$$

where $c_k = \eta t_k$, $t_k = \exp(k\eta)$ and $\eta = \pi/q$. As already mentioned, since $M$ is a sum of tensors, its TT-rank is greater or equal than $2q + 1$. The magnitude of TT-ranks of $M$ conditions the TT-ranks of the Krylov basis vectors and of the final solution. Therefore it is convenient to keep $M$ TT-rank significantly small, either by reducing the number of addends, i.e., choosing a low value for $q$, or by compressing $M$ with an accuracy $\tau$. With the help of a Poisson problem, we illustrate the trade off between number of addends and compression accuracy which leads to the optimal convergence. We consider the Poisson problem, written as

$$\begin{cases} -\Delta u = 1 & \text{in } \Omega = [0, 1]^3 \\ u = 0 & \text{in } \partial\Omega \end{cases}$$

so that the effect of the preconditioner is as much evident as possible. Let $-\Delta_3$ be the discretization of the Laplacian operator over a grid of $n = 63$ points per mode. Similarly let $b \in \mathbb{R}^{n \times n \times n}$ be a tensor with all the entries equal to 1. Then, setting $A = -\Delta_3$, TT-GMRES solves the tensor linear system $Au = b$, preconditioning it on the right as

$$AM_{q,\tau}t = b$$

for $q \in \{2, 8, 16, 32, 64\}$ and $\tau \in \{10^{-2}, 10^{-8}\}$. The parameters of TT-GMRES are tolerance $\epsilon = 10^{-16}$, rounding accuracy $\delta = 10^{-5}$, dimension of the Krylov space $m = 25$ and a maximum of 2 restart. We set TT-GMRES tolerance equal to the machine precision so that the algorithm performs all the 50 iterations. In Table 1, we report the maximal TT-rank of $M_{q,\tau}$ and the $\|AM_{q,\tau}\|_2$ rounded at the third digits for all the combinations of $q$ and $\tau$. Remark that fixed a value for $q$ the L2 norm of the preconditioned linear system is the same up to the third digits for both the values of $\tau$. This seems to suggest that the number of addends plays a key role in determining the quality of the preconditioner, while the rounding accuracy $\tau$ affects more significantly the TT-rank, removing kind of unnecessary information. Indeed for $\tau = 10^{-2}$ and $q \ge 8$, the maximal value of the TT-rank is always 5, but depending for an increasing number of addends, the L2 norm gets closer to 1. Similarly for $\tau = 10^{-8}$ and $q \ge 32$, the maximal TT-rank is 15 and the rounded L2 norm is equal to 1.

<table><caption>Table 1: Preconditioner properties for grid step $n = 63$.</caption><thead><tr><th rowspan="2">q</th><th colspan="5">τ = 10<sup>-2</sup></th><th colspan="5">τ = 10<sup>-8</sup></th></tr><tr><th>2</th><th>8</th><th>16</th><th>32</th><th>64</th><th>2</th><th>8</th><th>16</th><th>32</th><th>64</th></tr></thead><tbody><tr><td>Max TT-rank of M</td><td>2</td><td>5</td><td>5</td><td>5</td><td>5</td><td>2</td><td>7</td><td>13</td><td>15</td><td>15</td></tr><tr><td>L2 norm of AM<sub>q,τ</sub></td><td>0.012</td><td>0.276</td><td>0.949</td><td>1.00</td><td>1.00</td><td>0.012</td><td>0.276</td><td>0.949</td><td>1.00</td><td>1.00</td></tr></tbody></table>
Looking at the convergence history in Figures 17a and 17b, a value of $q \ge 16$ is already sufficient to reach in a very low number of iterations the bound $10^{-5}$, due to the TT-GMRES rounding value $\delta$. Figure 17b shows clearly that keeping more information in the preconditioner, TT-GMRES may reach very low levels. However in Figure 17d we observe the side effect of more information. The TT-rank of the last Krylov vector increases significantly for very accurate preconditioner. More precisely, comparing Figures 17c and 17d, the TT-rank of the last Krylov vector doubles if the preconditioner is more accurately rounded. Notice also that in Figure 17c, the TT-rank for $q \in \{16, 32, 64\}$ is almost the same. For the solution viewpoint, the rounding accuracy chosen for the preconditioner has not a big impact on its TT-rank. Indeed, as plotted in Figure 17e and 17f, for both the values of $\tau$ and for all $q \ge 8$, the TT-rank of the solution is equal to 5, while only for $q = 2$ it increases, meaning that only 5 addends are not sufficient to speed up the discrete Laplacian convergence.

<figure><img src="image_22.png" /><figcaption>Figure 17: 3-d Poisson problem, comparing preconditioners</figcaption></figure>
Looking at the convergence history in Figures 17a and 17b, a value of $q \ge 16$ is already sufficient to reach in a very low number of iterations the bound $10^{-5}$, due to the TT-GMRES rounding value $\delta$. Figure 17b shows clearly that keeping more information in the preconditioner, TT-GMRES may reach very low levels. However in Figure 17f we observe the side effect of more information. The TT-rank of the last Krylov vector increases significantly for very accurate preconditioner. More precisely, comparing Figures 17e and 17f, the TT-rank of the last Krylov vector doubles if the preconditioner is more accurately rounded. Notice also that in Figure 17e, the TT-rank for $q \in \{16, 32, 64\}$ is almost the same. For the solution viewpoint, the rounding accuracy chosen for the preconditioner has not a big impact on its TT-rank. Indeed, as plotted in Figure 17g and 17h, for both the values of $\tau$ and for all $q \ge 8$, the TT-rank of the solution is equal to 5, while only for $q = 2$ it increases, meaning that only 5 addends are not sufficient to speed up the discrete Laplacian convergence.
<figure><img src="image_23.png" /><figcaption>Figure 17: 3-d Poisson problem, comparing preconditioners</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 17: 3-d Poisson problem, comparing preconditioners</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>Figure 17: 3-d Poisson problem of size $n = 63$, comparing preconditioners using $\delta = 10^{-5}$ and $\varepsilon = 10^{-16}$</figcaption></figure>
## B Multiple right-hand sides: a focus on eigenvectors

In this appendix we study further the convergence of a multiple right-hand side problem. Indeed comparing the convergence history of the convection-diffusion problem, see Subsection 4.1.3 and of the multiple right-hand side convection-diffusion problem discussed in 4.3.2, notice that the number of iterations necessary to converge is equal, 5 in both cases. This appendix explains the causes of the phenomenon.

As we already explained, given a (tensor) linear system $Ax = b$ and the null tensor as initial guess, at the $k$-th iteration GMRES minimizes the norm of the residual $r_k = Ax - b$ on the Krylov space of dimension $k$ defined as

$$ \mathcal{K}_k(A, b) = \operatorname{span}\{b, Ab, \dots, A^{k-1}b\} $$

where $A^h$ is obtained from $h$ contractions over the indexes $(1, 3, \dots, 2d - 1, 2d + 1)$ of tensor operator $A$. If $b$ is equal to $e_i$ an eigenvector of the tensor operator $A$, then the Krylov space writes

$$ \begin{aligned} \mathcal{K}_k(A, b) &= \operatorname{span}\{b, Ab, \dots, A^{k-1}b\} \\ &= \operatorname{span}\{e_i, \lambda_i e_i, \dots, \lambda_i^{k-1} e_i\} \\ &= \operatorname{span}\{e_i\} \end{aligned} $$

where $\lambda_i$ is the $i$-th eigenvalue of $A$. The Krylov space dimension is equal to 1, i.e., the number of eigenvector $e_i$ necessary to express the right-hand side. Theoretically the number of iterations necessary to converge, i.e., the dimension of the Krylov space where the exact solution lives, is By linearity equal to the number of eigenvector necessary to express the right-hand side as their linear combination. In the problems presented in 4.3.1 and 4.3.2, we add a random generated tensor to the chosen right-hand side. Comparing the results a single right-hand side and multiple ones for the convection-diffusion problem, we may conclude that the introduced error has not increased the number of eigenvectors, for the tolerance chosen.

Let now consider a more peculiar problem with two right-hand side, living in subspaces generated by different eigenvector. More in details one right-hand side belongs to the subspace generated by a single eigenvector, while the other to the subspace generated by $j$ different eigenvector. Thanks to our previous argument, theoretically the two systems converge independently with a different number of iterations, one for the first and $j$ for the second. When we solve the two systems together, we expect the “all-in-one” system to converge as the slowest one, i.e., as the slowest converging one. Let $e_1, \dots, e_{j+1}$ be the first $j+1$ different eigenvectors of the 3-dimensional discrete Laplacian $-\Delta_3$. We consider the two following linear systems

$$ -\Delta_3 y_1 = e_1 \qquad (37) $$

$$ -\Delta_3 y_2 = \sum_{\ell=2}^{j+1} e_{\ell}. \qquad (38) $$

As described in Subsection 3, we define the “all-in-one” linear system with the ‘diagonal’ tensor operator $A$ and the “all-in-one” right-hand side $b$. TT-GMRES is used to solve this “all-in-one” system for $j = 10$, for a grid step dimension equal to $n \in \{63, 127, 255\}$, without preconditioner, with tolerance $\epsilon$ and rounding accuracy $\delta$ equal to $10^{-5}$, no restart and a maximum of 50 iterations. Figure 18a shows the convergence history of the problem with the three different grid dimensions. Since there is no preconditioner the convergence is kind of slow, if compared with Figure 11a. At the same time, the TT-ranks growth not too quickly, because both there is not a random generated error and there are just two right-hand side. The residual curve associated
<figure><img src="image_23.png" /><figcaption>Figure 17: 3-d Poisson problem, comparing preconditioners</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 17: 3-d Poisson problem, comparing preconditioners</figcaption></figure>
<figure><img src="image_25.png" /><figcaption>Figure 18: 4-d multiple right-hand side problem with eigenvector</figcaption></figure>

with Equation 37 in blue is almost flatten for all the grid dimensions, suggesting that GMRES almost immediately minimized it completely. On the other side the orange curve of problem (38) residual decreases slowly, meaning that minimizing its norm requires more steps. Lastly in all the plots the “all-in-one” residual curve follows exactly the eigenvector sum problem residual, confirming that the general convergence of the “all-in-one” system is decided by the slowest converging system, that is our intuition, confirmed in for all the grid dimensions in Figure 19. As last remark the “all-in-one” doesn’t converge in 10 iterations because of the rounding effect, which slows down the convergence.

<figure><img src="image_26.png" /><figcaption>Figure 19: 4-d multiple right-hand side problem, residual comparison</figcaption></figure>

C Further details on the “all-in-one” system

This appendix describes in details the construction in TT-format of the “all-in-one” system. As conclusion we provides a corollary to Proposition 3.4.

As previously stated, given a tensor $\mathbf{a} \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ in TT-format with TT-cores $\mathbf{a}_k \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}$, we denote by $\mathbf{a}^{[k, i_k]}$ the $i_k$-th slice with respect to mode $k$, which in TT-format
## B Multiple right-hand sides: a focus on eigenvectors

In this appendix we study further the convergence of a multiple right-hand side problem. Indeed comparing the convergence history of the convection-diffusion problem, see Subsection 4.1.3 and of the multiple right-hand side convection-diffusion problem discussed in 4.3.2, notice that the number of iterations necessary to converge is equal, 5 in both cases. This appendix explains the causes of the phenomenon.

As we already explained, given a (tensor) linear system $Ax = b$ and the null tensor as initial guess, at the $k$-th iteration GMRES minimizes the norm of the residual $r_k = Ax - b$ on the Krylov space of dimension $k$ defined as

$$ \mathcal{K}_k(\mathbf{A}, \mathbf{b}) = \operatorname{span}\{\mathbf{b}, \mathbf{A}\mathbf{b}, \dots, \mathbf{A}^{k-1}\mathbf{b}\} $$

where $\mathbf{A}^h$ is obtained from $h$ contractions over the indexes $(1, 3, \dots, 2d - 1, 2d + 1)$ of tensor operator $\mathbf{A}$. If $\mathbf{b}$ is equal to $\mathbf{e}_i$ an eigenvector of the tensor operator $\mathbf{A}$, then the Krylov space writes

$$ \begin{aligned} \mathcal{K}_k(\mathbf{A}, \mathbf{b}) &= \operatorname{span}\{\mathbf{b}, \mathbf{A}\mathbf{b}, \dots, \mathbf{A}^{k-1}\mathbf{b}\} \\ &= \operatorname{span}\{\mathbf{e}_i, \lambda_i \mathbf{e}_i, \dots, \lambda_i^{k-1} \mathbf{e}_i\} \\ &= \operatorname{span}\{\mathbf{e}_i\} \end{aligned} $$

where $\lambda_i$ is the $i$-th eigenvalue of $\mathbf{A}$. The Krylov space dimension is equal to 1, i.e., the number of eigenvector $\mathbf{e}_i$ necessary to express the right-hand side. Theoretically the number of iterations necessary to converge, i.e., the dimension of the Krylov space where the exact solution lives, is By linearity equal to the number of eigenvector necessary to express the right-hand side as their linear combination. In the problems presented in 4.3.1 and 4.3.2, we add a random generated tensor to the chosen right-hand side. Comparing the results a single right-hand side and multiple ones for the convection-diffusion problem, we may conclude that the introduced error has not increased the number of eigenvectors, for the tolerance chosen.

Let now consider a more peculiar problem with two right-hand side, living in subspaces generated by different eigenvector. More in details one right-hand side belongs to the subspace generated by a single eigenvector, while the other to the subspace generated by $j$ different eigenvector. Thanks to our previous argument, theoretically the two systems converge independently with a different number of iterations, one for the first and $j$ for the second. When we solve the two systems together, we expect the “all-in-one” system to converge as the slowest one, i.e., as the slowest converging one. Let $\mathbf{e}_1, \dots, \mathbf{e}_{j+1}$ be the first $j + 1$ different eigenvectors of the 3-dimensional discrete Laplacian $-\Delta_3$. We consider the two following linear systems

$$ -\Delta_3 \mathbf{y}_1 = \mathbf{e}_1 \qquad (37) $$

$$ -\Delta_3 \mathbf{y}_2 = \sum_{\ell=2}^{j+1} \mathbf{e}_{\ell}. \qquad (38) $$

As described in Subesction 3, we define the “all-in-one” linear system with the ‘diagonal’ tensor operator $\mathbf{A}$ and the “all-in-one” right-hand side $\mathbf{b}$. TT-GMRES is used to solve this “all-in-one” system for $j = 10$, for a grid step dimension equal to $n \in \{63, 127, 255\}$, without preconditioner, with tolerance $\varepsilon$ and rounding accuracy $\delta$ equal to $10^{-5}$, no restart and a maximum of 50 iterations. Figure ?? shows the convergence history of the problem with the three different grid dimensions. Since there is no preconditioner the convergence is kind of slow, if compared with Figure 11a. At the same time, the TT-ranks growth not too quickly, because both there is not a random generated error and there are just two right-hand side. The residual curve associated
writes as

$$ \mathbf{a}^{[k, i_k]} = \underline{\mathbf{a}}_1 \cdots \underline{\mathbf{a}}_{k-1} \underline{\mathbf{A}}_k(i_k) \underline{\mathbf{a}}_{k+1} \cdots \underline{\mathbf{a}}_d $$

with $\underline{\mathbf{A}}_k(i_k) \in \mathbb{R}^{r_{k-1} \times r_k}$. Since henceforth we will take slice only with respect to the first mode, instead of writing $\mathbf{a}^{[1, i_1]}$ for the $i_1$-th slice on the first mode we will simply write $\mathbf{a}^{[i_1]}$. Similarly $\underline{\mathbf{A}}^{[\ell]}$ denotes the $(\ell, \ell)$-th slice of $\mathbf{A} \in \mathbb{R}^{(n_1 \times n_1) \times \cdots \times (n_d \times n_d)}$ with respect to the first two modes.

We start constructing the elements of the “all-in-one” system from the $p$ individual right-hand sides. Let $\mathbf{b}_\ell \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ be a TT-vector for every $\ell \in \{1, \dots, p\}$ with TT-cores $\underline{\mathbf{b}}_{\ell,k} \in \mathbb{R}^{s_{\ell,k} \times n_k \times s_{\ell,k+1}}$ for every $k \in \{1, \dots, d\}$ with $s_1 = s_{d+1} = 1$, i.e.,

$$ \mathbf{b}_{\ell} = \underline{\mathbf{b}}_{\ell,1} \cdots \underline{\mathbf{b}}_{\ell,d} \qquad (39) $$

and its $(i_1, \dots, i_d)$ element writes

$$ \mathbf{b}_{\ell}(i_1, \dots, i_d) = \underline{\mathbf{B}}_{\ell,1}(i_1) \cdots \underline{\mathbf{B}}_{\ell,d}(i_d) $$

with $\underline{\mathbf{B}}_{\ell,k}(i_k) \in \mathbb{R}^{s_{\ell,k} \times s_{\ell,k+1}}$, $\underline{\mathbf{B}}_{\ell,1}(i_1) \in \mathbb{R}^{1 \times s_{\ell,2}}$ and $\underline{\mathbf{B}}_{\ell,d}(i_d) \in \mathbb{R}^{s_{\ell,d} \times 1}$. For simplicity we impose $s_k = s_{\ell,k}$ for every $\ell \in \{1, \dots, p\}$ and $k \in \{1, \dots, d\}$.

**Remark C.1.** This assumption on the TT-rank of $\mathbf{b}_\ell$ is not binding. Indeed setting $s_k = \max_{h \in \{1, \dots, p\}} s_{h,k}$, then each core tensor $\underline{\mathbf{b}}_{h,k}$ of mode sizes $(s_{h,k}, n_h, s_{h,k+1})$ can be extended with zeros to $(s_k, n_h, s_{k+1})$

We want to construct a tensor $\mathbf{b} \in \mathbb{R}^{p \times n_1 \times \cdots \times n_d}$ such that its $\ell$-th slice with respect to the first mode of $\mathbf{b}$ is $\mathbf{b}_\ell$, i.e., $\mathbf{b}^{[\ell]} = \mathbf{b}_\ell$. As consequence, the $k$-th TT-core of $\mathbf{b}$ is $\underline{\mathbf{b}}_k \in \mathbb{R}^{p s_k \times n_k \times p s_{k+1}}$ such that

$$ \underline{\mathbf{B}}_k(i_k) = \begin{bmatrix} \underline{\mathbf{B}}_{1,k}(i_k) & & & \\ & \ddots & & \\ & & \underline{\mathbf{B}}_{p,k}(i_k) & \\ & & & \underline{\mathbf{B}}_{k,k}(i_k) \end{bmatrix} \in \mathbb{R}^{p s_k \times p s_{k+1}} $$

for $k \in \{1, \dots, d-1\}$, while $\underline{\mathbf{b}}_d \in \mathbb{R}^{p s_{d-1} \times n_d \times 1}$ and $\underline{\mathbf{b}}_0 \in \mathbb{R}^{1 \times p \times p s_1}$ are

$$ \underline{\mathbf{B}}_d(i_d) = \begin{bmatrix} \underline{\mathbf{B}}_{1,d}(i_d) \\ \vdots \\ \underline{\mathbf{B}}_{p,d}(i_d) \end{bmatrix} \in \mathbb{R}^{p s_d \times 1} \quad \text{and} \quad \underline{\mathbf{B}}_0(\ell) = \begin{bmatrix} 0 \cdots 1 \cdots 0 \end{bmatrix} \in \mathbb{R}^{1 \times p s_1} $$

with the $\ell$-th component of $\underline{\mathbf{B}}_0(\ell)$ beign the only non-zero element. The TT-expression of $\mathbf{b}$ is

$$ \mathbf{b} = \underline{\mathbf{b}}_0 \underline{\mathbf{b}}_1 \cdots \underline{\mathbf{b}}_d. \qquad (40) $$

By construction we have that the $\ell$-th slice of $\mathbf{b}$ with respect to mode 1 is

$$ \begin{aligned} \mathbf{b}^{[\ell]} &= \underline{\mathbf{B}}_0(\ell) \underline{\mathbf{b}}_1 \cdots \underline{\mathbf{b}}_d \\ &= \underline{\mathbf{b}}_{\ell,1} \cdots \underline{\mathbf{b}}_{\ell,d} \\ &= \mathbf{b}_\ell. \end{aligned} $$

We illustrate now the construction of the “all-in-one” system tensor linear operator. Let $\mathbf{C}, \mathbf{G} \in \mathbb{R}^{(n_1 \times n_1) \times \cdots \times (n_d \times n_d)}$ be two TT-matrix with $k$-th TT-core $\underline{\mathbf{c}}_k \in \mathbb{R}^{r_k \times n_k \times n_k \times r_{k+1}}$ and $\underline{\mathbf{g}}_k \in \mathbb{R}^{q_k \times n_k \times n_k \times q_{k+1}}$ for $k \in \{1, \dots, d\}$ with $q_1 = r_1 = r_{d+1} = q_{d+1} = 1$, whose TT-expression is

$$ \mathbf{C} = \underline{\mathbf{c}}_1 \cdots \underline{\mathbf{c}}_d \quad \text{and} \quad \mathbf{G} = \underline{\mathbf{g}}_1 \cdots \underline{\mathbf{g}}_d. \qquad (41) $$
<figure><img src="image_25.png" /><figcaption>Convergence history of $\tilde{\eta}_b$ and $\eta_{AM,b}$ versus loss of orthogonality</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>Figure 19: 4-d multiple right-hand side problem with eigenvector using $\delta = 10^{-5}$ and $\varepsilon = 10^{-16}$</figcaption></figure>

with Equation 37 in blue is almost flatten for all the grid dimensions, suggesting that GMRES almost immediately minimized it completely. On the other side the orange curve of problem (38) residual decreases slowly, meaning that minimizing its norm requires more steps. Lastly in all the plots the “all-in-one” residual curve follows exactly the eigenvector sum problem residual, confirming that the general convergence of the “all-in-one” system is decided by the slowest converging system, that is our intuition, confirmed in for all the grid dimensions in Figure 20. As last remark the “all-in-one” doesn’t converge in 10 iterations because of the rounding effect, which slows down the convergence.

## C Further details on the “all-in-one” system

This appendix describes in details the construction in TT-format of the “all-in-one” system. As conclusion we provides a corollary to Proposition 3.4.

As previously stated, given a tensor $\mathbf{a} \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ in TT-format with TT-cores $\mathbf{a}_k \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}$, we denote by $\mathbf{a}^{[k, i_k]}$ the $i_k$-th slice with respect to mode $k$, which in TT-format
Given a diagonal matrix $D = \text{diag}(\alpha_1, \dots, \alpha_p)$, we define $\mathbf{A} \in \mathbb{R}^{(p \times p) \times (n_1 \times n_1) \times \dots \times (n_d \times n_d)}$ as

$$ \mathbf{A} = \mathbb{I}_p \otimes \mathbf{C} + D \otimes \mathbf{G} \qquad (42) $$

Then the expression of $\underline{\mathbf{a}}_k \in \mathbb{R}^{(r_k+q_k) \times n_k \times n_k \times (r_{k+1}+q_{k+1})}$ the k-th TT-core of $\mathbf{A}$ is

$$ \underline{\mathbf{A}}_k(i_k, j_k) = \begin{bmatrix} \underline{\mathbf{C}}_k(i_k, j_k) & \mathbf{0} \\ \mathbf{0} & \underline{\mathbf{G}}_k(i_k, j_k) \end{bmatrix} \quad \text{and} \quad \underline{\mathbf{A}}_d(i_d, j_d) = \begin{bmatrix} \underline{\mathbf{C}}_d(i_d, j_d) \\ \underline{\mathbf{G}}_d(i_d, j_d) \end{bmatrix} \qquad (43) $$

for every $i_k, j_k \in \{1, \dots, n_k\}$ and $k \in \{1, \dots, d\}$. The first TT-core $\underline{\mathbf{a}}_0 \in \mathbb{R}^{1 \times p \times p \times 2}$ writes

$$ \underline{\mathbf{A}}_0(\ell, m) = \delta_{\ell,m} a_{\ell} \quad \text{with} \quad a_{\ell} = \begin{bmatrix} 1 & \alpha_{\ell} \end{bmatrix} \qquad (44) $$

with $\delta_{\ell,m}$ the Kronecker delta, for $\ell, m \in \{1, \dots, p\}$. The final TT-expression of $\mathbf{A}$ is

$$ \mathbf{A} = \underline{\mathbf{a}}_0 \underline{\mathbf{a}}_1 \cdots \underline{\mathbf{a}}_d. $$

Remark now that $\mathbf{A}^{(\ell,m)}$ the $(\ell, m)$-th slice with respect to mode 1 of $\mathbf{A}$ is

$$ \mathbf{A}^{[\ell,m]} = \underline{\mathbf{A}}_0(\ell, m) \underline{\mathbf{a}}_1 \cdots \underline{\mathbf{a}}_d = \delta_{\ell,m} a_{\ell} \underline{\mathbf{a}}_1 \cdots \underline{\mathbf{a}}_d. $$

If $\ell \neq m$, then $\mathbf{A}^{[\ell,m]} = \mathbf{0}$. On the other side, if $\ell$ and $m$ are equal, then

$$ \mathbf{A}^{[\ell, \ell]} = \mathbb{I}(\ell, \ell) a_{\ell} \underline{\mathbf{a}}_1 \cdots \underline{\mathbf{a}}_d = \underline{\mathbf{c}}_1 \cdots \underline{\mathbf{c}}_d + \alpha_{\ell} \underline{\mathbf{g}}_1 \cdots \underline{\mathbf{g}}_d = \mathbf{C} + \alpha_{\ell} \mathbf{G}. $$

Let consider $\mathbf{A}$ and $\mathbf{b}$ as defined in Equation (42) and (40), given $\mathbf{x} \in \mathbb{R}^{p \times n_1 \times \dots \times n_d}$ and define the new vector

$$ \mathbf{r} = \mathbf{A}\mathbf{x} - \mathbf{b}. $$

We want to prove that $\mathbf{r}^{[\ell]}$ the $\ell$-th slice with respect to the first mode of $\mathbf{r}$ is equal to the difference of the $\ell$-th slices, i.e.,

$$ \mathbf{r}^{[\ell]} = \mathbf{A}^{[\ell, \ell]} \mathbf{x}^{[\ell]} - \mathbf{b}_{\ell} = (\mathbf{C} + \alpha_{\ell} \mathbf{G}) \mathbf{x}^{[\ell]} - \mathbf{b}_{\ell} \qquad (45) $$

since the $(\ell, \ell)$-th slice of $\mathbf{A}$ is $\mathbf{C} + \alpha_{\ell} \mathbf{G}$ for every $\ell \in \{1, \dots, p\}$. Remark that the $\ell$-th slice of $\mathbf{b}$ is $\mathbf{b}_{\ell}$ by construction. As consequence, the Equation (45) is true if we show that the $\ell$-th slice of the contraction between $\mathbf{A}$ and $\mathbf{x}$ is equal to the contraction of their $\ell$-th slices, i.e.,

$$ (\mathbf{A}\mathbf{x})^{[\ell]} = \mathbf{A}^{[\ell, \ell]}\mathbf{x}^{[\ell]}. $$

**Lemma C.2.** Given $\mathbf{A}, \mathbf{C}, \mathbf{G}$ as in Equations (41) and (42), let $\mathbf{x} \in \mathbb{R}^{p \times n_1 \times \dots \times n_d}$ be a $(d+1)$-order tensor. Then the $\ell$-th slice of $\mathbf{A}\mathbf{x}$ is equal to the product of their $\ell$-th slices, i.e.

$$ (\mathbf{A}\mathbf{x})^{[\ell]} = \mathbf{A}^{[\ell, \ell]}\mathbf{x}^{[\ell]} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}. $$

Defined and $\mathbf{w} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}$, then $\mathbf{y}^{[\ell]}$ the $\ell$-th slice of $\mathbf{y}$ with respect to mode 1 is equal to $\mathbf{w}$, i.e.,

$$ \mathbf{y}^{[\ell]} = \mathbf{w}. $$

*Proof.* Let $\underline{\mathbf{x}}_k \in \mathbb{R}^{t_k \times n_k \times t_{k+1}}$ be the $k$-th TT-core of $\mathbf{x}$ for $k \in \{1, \dots, d\}$ with $t_{d+1} = 1$ and $\underline{\mathbf{x}}_0 \in \mathbb{R}^{1 \times p \times t_1}$, getting

$$ \mathbf{x} = \underline{\mathbf{x}}_0 \underline{\mathbf{x}}_1 \cdots \underline{\mathbf{x}}_d \qquad (46) $$
<figure><img src="image_27.png" /><figcaption>Figure 20: 4-d multiple right-hand side problem, residual comparison using $\delta = 10^{-5}$ and $\varepsilon = 10^{-16}$</figcaption></figure>

writes as

$$ \mathbf{a}^{[k, i_k]} = \underline{\mathbf{a}}_1 \cdots \underline{\mathbf{a}}_{k-1} \underline{\mathbf{A}}_k(i_k) \underline{\mathbf{a}}_{k+1} \cdots \underline{\mathbf{a}}_d $$

with $\underline{\mathbf{A}}_k(i_k) \in \mathbb{R}^{r_{k-1} \times r_k}$. Since henceforth we will take slice only with respect to the first mode, instead of writing $\mathbf{a}^{[1, i_1]}$ for the $i_1$-th slice on the first mode we will simply write $\mathbf{a}^{[i_1]}$. Similarly $\underline{\mathbf{A}}^{[\ell]}$ denotes the $(\ell, \ell)$-th slice of $\mathbf{A} \in \mathbb{R}^{(n_1 \times n_1) \times \cdots \times (n_d \times n_d)}$ with respect to the first two modes.

We start constructing the elements of the “all-in-one” system from the $p$ individual right-hand sides. Let $\mathbf{b}_\ell \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ be a TT-vector for every $\ell \in \{1, \dots, p\}$ with TT-cores $\underline{\mathbf{b}}_{\ell,k} \in \mathbb{R}^{s_{\ell,k} \times n_k \times s_{\ell,k+1}}$ for every $k \in \{1, \dots, d\}$ with $s_1 = s_{d+1} = 1$, i.e.,

$$ \mathbf{b}_{\ell} = \underline{\mathbf{b}}_{\ell,1} \cdots \underline{\mathbf{b}}_{\ell,d} \qquad (39) $$

and its $(i_1, \dots, i_d)$ element writes

$$ \mathbf{b}_{\ell}(i_1, \dots, i_d) = \underline{\mathbf{B}}_{\ell,1}(i_1) \cdots \underline{\mathbf{B}}_{\ell,d}(i_d) $$

with $\underline{\mathbf{B}}_{\ell,k}(i_k) \in \mathbb{R}^{s_{\ell,k} \times s_{\ell,k+1}}$, $\underline{\mathbf{B}}_{\ell,1}(i_1) \in \mathbb{R}^{1 \times s_{\ell,2}}$ and $\underline{\mathbf{B}}_{\ell,d}(i_d) \in \mathbb{R}^{s_{\ell,d} \times 1}$. For simplicity we impose $s_k = s_{\ell,k}$ for every $\ell \in \{1, \dots, p\}$ and $k \in \{1, \dots, d\}$.

**Remark C.1.** This assumption on the TT-rank of $\mathbf{b}_\ell$ is not binding. Indeed setting $s_k = \max_{h \in \{1, \dots, p\}} s_{h,k}$, then each core tensor $\underline{\mathbf{b}}_{h,k}$ of mode sizes $(s_{h,k}, n_h, s_{h,k+1})$ can be extended with zeros to $(s_k, n_h, s_{k+1})$

We want to construct a tensor $\mathbf{b} \in \mathbb{R}^{p \times n_1 \times \cdots \times n_d}$ such that its $\ell$-th slice with respect to the first mode of $\mathbf{b}$ is $\mathbf{b}_\ell$, i.e., $\underline{\mathbf{b}}^{[\ell]} = \underline{\mathbf{b}}_\ell$. As consequence, the $k$-th TT-core of $\mathbf{b}$ is $\underline{\mathbf{b}}_k \in \mathbb{R}^{p s_k \times n_k \times p s_{k+1}}$ such that

$$ \underline{\mathbf{B}}_k(i_k) = \begin{bmatrix} \underline{\mathbf{B}}_{1,k}(i_k) & & & \\ & \ddots & & \\ & & \underline{\mathbf{B}}_{p,k}(i_k) & \\ & & & \underline{\mathbf{B}}_{p,d}(i_d) \end{bmatrix} \in \mathbb{R}^{p s_k \times p s_{k+1}} $$

for $k \in \{1, \dots, d-1\}$, while $\underline{\mathbf{b}}_d \in \mathbb{R}^{p s_{d-1} \times n_d \times 1}$ and $\underline{\mathbf{b}}_0 \in \mathbb{R}^{1 \times p \times p s_1}$ are

$$ \underline{\mathbf{B}}_d(i_d) = \begin{bmatrix} \underline{\mathbf{B}}_{1,d}(i_d) \\ \vdots \\ \underline{\mathbf{B}}_{p,d}(i_d) \end{bmatrix} \in \mathbb{R}^{p s_d \times 1} \quad \text{and} \quad \underline{\mathbf{B}}_0(\ell) = \begin{bmatrix} 0 & \cdots & 1 & \cdots & 0 \end{bmatrix} \in \mathbb{R}^{1 \times p s_1} $$
Set $\mathbf{y} = \mathbf{A}\mathbf{x}$, then by the property of TT-contraction, we get

$$
\begin{align*}
\mathbf{y}(\ell, i_1, \dots, i_d) &= \sum_{j_0, j_1, \dots, j_d=1}^{p, n_1, \dots, n_d} \underline{A}_0(\ell, j_0) \underline{A}_1(i_1, j_1) \cdots \underline{A}_d(i_d, j_d) \underline{X}_0(j_0) \underline{X}_1(j_1) \cdots \underline{X}_d(j_d) \\
&= \sum_{j_0, j_1, \dots, j_d=1}^{p, n_1, \dots, n_d} (\underline{A}_0(\ell, j_0) \otimes_K \underline{X}_0(j_0)) (\underline{A}_1(i_1, j_1) \otimes_K \underline{X}_1(j_1)) \cdots (\underline{A}_d(i_d, j_d) \otimes_K \underline{X}_d(j_d)) \\
&= \underline{Y}_0(\ell) \underline{Y}_1(i_1) \cdots \underline{Y}_d(i_d)
\end{align*}
$$

where $\underline{Y}_k(i_k) \in \mathbb{R}^{r_k t_k \times r_{k+1} t_{k+1}}$ with $r_1 = 1$, $Y_d(i_d) \in \mathbb{R}^{r_d t_d \times 1}$ and $\underline{Y}_0(\ell) \in \mathbb{R}^{1 \times t_1}$ defined as

$$
\begin{align}
\underline{Y}_0(i_0) &= \sum_{j_0=1}^{p} \underline{A}_0(\ell, j_0) \otimes_K \underline{X}_0(j_0) \nonumber \\
\underline{Y}_k(i_k) &= \sum_{j_k=1}^{n_k} \underline{A}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) \quad \text{for} \quad k \in \{2, \dots, d\}. \tag{47}
\end{align}
$$

Remark now that in the expression $\underline{Y}_0(\ell)$, the quantity $\underline{A}_0(\ell, j_0)$ is actually a vector of 2 elements times $\delta_{\ell,j_0}$, so we replace the Kronecker product with a simple scalar-matrix product, writing

$$
\begin{align}
\underline{Y}_0(\ell) &= \sum_{j_0=1}^{p} \delta_{\ell, j_0} a_\ell \otimes_K \underline{X}_0(j_0) \nonumber \\
&= \underline{A}_0(\ell, \ell) \otimes_K \underline{X}_0(\ell). \tag{48}
\end{align}
$$

Let $\mathbf{x}^{[\ell]}$ be the $\ell$-th slice with respect to the first mode of $\mathbf{x}$, whose TT-expression is

$$
\mathbf{x}^{[\ell]} = \underline{X}_0(\ell)\underline{\mathbf{x}}_1 \cdots \underline{\mathbf{x}}_d.
$$

We define $\mathbf{x}^{[\ell]}$ TT-cores to get the clean expression as

$$
\begin{align*}
\underline{\mathbf{x}}_{\ell,1} &= \underline{X}_0(\ell)\underline{\mathbf{x}}_1 \in \mathbb{R}^{1 \times n_1 \times t_2} \\
\underline{\mathbf{x}}_{\ell,k} &= \underline{\mathbf{x}}_k \in \mathbb{R}^{t_k \times n_k \times t_{k+1}} \quad \text{for} \quad k \in \{2, \dots, d\}
\end{align*}
$$

getting

$$
\mathbf{x}^{[\ell]} = \underline{\mathbf{x}}_{\ell,1} \cdots \underline{\mathbf{x}}_{\ell,d}.
$$

To compute $\mathbf{w} = (\mathbf{C} + \alpha_{\ell} \mathbf{G})\mathbf{x}^{[\ell]}$, we need to clarify the structure of the $k$-th TT-core of $\mathbf{H} = (\mathbf{C} + \alpha_{\ell} \mathbf{G})$, given by the TT-sum rule. Therefore the $k$-th TT-core is $\underline{\mathbf{h}}_k \in \mathbb{R}^{(r_k+q_k) \times n_k \times n_k \times (r_{k+1}+q_{k+1})}$ such that

$$
\underline{H}_k(i_k, j_k) = \begin{bmatrix} \underline{C}_k(i_k, j_k) & \emptyset \\ \emptyset & \underline{G}_k(i_k, j_k) \end{bmatrix} \quad \text{and} \quad \underline{H}_d(i_d, j_d) = \begin{bmatrix} \underline{C}_d(i_d, j_d) \\ \underline{G}_d(i_d, j_d) \end{bmatrix} \quad (49)
$$

for $i_k, j_k \in \{1, \dots, n_k\}$ and $k \in \{2, \dots, d\}$ with $r_{d+1} + q_{d+1} = 1$. The first TT-core $\underline{\mathbf{h}}_1 \in \mathbb{R}^{1 \times n_1 \times n_1 \times (r_2 + q_2)}$ is

$$
\underline{H}_1(i_1, j_1) = \begin{bmatrix} \underline{C}_1(i_1, j_1) \\ \alpha_{\ell} \underline{G}_1(i_1, j_1) \end{bmatrix}
$$

for $i_1, j_1 \in \{1, \dots, n_1\}$.
with the $\ell$-th component of $\underline{B}_0(\ell)$ be the only non-zero element. The TT-expression of $\mathbf{b}$ is

$$ \mathbf{b} = \underline{b}_0 \underline{b}_1 \cdots \underline{b}_d. \qquad (40) $$

By construction we have that the $\ell$-th slice of $\mathbf{b}$ with respect to mode 1 is

$$ \begin{aligned} \mathbf{b}^{[\ell]} &= \underline{B}_0(\ell) \underline{b}_1 \cdots \underline{b}_d \\ &= \underline{b}_{\ell,1} \cdots \underline{b}_{\ell,d} \\ &= \mathbf{b}_{\ell}. \end{aligned} $$

We illustrate now the construction of the “all-in-one” system tensor linear operator. Let $\mathbf{C}, \mathbf{G} \in \mathbb{R}^{(n_1 \times n_1) \times \cdots \times (n_d \times n_d)}$ be two TT-matrix with $k$-th TT-core $\underline{c}_k \in \mathbb{R}^{r_k \times n_k \times n_k \times r_{k+1}}$ and $\underline{g}_k \in \mathbb{R}^{q_k \times n_k \times n_k \times q_{k+1}}$ for $k \in \{1, \dots, d\}$ with $q_1 = r_1 = r_{d+1} = q_{d+1} = 1$, whose TT-expression is

$$ \mathbf{C} = \underline{c}_1 \cdots \underline{c}_d \quad \text{and} \quad \mathbf{G} = \underline{g}_1 \cdots \underline{g}_d. \qquad (41) $$

Given a diagonal matrix $D = \text{diag}(\alpha_1, \dots, \alpha_p)$, we define $\mathbf{A} \in \mathbb{R}^{(p \times p) \times (n_1 \times n_1) \times \cdots \times (n_d \times n_d)}$ as

$$ \mathbf{A} = \mathbb{I}_p \otimes \mathbf{C} + D \otimes \mathbf{G} \qquad (42) $$

Then the expression of $\underline{a}_k \in \mathbb{R}^{(r_k+q_k) \times n_k \times n_k \times (r_{k+1}+q_{k+1})}$ the $k$-th TT-core of $\mathbf{A}$ is

$$ \underline{A}_k(i_k, j_k) = \begin{bmatrix} \underline{C}_k(i_k, j_k) & \mathbf{0} \\ \mathbf{0} & \underline{G}_k(i_k, j_k) \end{bmatrix} \quad \text{and} \quad \underline{A}_d(i_d, j_d) = \begin{bmatrix} \underline{C}_d(i_d, j_d) \\ \underline{G}_d(i_d, j_d) \end{bmatrix} \qquad (43) $$

for every $i_k, j_k \in \{1, \dots, n_k\}$ and $k \in \{1, \dots, d\}$. The first TT-core $\underline{a}_0 \in \mathbb{R}^{1 \times p \times p \times 2}$ writes

$$ \underline{A}_0(\ell, m) = \delta_{\ell,m} a_{\ell} \quad \text{with} \quad a_{\ell} = \begin{bmatrix} 1 & \alpha_{\ell} \end{bmatrix} \qquad (44) $$

with $\delta_{\ell,m}$ the Kronecker delta, for $\ell, m \in \{1, \dots, p\}$. The final TT-expression of $\mathbf{A}$ is

$$ \mathbf{A} = \underline{a}_0 \underline{a}_1 \cdots \underline{a}_d. $$

Remark now that $\mathbf{A}^{(\ell,m)}$ the $(\ell, m)$-th slice with respect to mode 1 of $\mathbf{A}$ is

$$ \mathbf{A}^{[\ell,m]} = \underline{A}_0(\ell, m) \underline{a}_1 \cdots \underline{a}_d = \delta_{\ell,m} a_{\ell} \underline{a}_1 \cdots \underline{a}_d. $$

If $\ell \neq m$, then $\mathbf{A}^{[\ell,m]} = \mathbf{0}$. On the other side, if $\ell$ and $m$ are equal, then

$$ \mathbf{A}^{[\ell, \ell]} = \mathbb{I}(\ell, \ell) a_{\ell} \underline{a}_1 \cdots \underline{a}_d = \underline{c}_1 \cdots \underline{c}_d + \alpha_{\ell} \underline{g}_1 \cdots \underline{g}_d = \mathbf{C} + \alpha_{\ell} \mathbf{G}. $$

Let consider $\mathbf{A}$ and $\mathbf{b}$ as defined in Equation (42) and (40), given $\mathbf{x} \in \mathbb{R}^{p \times n_1 \times \cdots \times n_d}$ and define the new vector

$$ \mathbf{r} = \mathbf{A}\mathbf{x} - \mathbf{b}. $$

We want to prove that $\mathbf{r}^{[\ell]}$ the $\ell$-th slice with respect to the first mode of $\mathbf{r}$ is equal to the difference of the $\ell$-th slices, i.e.,

$$ \mathbf{r}^{[\ell]} = \mathbf{A}^{[\ell, \ell]} \mathbf{x}^{[\ell]} - \mathbf{b}_{\ell} = (\mathbf{C} + \alpha_{\ell} \mathbf{G}) \mathbf{x}^{[\ell]} - \mathbf{b}_{\ell} \qquad (45) $$

since the $(\ell, \ell)$-th slice of $\mathbf{A}$ is $\mathbf{C} + \alpha_{\ell} \mathbf{G}$ for every $\ell \in \{1, \dots, p\}$. Remark that the $\ell$-th slice of $\mathbf{b}$ is $\mathbf{b}_{\ell}$ by construction. As consequence, the Equation (45) is true if we show that the $\ell$-th slice of the contraction between $\mathbf{A}$ and $\mathbf{x}$ is equal to the contraction of their $\ell$-th slices, i.e.,

$$ (\mathbf{A}\mathbf{x})^{[\ell]} = \mathbf{A}^{[\ell, \ell]} \mathbf{x}^{[\ell]}. $$
Compute the $(i_1, \dots, i_d)$ element of $\mathbf{w} = \mathbf{H}\mathbf{x}^{[\ell]} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}$ as

$$ 
\begin{aligned}
\mathbf{w}(i_1, \dots, i_d) &= \sum_{j_1, \dots, j_d}^{n_1 \dots n_d} \underline{H}_1(i_1, i_1) \cdots \underline{H}_d(i_d, j_d) \underline{X}_{\ell,1}(j_1) \cdots \underline{X}_{\ell,d}(j_d) \\
&= \sum_{j_1, \dots, j_d}^{n_1, \dots, n_d} (\underline{H}_1(i_1, j_1)) \otimes_K \underline{X}_{\ell,1}(j_1) \cdots (\underline{H}_d(i_d, j_d) \otimes_K \underline{X}_{\ell,d}(j_d)) \\
&= \underline{W}_1(i_1) \underline{W}_2(i_2) \cdots \underline{W}_d(i_d)
\end{aligned}
$$

where $\underline{W}_k(i_k) \in \mathbb{R}^{r_k t_k \times r_{k+1} t_{k+1}}$, $W_d \in \mathbb{R}^{r_d t_d \times 1}$ and $\underline{W}_1 \in \mathbb{R}^{1 \times r_2 t_2}$ are defined as

$$ \underline{W}_1(i_1) = \sum_{j_1=1}^{n_1} \underline{H}_1(i_1, j_1) \otimes_K \underline{X}_0(\ell) \underline{X}_1(j_1) \qquad (50) $$

$$ \underline{W}_k(i_k) = \sum_{j_k=1}^{n_k} \underline{W}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) \quad \text{for} \quad k \in \{2, \dots, d\}. \qquad (51) $$

Comparing Equation (49) and (43), we get $\underline{h}_k = \underline{a}_k$ for $k \in \{2, \dots, d\}$. As consequence $\underline{W}_k(i_k)$ writes as

$$ \underline{W}_k(i_k) = \sum_{j_k=1}^{n_k} \underline{H}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) = \sum_{j_k=1}^{n_k} \underline{A}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) = \underline{Y}_k(i_k). $$

If we show that $\underline{Y}_0(\ell)Y_1(i_1)$ is equal to $\underline{W}_1(i_1)$, then the thesis holds true. Remark now that $\underline{H}_1(i_1, j_1)$ can be expressed equivalently as

$$ \underline{H}_1(i_1, j_1) = \begin{bmatrix} 1 & \alpha_{\ell} \end{bmatrix} \begin{bmatrix} \underline{C}_1(i_1, j_1) & \emptyset \\ \emptyset & \underline{G}_1(i_1, j_1) \end{bmatrix} = \underline{A}_0(\ell, \ell) \underline{A}_1(i_1, j_1). $$

from Equation (43) and (44). Thanks to this last equation, we have that

$$ 
\begin{aligned}
(\underline{H}_1(i_1, j_1)) \otimes_K (\underline{X}_0(\ell)\underline{X}_1(j_1)) &= (\underline{A}_0(\ell, \ell)\underline{A}_1(i_1, j_1)) \otimes_K (\underline{X}_0(\ell)\underline{X}_1(j_1)) \\
&= (\underline{A}_0(\ell, \ell) \otimes_K \underline{X}_0(\ell)) (\underline{A}_1(i_1, j_1)) \otimes_K \underline{X}_1(j_1)
\end{aligned}
$$

by the mixed-product property of the Kronecker product. Summing over index $j_1$ the previous equation leads to

$$ 
\begin{aligned}
\underline{W}_1(i_1) &= \sum_{j_1=1}^{n_1} (\underline{H}_1(i_1, j_1)) \otimes_K (\underline{X}_0(\ell)\underline{X}_1(j_1)) \\
&= \sum_{j_1=1}^{n_1} (\underline{A}_0(\ell, \ell) \otimes_K \underline{X}_0(\ell)) (\underline{A}_1(i_1, j_1)) \otimes_K \underline{X}_1(j_1) \\
&= \underline{Y}_0(\ell)\underline{Y}_1(i_1),
\end{aligned}
$$

from Equations (47) and (48) i.e., the thesis. $\square$

By the result of Lemma C.2, we get that the $\ell$-th slice of $\mathbf{A}\mathbf{x}$ writes

$$ (\mathbf{A}\mathbf{x})^{[\ell]} = \mathbf{C}\mathbf{x}^{[\ell]}. $$
**Lemma C.2.** Given **A**, **C**, **G** as in Equations (41) and (42), let **x** ∈ ℝ$^{p×n_1×...×n_d}$ be a $(d+1)$-order tensor. Then the $\ell$-th slice of **Ax** is equal to the product of their $\ell$-th slices, i.e.

$$ (\mathbf{A}\mathbf{x})^{[\ell]} = \mathbf{A}^{[\ell, \ell]}\mathbf{x}^{[\ell]} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}. $$

Defined and $\mathbf{w} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}$, then $\mathbf{y}^{[\ell]}$ the $\ell$-th slice of $\mathbf{y}$ with respect to mode 1 is equal to $\mathbf{w}$, i.e.,

$$ \mathbf{y}^{[\ell]} = \mathbf{w}. $$

*Proof.* Let $\mathbf{x}_k \in \mathbb{R}^{t_k \times n_k \times t_{k+1}}$ be the $k$-th TT-core of $\mathbf{x}$ for $k \in \{1, \dots, d\}$ with $t_{d+1} = 1$ and $\mathbf{x}_0 \in \mathbb{R}^{1 \times p \times t_1}$, getting

$$ \mathbf{x} = \mathbf{x}_0 \mathbf{x}_1 \cdots \mathbf{x}_d \qquad (46) $$

Set $\mathbf{y} = \mathbf{A}\mathbf{x}$, then by the property of TT-contraction, we get

$$ \begin{aligned} \mathbf{y}(\ell, i_1, \dots, i_d) &= \sum_{j_0, j_1, \dots, j_d=1}^{p, n_1, \dots, n_d} \underline{A}_0(\ell, j_0) \underline{A}_1(i_1, j_1) \cdots \underline{A}_d(i_d, j_d) \underline{X}_0(j_0) \underline{X}_1(j_1) \cdots \underline{X}_d(j_d) \\ &= \sum_{j_0, j_1, \dots, j_d=1}^{p, n_1, \dots, n_d} (\underline{A}_0(\ell, j_0) \otimes_K \underline{X}_0(j_0)) (\underline{A}_1(i_1, j_1) \otimes_K \underline{X}_1(j_1)) \cdots (\underline{A}_d(i_d, j_d) \otimes_K \underline{X}_d(j_d)) \\ &= \underline{Y}_0(\ell) \underline{Y}_1(i_1) \cdots \underline{Y}_d(i_d) \end{aligned} $$

where $\underline{Y}_k(i_k) \in \mathbb{R}^{r_k t_k \times r_{k+1} t_{k+1}}$ with $r_1 = 1$, $Y_d(i_d) \in \mathbb{R}^{r_d t_d \times 1}$ and $\underline{Y}_0(\ell) \in \mathbb{R}^{1 \times t_1}$ defined as

$$ \begin{aligned} \underline{Y}_0(i_0) &= \sum_{j_0=1}^{p} \underline{A}_0(\ell, j_0) \otimes_K \underline{X}_0(j_0) \\ \underline{Y}_k(i_k) &= \sum_{j_k=1}^{n_k} \underline{A}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) \quad \text{for} \quad k \in \{2, \dots, d\}. \end{aligned} \qquad (47) $$

Remark now that in the expression $\underline{Y}_0(\ell)$, the quantity $\underline{A}_0(\ell, j_0)$ is actually a vector of 2 elements times $\delta_{\ell, j_0}$, so we replace the Kronecker product with a simple scalar-matrix product, writing

$$ \begin{aligned} \underline{Y}_0(\ell) &= \sum_{j_0=1}^{p} \delta_{\ell, j_0} a_{\ell} \otimes_K \underline{X}_0(j_0) \\ &= \underline{A}_0(\ell, \ell) \otimes_K \underline{X}_0(\ell). \end{aligned} \qquad (48) $$

Let $\mathbf{x}^{[\ell]}$ be the $\ell$-th slice with respect to the first mode of $\mathbf{x}$, whose TT-expression is

$$ \mathbf{x}^{[\ell]} = \underline{X}_0(\ell)\underline{X}_1 \cdots \underline{X}_d. $$

We define $\mathbf{x}^{[\ell]}$ TT-cores to get the clean expression as

$$ \begin{aligned} \underline{X}_{\ell,1} &= \underline{X}_0(\ell)\underline{X}_1 \in \mathbb{R}^{1 \times n_1 \times t_2} \\ \underline{X}_{\ell,k} &= \underline{X}_k \in \mathbb{R}^{t_k \times n_k \times t_{k+1}} \quad \text{for} \quad k \in \{2, \dots, d\} \end{aligned} $$

getting

$$ \mathbf{x}^{[\ell]} = \underline{X}_{\ell,1} \cdots \underline{X}_{\ell,d}. $$

Inria
Therefore the $\ell$-th slice of $\mathbf{r}$ is

$$ \mathbf{r}^{[\ell]} = \mathbf{C}\mathbf{x}^{[\ell]} - \mathbf{b}^{[\ell]}. $$

As conclusive result of this construction, we want to show that

$$ ||\mathbf{r}||^2 = \sum_{\ell=1}^{p} ||\mathbf{r}^{[\ell]}||^2. $$

**Lemma C.3.** Given $\mathbf{s} \in \mathbb{R}^{n_0 \times n_1 \times \cdots \times n_d}$ and its $i_0$-th slice with respect to the first mode $\mathbf{s}^{(i_0)}$ then

$$ ||\mathbf{s}||^2 = \sum_{i_0=1}^{n_0} ||\mathbf{s}^{[i_0]}||^2. $$

*Proof.* Let $\mathbf{s} \in \mathbb{R}^{n_0 \times n_1 \times \cdots \times n_d}$ be a $(d+1)$-order tensor expressed in TT-format with TT-cores $\underline{\mathbf{s}}_k \in \mathbb{R}^{r_k \times n_k \times r_{k+1}}$ with $r_0 = r_{d+1} = 1$, such that

$$ \mathbf{s} = \underline{\mathbf{s}}_0 \cdots \underline{\mathbf{s}}_d. $$

Let define the TT-expression of $\mathbf{s}^{(i_0)} \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ is

$$ \mathbf{s}^{[i_0]} = \underline{\mathbf{S}}_0(i_0)\underline{\mathbf{S}}_1 \cdots \underline{\mathbf{S}}_d. $$

To have a correct TT-representation of $\mathbf{s}^{[i_0]}$ we define its TT-cores $\underline{\mathbf{s}}_{i_0,k} \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}$ as follows

$$ \begin{aligned} \underline{\mathbf{s}}_{i_0,1} &= \underline{\mathbf{S}}_0(i_0)\underline{\mathbf{S}}_1 \in \mathbb{R}^{1 \times n_1 \times r_2} \\ \underline{\mathbf{s}}_{i_0,k} &= \underline{\mathbf{s}}_k \in \mathbb{R}^{r_k \times n_k \times r_{k+1}} \quad \text{for} \quad k \in \{2, \dots, d\}. \end{aligned} $$

Compute now the norm of $\mathbf{s}$ as

$$ \begin{aligned} ||\mathbf{s}||^2 &= \sum_{i_0,j_1,\dots,j_d=1}^{n_0,n_1,\dots,n_d} \underline{\mathbf{S}}_0(i_0)\underline{\mathbf{S}}_1(j_1) \cdots \underline{\mathbf{S}}_d(j_d)\underline{\mathbf{S}}_0(i_0)\underline{\mathbf{S}}_1(j_1) \cdots \underline{\mathbf{S}}_d(j_d) \\ &= \sum_{i_0,j_1,\dots,j_d=1}^{n_0,n_1,\dots,n_d} \left( \underline{\mathbf{S}}_0(i_0) \otimes_K \underline{\mathbf{S}}_0(i_0) \right) \left( \underline{\mathbf{S}}_1(j_1) \otimes_K \underline{\mathbf{S}}_1(j_1) \right) \cdots \left( \underline{\mathbf{S}}_d(j_d) \otimes_K \underline{\mathbf{S}}_d(j_d) \right). \end{aligned} $$

Applying the mixed-product property of the Kronecker product to the first two matrix product, this last equation writes as

$$ \begin{aligned} ||\mathbf{s}||^2 &= \sum_{i_0,j_1,\dots,j_d=1}^{n_0,n_1,\dots,n_d} \left( \underline{\mathbf{S}}_0(i_0) \otimes_K \underline{\mathbf{S}}_0(i_0) \right) \left( \underline{\mathbf{S}}_1(j_1) \otimes_K \underline{\mathbf{S}}_1(j_1) \right) \cdots \left( \underline{\mathbf{S}}_d(j_d) \otimes_K \underline{\mathbf{S}}_d(j_d) \right) \\ &= \sum_{i_0=1}^{n_0} \sum_{j_1,\dots,j_d=1}^{n_1,\dots,n_d} \left( \underline{\mathbf{S}}_0(i_0)\underline{\mathbf{S}}_1(j_1) \otimes_K \underline{\mathbf{S}}_0(i_0)\underline{\mathbf{S}}_1(j_1) \right) \cdots \left( \underline{\mathbf{S}}_d(j_d) \otimes_K \underline{\mathbf{S}}_d(j_d) \right) \\ &= \sum_{i_0=1}^{n_0} \sum_{j_1,\dots,j_d=1}^{n_1,\dots,n_d} \left( \underline{\mathbf{S}}_{i_0,1}(j_1) \otimes_K \underline{\mathbf{S}}_{i_0,1}(j_1) \right) \cdots \left( \underline{\mathbf{S}}_{i_0,d}(j_d) \otimes_K \underline{\mathbf{S}}_{i_0,d}(j_d) \right) \\ &= \sum_{i_0=1}^{n_0} ||\mathbf{s}^{[i_0]}||^2. \end{aligned} $$

i.e., the thesis.

□
To compute $\mathbf{w} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}$, we need to clarify the structure of the k-th TT-core of $\mathbf{H} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})$, given by the TT-sum rule. Therefore the k-th TT-core is $\underline{\mathbf{h}}_k \in \mathbb{R}^{(r_k+q_k)\times n_k \times n_k \times (r_{k+1}+q_{k+1})}$ such that

$$ \underline{H}_k(i_k, j_k) = \begin{bmatrix} \underline{C}_k(i_k, j_k) & \mathbf{0} \\ \mathbf{0} & \underline{G}_k(i_k, j_k) \end{bmatrix} \quad \text{and} \quad \underline{H}_d(i_d, j_d) = \begin{bmatrix} \underline{C}_d(i_d, j_d) \\ \underline{G}_d(i_d, j_d) \end{bmatrix} \qquad (49) $$

for $i_k, j_k \in \{1, \dots, n_k\}$ and $k \in \{2, \dots, d\}$ with $r_{d+1} + q_{d+1} = 1$. The first TT-core $\underline{\mathbf{h}}_1 \in \mathbb{R}^{1 \times n_1 \times n_1 \times (r_2+q_2)}$ is

$$ \underline{H}_1(i_1, j_1) = \begin{bmatrix} \underline{C}_1(i_1, j_1) \\ \alpha_{\ell} \underline{G}_1(i_1, j_1) \end{bmatrix} $$

for $i_1, j_1 \in \{1, \dots, n_1\}$.

Compute the $(i_1, \dots, i_d)$ element of $\mathbf{w} = \mathbf{H}\mathbf{x}^{[\ell]} = (\mathbf{C} + \alpha_{\ell}\mathbf{G})\mathbf{x}^{[\ell]}$ as

$$ \begin{aligned} \mathbf{w}(i_1, \dots, i_d) &= \sum_{j_1, \dots, j_d}^{n_1 \dots n_d} \underline{H}_1(i_1, i_1) \cdots \underline{H}_d(i_d, j_d) \underline{X}_{\ell,1}(j_1) \cdots \underline{X}_{\ell,d}(j_d) \\ &= \sum_{j_1, \dots, j_d}^{n_1, \dots, n_d} (\underline{H}_1(i_1, j_1)) \otimes_K \underline{X}_{\ell,1}(j_1) \cdots (\underline{H}_d(i_d, j_d) \otimes_K \underline{X}_{\ell,d}(j_d)) \\ &= \underline{W}_1(i_1) \underline{W}_2(i_2) \cdots \underline{W}_d(i_d) \end{aligned} $$

where $\underline{W}_k(i_k) \in \mathbb{R}^{r_k t_k \times r_{k+1} t_{k+1}}$, $W_d \in \mathbb{R}^{r_d t_d \times 1}$ and $\underline{W}_1 \in \mathbb{R}^{1 \times r_2 t_2}$ are defined as

$$ \underline{W}_1(i_1) = \sum_{j_1=1}^{n_1} \underline{H}_1(i_1, j_1) \otimes_K \underline{X}_0(\ell) \underline{X}_1(j_1) \qquad (50) $$

$$ \underline{W}_k(i_k) = \sum_{j_k=1}^{n_k} \underline{W}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) \quad \text{for} \quad k \in \{2, \dots, d\}. \qquad (51) $$

Comparing Equation (49) and (43), we get $\underline{\mathbf{h}}_k = \underline{\mathbf{a}}_k$ for $k \in \{2, \dots, d\}$. As consequence $\underline{W}_k(i_k)$ writes as

$$ \underline{W}_k(i_k) = \sum_{j_k=1}^{n_k} \underline{H}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) = \sum_{j_k=1}^{n_k} \underline{A}_k(i_k, j_k) \otimes_K \underline{X}_k(j_k) = \underline{Y}_k(i_k). $$

If we show that $\underline{Y}_0(\ell)\underline{Y}_1(i_1)$ is equal to $\underline{W}_1(i_1)$, then the thesis holds true. Remark now that $\underline{H}_1(i_1, j_1)$ can be expressed equivalently as

$$ \underline{H}_1(i_1, j_1) = \begin{bmatrix} 1 & \alpha_{\ell} \end{bmatrix} \begin{bmatrix} \underline{C}_1(i_1, j_1) & \mathbf{0} \\ \mathbf{0} & \underline{G}_1(i_1, j_1) \end{bmatrix} = \underline{A}_0(\ell, \ell) \underline{A}_1(i_1, j_1). $$

from Equation (43) and (44). Thanks to this last equation, we have that

$$ \begin{aligned} (\underline{H}_1(i_1, j_1)) \otimes_K (\underline{X}_0(\ell)\underline{X}_1(j_1)) &= (\underline{A}_0(\ell, \ell)\underline{A}_1(i_1, j_1)) \otimes_K (\underline{X}_0(\ell)\underline{X}_1(j_1)) \\ &= (\underline{A}_0(\ell, \ell) \otimes_K \underline{X}_0(\ell)) (\underline{A}_1(i_1, j_1)) \otimes_K \underline{X}_1(j_1) \end{aligned} $$
By the result of Lemma C.3, we have

$$||\mathbf{r}||^2 = \sum_{\ell=1}^{p} ||\mathbf{r}^{[\ell]}||^2.$$

Once the “all-in-one” system has been completely described in its construction in TT-format, we present a further result related to Proposition 3.2.

**Corollary C.4.** Under the hypothesis of Corollary 3.5, if there exists a $k^\dagger \in \mathbb{N}$ such that $||\mathbf{x}_k^{[\ell]}|| \le ||\mathbf{A}^{-1}||_2 \sqrt{p}$ for every $k \ge k^\dagger$, then

$$\eta_{\mathbf{A},\mathbf{v}}(\mathbf{x}_k) \rho^\dagger \ge \eta_{\mathbf{A}_\ell,\mathbf{v}_\ell}(\mathbf{x}_k^{[\ell]}) \quad \text{where} \quad \rho^\dagger = \frac{\sqrt{p}}{2-\nu}(1+\kappa_2(\mathbf{A})) \quad (52)$$

with $\kappa_2(\mathbf{A}) = ||\mathbf{A}||_2 ||\mathbf{A}^{-1}||_2$ for every $\ell \in \{1, \dots, p\}$ and for every $k \in \mathbb{N}$ such that $k \ge k^\dagger$ where $k^\dagger = \max\{k^{**}, k^\dagger\}$ with $k^{**}$ given in Corollary 3.5.
by the mixed-product property of the Kronecker product. Summing over index $j_1$ the previous equation leads to

$$ 
\begin{aligned}
\underline{W}_1(i_1) &= \sum_{j_1=1}^{n_1} (\underline{H}_1(i_1, j_1)) \otimes_K (\underline{X}_0(\ell)\underline{X}_1(j_1)) \\
&= \sum_{j_1=1}^{n_1} (\underline{A}_0(\ell, \ell) \otimes_K \underline{X}_0(\ell)) (\underline{A}_1(i_1, j_1)) \otimes_K \underline{X}_1(j_1) \\
&= \underline{Y}_0(\ell)\underline{Y}_1(i_1),
\end{aligned}
$$

from Equations (47) and (48) i.e., the thesis.

<figure><img src="image_28.png" /></figure>

By the result of Lemma C.2, we get that the $\ell$-th slice of $Ax$ writes

$$ (Ax)^{[\ell]} = Cx^{[\ell]}. $$

Therefore the $\ell$-th slice of $r$ is

$$ r^{[\ell]} = Cx^{[\ell]} - b^{[\ell]}. $$

As conclusive result of this construction, we want to show that

$$ ||r||^2 = \sum_{\ell=1}^{p} ||r^{[\ell]}||^2. $$

**Lemma C.3.** Given $s \in \mathbb{R}^{n_0 \times n_1 \times \cdots \times n_d}$ and its $i_0$-th slice with respect to the first mode $s^{(i_0)}$ then

$$ ||s||^2 = \sum_{i_0=1}^{n_0} ||s^{[i_0]}||^2. $$

*Proof.* Let $s \in \mathbb{R}^{n_0 \times n_1 \times \cdots \times n_d}$ be a $(d+1)$-order tensor expressed in TT-format with TT-cores $s_k \in \mathbb{R}^{r_k \times n_k \times r_{k+1}}$ with $r_0 = r_{d+1} = 1$, such that

$$ s = \underline{s}_0 \cdots \underline{s}_d. $$

Let define the TT-expression of $s^{(i_0)} \in \mathbb{R}^{n_1 \times \cdots \times n_d}$ is

$$ s^{[i_0]} = \underline{S}_0(i_0)\underline{s}_1 \cdots \underline{s}_d. $$

To have a correct TT-representation of $s^{[i_0]}$ we define its TT-cores $\underline{s}_{i_0,k} \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}$ as follows

$$ 
\begin{aligned}
\underline{s}_{i_0,1} &= \underline{S}_0(i_0)\underline{s}_1 \in \mathbb{R}^{1 \times n_1 \times r_2} \\
\underline{s}_{i_0,k} &= \underline{s}_k \in \mathbb{R}^{r_k \times n_k \times r_{k+1}} \quad \text{for} \quad k \in \{2, \dots, d\}.
\end{aligned}
$$

Compute now the norm of $s$ as

$$ 
\begin{aligned}
||s||^2 &= \sum_{i_0, j_1, \dots, j_d=1}^{n_0, n_1, \dots, n_d} \underline{S}_0(i_0)\underline{S}_1(j_1) \cdots \underline{S}_d(j_d)\underline{S}_0(i_0)\underline{S}_1(j_1) \cdots \underline{S}_d(j_d) \\
&= \sum_{i_0, j_1, \dots, j_d=1}^{n_0, n_1, \dots, n_d} (\underline{S}_0(i_0) \otimes_K \underline{S}_0(i_0)) (\underline{S}_1(j_1) \otimes_K \underline{S}_1(j_1)) \cdots (\underline{S}_d(j_d) \otimes_K \underline{S}_d(j_d)).
\end{aligned}
$$

Inria
<figure><img src="image_27.png" /></figure>

RESEARCH CENTRE
BORDEAUX - SUD-OUEST

200 avenue de la Vieille Tour
33405 Talence Cedex

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr

ISSN 0249-6399
Applying the mixed-product property of the Kronecker product to the first two matrix product, this last equation writes as

$$ \begin{aligned} ||\mathbf{s}||^2 &= \sum_{i_0, j_1, \dots, j_d=1}^{n_0, n_1, \dots, n_d} \left( \underline{S}_0(i_0) \otimes_K \underline{S}_0(i_0) \right) \left( \underline{S}_1(j_1) \otimes_K \underline{S}_1(j_1) \right) \cdots \left( \underline{S}_d(j_d) \otimes_K \underline{S}_d(j_d) \right) \\ &= \sum_{i_0=1}^{n_0} \sum_{j_1, \dots, j_d=1}^{n_1, \dots, n_d} \left( \underline{S}_0(i_0) \underline{S}_1(j_1) \otimes_K \underline{S}_0(i_0) \underline{S}_1(j_1) \right) \cdots \left( \underline{S}_d(j_d) \otimes_K \underline{S}_d(j_d) \right) \\ &= \sum_{i_0=1}^{n_0} \sum_{j_1, \dots, j_d=1}^{n_1, \dots, n_d} \left( \underline{S}_{i_0,1}(j_1) \otimes_K \underline{S}_{i_0,1}(j_1) \right) \cdots \left( \underline{S}_{i_0,d}(j_d) \otimes_K \underline{S}_{i_0,d}(j_d) \right) \\ &= \sum_{i_0=1}^{n_0} ||\mathbf{s}^{[i_0]}||^2. \end{aligned} $$

i.e., the thesis.

□

By the result of Lemma C.3, we have

$$ ||\mathbf{r}||^2 = \sum_{\ell=1}^{p} ||\mathbf{r}^{[\ell]}||^2. $$

Once the “all-in-one” system has been completely described in its construction in TT-format, we present a further result related to Proposition 3.2.

**Corollary C.4.** Under the hypothesis of Corollary 3.5, if there exists a $k^\dagger \in \mathbb{N}$ such that $||\mathbf{x}_k^{[\ell]}|| \le ||\mathbf{A}^{-1}||_2 \sqrt{p}$ for every $k \ge k^\dagger$, then

$$ \eta_{\mathbf{A},\mathbf{v}}(\mathbf{x}_k) \rho^\dagger \ge \eta_{\mathbf{A}_\ell,\mathbf{v}_\ell}(\mathbf{x}_k^{[\ell]}) \quad \text{where} \quad \rho^\dagger = \frac{\sqrt{p}}{2-\nu}(1+\kappa_2(\mathbf{A})) \quad (52) $$

with $\kappa_2(\mathbf{A}) = ||\mathbf{A}||_2 ||\mathbf{A}^{-1}||_2$ for every $\ell \in \{1, \dots, p\}$ and for every $k \in \mathbb{N}$ such that $k \ge k^\ddagger$ where $k^\ddagger = \max\{k^{**}, k^\dagger\}$ with $k^{**}$ given in Corollary 3.5.
<figure><img src="image_29.png" /></figure>

RESEARCH CENTRE
BORDEAUX - SUD-OUEST

200 avenue de la Vieille Tour
33405 Talence Cedex

Publisher

Inria

Domaine de Voluceau - Rocquencourt

BP 105 - 78153 Le Chesnay Cedex

inria.fr

ISSN 0249-6399