We study the solution of linear systems with tensor product structure using the Generalized Minimal RESidual (GMRES) algorithm. To manage the computational complexity of high-dimensional problems, our approach relies on low-rank tensor representation, focusing specifically on the Tensor Train format. We implement and experimentally study the TT-GMRES algorithm.
Our analysis bridges the heuristic methods proposed for TT-GMRES by Dolgov [Russian J. Numer. Anal. Math. Modelling, 28 (2013), pp. 149–172]
and the theoretical framework of inexact GMRES by Simoncini and Szyld
[SIAM J. Sci. Comput. 25 (2003), pp. 454–477].
This approach is particularly relevant in a scenario where a $(d+1)$-dimensional problem arises from concatenating a sequence of
$d$-dimensional problems, as in the case of a parametric linear operator or parametric right-hand-side formulation. Thus, we provide backward error bounds that link the accuracy of the computed $(d+1)$-dimensional solution to the numerical quality of the extracted $d$-dimensional solutions. This facilitates the prescription of a convergence threshold ensuring that the $d$-dimensional solutions extracted from the $(d+1)$-dimensional result have the desired accuracy once the solver converges.
We illustrate these results with academic examples across varying dimensions and sizes. Our experiments indicate that TT-GMRES retains the theoretical rounding-error properties observed in matrix-based GMRES.