💻 computer science

Towards a mixed-precision ADI method for Lyapunov equations

This paper proposes and empirically validates a mixed-precision low-rank ADI method for solving Lyapunov equations, demonstrating that strategically using single precision for specific algorithmic components can achieve residuals comparable to full double precision while offering competitive performance for applications like computing the H2 norm of descriptor systems.

Original authors: Jonas Schulze, Jens Saak

Published 2026-02-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Jonas Schulze, Jens Saak

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 authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: The "Sketch Artist" Approach to Math

Imagine you are a detective trying to reconstruct a massive, incredibly detailed crime scene—a room filled with millions of tiny, specific details (this is the Lyapunov equation).

Usually, to get this right, you’d need a high-resolution 3D scanner that captures every single atom. This is like using "Double Precision" math: it’s incredibly accurate, but it requires massive amounts of memory and takes a long time to process.

The researchers in this paper are asking: "Do we really need to be perfect at every single step to get the right answer?"

They are proposing a "Mixed-Precision" method. Instead of using a high-res scanner for everything, they use a "Sketch Artist" approach. They use quick, rough sketches for the minor details and save the high-resolution tools only for the most important parts.

The Three Levels of "Detail"

The paper breaks the math down into three different "levels of focus" (precisions):

The Big Picture (The Solution): This is the final map of the crime scene.
The Moving Parts (The Increments): These are the small updates you make to the map as you learn more.
The Internal Notes (The Inner Factors): These are the tiny, messy scribbles in your notebook that help you calculate the next update.

In traditional math, you’d use "High Definition" for all three. In this paper’s Mixed-Precision method, they try using "Standard Definition" for the big picture and the notes, and only use "High Definition" for the actual math calculations.

The "Kitchen Analogy"

Think of cooking a massive feast for 1,000 people:

Double Precision (The Traditional Way): You weigh every single grain of salt with a laboratory scale and measure every drop of water with a pipette. It is perfect, but it takes forever, and you’ll run out of counter space (memory) before you finish.
Mixed-Precision (The Paper’s Way): You use the laboratory scale for the expensive spices (the critical math), but you use a standard measuring cup for the flour and water (the big picture). You might not be accurate to the micro-gram, but the soup still tastes delicious, and you finished the meal before the guests left!

What did they find? (The Results)

The researchers tested this on several complex "math puzzles." Here is what they discovered:

The "Good Enough" Rule: For certain tasks—like calculating the "energy" of a system (the $H_2$ norm)—using lower precision was almost as good as the expensive way. It’s like realizing that even if your sketch isn't perfect, you can still tell exactly how much food is on the table.
The "Stagnation" Trap: They noticed that if you go too low-quality with your sketches, you eventually hit a wall. You stop getting better, and your "map" starts to look blurry. This is called stagnation.
Memory Savings: Their main goal was to save "counter space" (memory). By using lower precision for the big parts, they can handle much larger problems without crashing the computer.

Summary for the Non-Scientist

This paper is a blueprint for efficiency. It proves that in the world of massive computer simulations, you don't need to be a perfectionist at every single step. By being "smartly messy"—using high precision where it matters and low precision where it doesn't—we can solve much bigger, more complex problems faster and with less computer memory.

Technical Summary: Towards a Mixed-Precision ADI Method for Lyapunov Equations

1. Problem Statement

The paper addresses the numerical solution of the continuous-time Algebraic Lyapunov Equation (ALE):
$L(X) := A^*XE + E^*XA + GSG^* = 0$
where $A$ and $E$ are large, sparse matrices, and the constant term is low-rank ( $g \ll n$ ). In large-scale applications like optimal control and model order reduction, the solution $X$ is typically approximated using a low-rank factorization $X \approx ZYZ^*$ .

The authors identify a significant bottleneck in large-scale computations: memory consumption. While the inner factor $Y$ is small, the outer factor $Z$ grows with each iteration of the Alternating-Directions Implicit (ADI) method, requiring substantial storage. The research seeks to reduce this memory footprint by employing mixed-precision arithmetic without sacrificing the accuracy of the solution.

2. Methodology

The authors propose a novel Mixed-Precision Low-Rank ADI (Algorithm 1). The core idea is to assign different IEEE 754 precisions (Single $\epsilon_S$ or Double $\epsilon_D$ ) to different components of the ADI iteration based on their impact on memory and accuracy.

They define three distinct precision levels:

$\epsilon_Z$ (Outer Solution): The precision used to accumulate the overall solution factor $Z$ .
$\epsilon_{VR}$ (Outer Increment/Residual): The precision used for the increment factor $V_k$ and the residual factor $R_k$ .
$\epsilon_{TY}$ (Inner Low-Rank Factors): The precision used for the inner factors $T$ and $Y$ .

The proposed hierarchy for minimizing memory is $\epsilon_Z \geq \epsilon_{VR} \geq \epsilon_{TY}$ . The study tests several configurations:

ADI(D, D, D): Uniform double precision (baseline).
ADI(S, D, D): Single precision for the solution $Z$ , double for others.
ADI(S, S, D): Single precision for $Z$ and increments, double for inner factors.
ADI(S, S, S): Uniform single precision.

The implementation uses a column-wise applied GMRES with an ILU(0) preconditioner to solve the linear systems within the ADI iterations.

3. Key Contributions

First Application of Mixed-Precision to LR-ADI: This work marks the inaugural attempt to apply mixed-precision strategies specifically to the low-rank ADI algorithm.
Memory-Centric Optimization: Unlike many mixed-precision studies that focus on speed, this work prioritizes reducing the maximum memory required during the ADI process.
Empirical Framework: The authors provide a rigorous comparison between implicit residuals (internal to the algorithm) and explicit residuals (the actual error in the Lyapunov equation), revealing critical insights into how precision affects convergence.

4. Results and Findings

The authors tested the method on three benchmark systems: a Steel Profile (heat transfer), a Chip (cooling), and a Triple Chain (mechanical system).

Convergence vs. Accuracy: While the implicit residuals (which guide the algorithm) often converge to the target tolerance even in single precision, the explicit residuals (the true error) often stagnate or diverge when lower precision is used.
The "H2 Norm" Advantage: For specific applications like computing the $H_2$ norm of a system, mixed-precision variants are highly competitive. Even when the solution $X$ itself is less accurate, the derived $H_2$ norm remains nearly identical to the double-precision result.
Performance Trade-offs:
- ADI(S, D, D) provides a middle ground: it yields solutions with significantly lower residuals than uniform single precision while using half the storage of double precision.
- ADI(S, S, D) is faster than the double-precision version but does not necessarily provide better solution quality than uniform single precision unless specific compression techniques are optimized.
Stagnation: The study highlights that the explicit residual tends to stagnate at a certain point in the iteration when using lower precision, a phenomenon that can be used for "stagnation detection."

5. Significance

This paper is significant for the field of large-scale numerical linear algebra and control theory. It demonstrates that mixed-precision is a viable path toward scaling Lyapunov solvers to even larger systems where memory is the primary constraint.

The findings suggest that for many engineering applications—where the goal is to compute a specific property (like an $H_2$ norm) rather than the full matrix $X$ —mixed-precision ADI offers a highly efficient alternative to traditional double-precision methods. It also opens doors for future research into adaptive-precision ADI, where the algorithm could automatically switch to lower precision as it approaches convergence.