Optimizing Sparse Tensor Train Decomposition to Solve Linear Systems of Equations

Abstract

This thesis investigates the potential of solving large-scale linear systems of equations (LSEs) in the Tensor Train (TT) format. First, we study when this approach can outperform traditional solvers like Conjugate Gradient (CG) and Gaussian Elimination (GE). In turn, we examine the time complexity of the TT-solve technique when applied to ill-conditioned, sparse, and symmetric positive definite (SPD) matrices. This enables us to assess the scenarios where TT-solve may offer significant advantages.
During this exploration, we have also identified and proposed solutions for a handful of research gaps that could further optimize the TT-solve process. These include challenges related to poorly factorizing matrix sizes, as well as the need for a deeper understanding of the trade-offs between TT-matrix (TTM) rank and maximal mode size during the decomposition process. Additionally, the study examined the potential for altering the coefficient matrix through techniques like variable reordering and partial Gaussian elimination (PG) to achieve lower TTM-ranks without affecting the solution of the LSE.