🔢 mathematics

Factorized approximate inverse preconditioners in the tensor train format

This paper introduces a factorized sparse approximate inverse preconditioner in the Tensor Train format, implemented in the new Julia library DifferenTT.jl, which accelerates Conjugate Gradient solvers for symmetric positive-definite problems by achieving up to 25% speedups in ill-conditioned settings.

Original author: Pau Torrente Badia, Daniel Pérez García, Artur Garcia-Saez, Stefano Carignano

Published 2026-11-04

📖 4 min read🧠 Deep dive

CC BY 4.0

Original author: Pau Torrente Badia, Daniel Pérez García, Artur Garcia-Saez, Stefano Carignano

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine trying to solve a puzzle where the number of pieces grows so fast that even the world's most powerful supercomputers would run out of memory before they could begin. This is the reality of simulating complex physical systems, from the flow of air over a wing to the behavior of electrons in a new material. Scientists often break these massive problems down into grids of tiny points, but as they add more dimensions to make the model more realistic, the data required explodes exponentially. To tackle this, researchers have developed a clever way to compress this information, breaking the giant puzzle into a chain of smaller, manageable links that fit together perfectly. This compression technique, known as the Tensor Train format, allows computers to handle problems that would otherwise be impossible. However, even with this compression, solving the underlying equations remains slow and difficult, especially when the system is "ill-conditioned," a state where tiny errors in the data can cause the solution to spiral out of control.

In a recent study, a team of researchers at the Barcelona Supercomputing Center has introduced a new tool to speed up these calculations, specifically for a class of problems involving heat diffusion and fluid pressure. They developed a method to create a "preconditioner," which acts like a shortcut or a guide for the computer, helping it find the correct answer much faster by smoothing out the mathematical landscape. The challenge they faced was that existing methods for creating these shortcuts often broke a fundamental rule of the math used to solve these problems: the shortcut had to be perfectly stable and positive. If it wasn't, the computer's solver would crash. The researchers solved this by building their shortcut not as a single block, but as a product of two parts that are mirror images of each other. This design guarantees that the shortcut remains stable and mathematically sound, no matter how much the data is compressed to save memory.

The team tested this new approach on two very different types of problems. First, they looked at a high-dimensional diffusion problem, which models how heat or particles spread through a material that conducts differently in different directions. In this scenario, the new method successfully reduced the number of steps the computer needed to take to find a solution by up to fifty percent compared to previous techniques. However, the time it took to build the shortcut was so long that the overall process actually slowed down. The researchers found that the cost of preparing the guide outweighed the time saved by using it, at least for this specific type of problem where the data structure was relatively simple.

The story changed when they applied the same method to a simulation of fluid flowing around a cylinder, a classic problem in aerodynamics. Here, the data was compressed in a way that made the initial setup of the shortcut much cheaper and faster. Because the same fluid flow equations are solved over and over again as time passes, the researchers could build the shortcut once and reuse it for thousands of time steps. In this setting, the new method proved highly effective. On a grid with over one million points, the shortcut reduced the number of calculation steps by a factor of more than five. When they accounted for the time spent building the shortcut, the total time to simulate the fluid flow dropped by about twenty-five percent. This demonstrates that while the method is not a universal fix for every situation, it is a powerful and practical tool for time-dependent simulations where the same equations are solved repeatedly, offering a genuine speedup for complex scientific modeling.

Technical Summary: Factorized Approximate Inverse Preconditioners in the Tensor Train Format

Problem Statement
The paper addresses the challenge of solving large-scale symmetric positive-definite (SPD) linear systems ( $Ax = b$ ) within the Tensor Train (TT) format, a common representation for high-dimensional problems in numerical modeling. While the Conjugate Gradient (CG) method is the standard solver for SPD systems, its convergence rate is heavily dependent on the condition number of the operator $A$ . In TT-based solvers, particularly those utilizing the Density Matrix Renormalization Group (DMRG) framework (e.g., the Alternating Linear Scheme or MALS), standard preconditioning techniques face significant hurdles. Direct approximate inversion methods (e.g., solving $AX \approx I$ ) do not guarantee that the resulting preconditioner remains SPD. As demonstrated in the paper, truncation errors inherent to the TT format can shift eigenvalues of the symmetric part of an approximate inverse below zero, causing the preconditioned CG (PCG) method to break down. Existing SPD-preserving techniques for sparse matrices have not been effectively adapted to the tensor network context.

Methodology
The authors propose a pipeline for constructing a Factorized Sparse Approximate Inverse (FSAI) preconditioner adapted to the TT format, termed TT-FAI. The core innovation lies in constructing the preconditioner $M^{-1}$ not as a direct approximation of $A^{-1}$ , but as the product of a factor and its transpose: $M^{-1} = G_L^T G_L$ . This formulation ensures that the preconditioner is positive semidefinite by construction, satisfying the mathematical requirements of the PCG method provided the factor $G_L$ is non-singular.

The methodology proceeds through the following steps:

Factorized Construction: Instead of inverting $A$ directly, the method seeks an approximate inverse $G_L$ of the Cholesky factor $L_A$ (where $A = L_A L_A^T$ ). The goal is to minimize $\|I - G_L L_A\|_F^2$ .
Triangularity Constraint via Projection: In the TT format, enforcing the lower-triangular structure required for $G_L$ is non-trivial. The authors introduce a "triangularity mask" $P_L$ constructed as a low-rank TT operator. This mask is used to project the linear system into a subspace of lower-triangular operators. The system is solved variationally:
$[P_L(I \otimes A)P_L + \mu(I - P_L)] \text{vec}(\tilde{G}_L) = \text{vec}(I)$
Here, $\mu$ is a penalty parameter (chosen as the Gershgorin bound $\|A\|_\infty$ ) that suppresses upper-triangular entries without requiring the explicit computation of the Cholesky factor $L_A$ .
Rescaling: The solution $\tilde{G}_L$ is rescaled by a diagonal matrix $D$ to ensure the preconditioned matrix has a unit diagonal. The authors employ a Recursive Sketched Interpolation (RSI) pipeline to compute the element-wise square root inverse ( $x^{-1/2}$ ) of the diagonal of $\tilde{G}_L$ efficiently within the TT format.
Integration with DMRG: To apply the preconditioner within DMRG-like solvers (MALS), the authors avoid contracting $G_L^T G_L$ into a single operator, which would inflate bond dimensions. Instead, they project $G_L$ and $G_L^T$ separately onto the local subspaces. This maintains the positive semi-definite property of the local preconditioner and keeps storage costs comparable to a standard TT operator.

Key Contributions

SPD-Preserving Preconditioning: The paper introduces the first FSAI-based preconditioner for TT linear solvers that guarantees positive semi-definiteness by design, overcoming the breakdown issues associated with direct TT inversion.
Projection-Based Triangularity: A novel method to enforce lower-triangular constraints on TT operators using a low-rank mask and variational projection, avoiding the need for explicit Cholesky decomposition.
Efficient Implementation: The development of the DifferenTT.jl library, an open-source Julia package built on ITensors.jl, which implements these pipelines and provides out-of-the-box access to TT-FAI preconditioned solvers.
Theoretical Bounds: The authors provide Lemma 1 and Corollary 1, establishing conditions under which the diagonal entries of the approximate factor remain positive, ensuring the stability of the rescaling step.

Results
The authors evaluated the TT-FAI on two distinct elliptic problems:

High-Dimensional Anisotropic Diffusion: In an $N$ -dimensional rotated anisotropy problem, the TT-FAI successfully captured correlations between dimensions that separable preconditioners (like the Sinc quadrature-based $B_M$ ) missed. It reduced local CG iterations by up to 50% for $N=10$ and 30% for $N=20$ compared to the state-of-the-art separable preconditioner. However, due to the high cost of constructing the preconditioner in the vectorized space (local dimension $n^2=225$ ) and the increased cost per iteration, the net result was a slowdown (11–30% slower than the baseline).
2D Incompressible Flow (Chorin Projection): In a time-stepping simulation of fluid flow using the Quantized Tensor Train (QTT) format, the preconditioner was constructed once and reused over 1000 time steps. On a $1024^2$ grid, the TT-FAI reduced iterations by a factor of 4.0–5.6. Because the QTT local dimension is small (2) and the operator is reused, the construction cost was amortized, resulting in a net speedup of 20–25% over the unpreconditioned baseline. On coarser grids ( $256^2$ ), the speedup was limited to ~13% due to fewer iterations required per step.

Significance and Claims
The paper claims that the TT-FAI is a practical addition to TT solvers specifically when the local dimension is small and the preconditioner can be reused, such as in time-stepping schemes for PDEs. The authors emphasize that while the method is robust and mathematically sound (guaranteeing SPD properties), its utility is currently limited in settings with large local dimensions or non-reusable operators due to the high construction cost relative to the solve time. The work demonstrates that factorized approximate inverses can be successfully adapted to tensor networks to improve convergence without sacrificing the stability required for CG methods, provided the construction overhead can be amortized. The authors explicitly state that the method's effectiveness in unstructured grids or with less structured operators remains an open question for future investigation.

More like this