Volume 62, pp. 163-187, 2024.

A note on TT-GMRES for the solution of parametric linear systems

Olivier Coulaud, Luc Giraud, and Martina Iannacito

Abstract

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.

Full Text (PDF) [715 KB], BibTeX , DOI: 10.1553/etna_vol62s163

Key words

GMRES, inexact GMRES, backward stability, Tensor Train format

AMS subject classifications

65F10, 15A69, 65G50