arXiv:2611.03859
Factorized approximate inverse preconditioners in the tensor train format
Pau Torrente Badia, Daniel Pérez García, Artur Garcia-Saez, Stefano Carignano
Abstract
We present a preconditioning pipeline that accelerates Tensor Train (TT) linear solvers for symmetric positive-definite problems. Extending the Factorized Sparse Approximate Inverse framework to tensor networks, we construct a preconditioner as the product of a TT operator and its transpose. This formulation is positive semidefinite for any bond dimension and truncation, and definite whenever the factor is non-singular, satisfying the mathematical requirements of the Conjugate Gradient method. We detail the construction of this preconditioner and its integration into Density Matrix Renormalization Group (DMRG)-like linear solvers. Performance evaluations show consistent iteration reductions for anisotropic diffusion and Poisson problems across various configurations, leading to net speedups of up to 25% in ill-conditioned settings of time stepping schemes that can reuse the approximate inverses. These benchmarks were performed with the open-source Julia library DifferenTT.jl, which we also introduce in this work to provide out-of-the-box access to these preconditioned pipelines.
AI Summary
Tensor-train (TT) approximate inverses can lose positive definiteness under truncation, making them unsuitable for preconditioned conjugate gradient (PCG). This paper adapts factorized sparse approximate inversion to construct a TT preconditioner $G^T G$, which remains positive semidefinite regardless of factor truncation and is positive definite when $G$ is nonsingular. The construction uses a bond-dimension-two triangularity mask to formulate a projected linear system for an approximate inverse Cholesky factor without computing the Cholesky decomposition. Diagonal rescaling uses recursive sketched interpolation. For DMRG-like MALS solvers, projecting the factor and applying its transpose locally avoids forming or truncating the full product. A proved bound controls diagonal-rescaling errors: $|\tilde G_{ii}/\tilde G^\star_{ii}-1|\leq\nu_i$, where $\nu_i$ is the relative row energy error; a nonpositive diagonal requires $\nu_i\geq1$. Benchmarks cover rotated anisotropic diffusion in 10 and 20 dimensions and repeated pressure-Poisson solves in a QTT fluid simulation. For anisotropic diffusion, iteration reductions relative to a separable preconditioner reach 50% and 30%, respectively, but application overhead and construction costs negate runtime gains. On a $1024^2$ fluid grid, factor bond dimensions 4–7 reduce iterations by factors of 4.0–5.6 and give reported net speedups of approximately 20–25% over 1,000 steps, including construction; the $256^2$ case reaches 13%. Practical benefits depend on small local dimensions and preconditioner reuse. Diagonal positivity is not guaranteed by the solver’s residual tolerance, projected factors can be singular, and performance on less structured operators, nonuniform grids, or strongly varying coefficients remains untested. Code and benchmark data are provided.
the authors used Claude (Anthropic) and Gemini (Google) LLMs to assist in the formalization of Lemma~\ref{lem:diag_positivity} and the rotated anisotropy benchmark of Sec.~\ref{subsec:anisotropy_experiment}
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 50 pages, 11 figures