Towards a mixed-precision ADI method for Lyapunov equations
Jonas Schulze, Jens Saak · 2025
Read Towards a mixed-precision ADI method for Lyapunov equations by Jonas Schulze, Jens Saak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00722.txt.
Introduction
Jonas Schulze and Jens Saak trim the cost of a classic matrix solver by mixing number precision in a 2025 arXiv paper. The solver handles Lyapunov equations, which sit behind control and model shrink tasks. Its low rank form builds the answer step by step from small pieces.
The team runs some steps in single precision and others in double, and tests the mixes. They try storing the running answer, solving the inner systems, and holding the spare parts each in either grade. On first order test systems, keeping the answer in single grade left an error near the full double run. For tasks like a system's energy norm, the mixed runs can rival the full ones at lower cost. Second order cases showed a tighter spread.
Catalog record
| CREATOR | Jonas Schulze, Jens Saak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00722
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards a mixed-precision ADI method for Lyapunov equations Jonas Schulze, Jens Saak Abstract We apply mixed-precision to the low-rank Lyapunov ADI (LR-ADI) by performing certain aspects of the algorithm in a lower working precision. Namely, we accumulate the overall solution, solve the linear systems comprising the ADI iteration, and store the inner low-rank factors of the residuals in various combinations of IEEE 754 single and double precision. We empirically test our implementation on Lyapunov equations arising from first- and second-order descriptor systems. For the first-order examples, accumulating the solution in single-precision yields an almost-as-small residual as for the double-precision solution. For certain applications, like computing the ℋ 2 {\mathcal{H}_{2}} norm of a descriptor system, low- or mixed-precision variants of the ADI can be quite competitive. \msc 15A24, 65F10, 65F45, 65F55 \novelty This work marks the first application of mixed-precision to the low-rank ADI. Our main focus is to keep the maximum memory required during the ADI as low as possible. keywords low-rank Lyapunov ADI, mixed-precision arithmetic 1 Introduction We consider the numerical solution of the continuous-time \ac ALE \mathcal{L}(X):=A^{*}XE+E^{*}XA+GSG^{*}=0, (1) with large and sparse coefficient matrix A\in\mathbb{C}^{n\times n} and a low-rank constant term comprised of the factors G\in\mathbb{C}^{n\times g} and S\in\mathbb{C}^{g\times g} , where g\ll n . This type of equation arises in, e.g., optimal control and model order reduction. We refer to [ 4 , 10 , 36 ] and the references therein for a more detailed introduction. Given the low rank of the constant term in ( 1 ), the solution can, at least numerically, be well approximated by a low-rank factorization [ 28 , 5 , 14 , 31 , 39 ] . We choose the symmetric indefinite factorization, X\approx ZYZ^{*} , with tall and skinny Z\in\mathbb{C}^{n\times z} and Hermitian Y\in\mathbb{C}^{z\times z} , z\ll n , [ 8 , 20 ] . For this kind of large-scale equations with low-rank solutions, the most successful algorithms used recently are the Krylov subspace projection method, e.g., [ 35 , 25 , 18 ] , as well as the \ac ADI method; see [ 34 ] and references therein. The latter will be the focus of this paper. In recent years, driven by the needs of machine learning, hardware capable of computing in lower than IEEE 754 [ 17 ] single precision has been becoming available to the general user. Many algorithms from all fields of mathematics have been found to yield just- or almost-as-good results when using lower precision for parts of their computations, while being faster or consuming less energy. We refer to [ 1 , 15 ] and the references therein for a more detailed introduction. Motivated by [ 2 ] , as a first step towards lower than IEEE 754 [ 17 ] single precision, we seek to employ mixed-precision for aforementioned low-rank factorizations in the context of large-scale matrix equations. For this paper, our motivation is to obtain same-quality solutions to \ac ALE ( 1 ) while using less memory to store the solution. A detailed examination of runtime and energy consumption is out of scope for this initial investigation, and left for future work. 1.1 Notation Throughout the paper, \left\lVert\cdot\right\rVert_{\mathrm{F}} denotes the Frobenius norm. Hermitian transposition of a matrix is denoted by (\cdot)^{*}:\mathbb{C}^{m\times n}\to\mathbb{C}^{n\times m} . We consistently use the same notation for the transposition of a real matrix. The identity matrix is denoted by I_{n}\in\mathbb{R}^{n\times n} , where we may omit the subscript if dimensions are clear from the context. Conceptually, we identify the zero matrix with a rank-zero decomposition [\,]\,[\,]\,[\,]^{*}=0\in\mathbb{R}^{n\times n} . We denote the machine epsilon of a data type by \varepsilon\in\mathbb{R} where 0<\varepsilon\ll 1 . Throughout the paper, we will only use IEEE 754 [ 17 ] precisions single and double, such that we may identify a data type with its machine epsilon. Subscripts of \varepsilon denote the matrices stored in the corresponding data type, for example, \varepsilon_{TY} refers the precision used to store matrices named T and Y . 1 1 1 The subscript does not denote matrix multiplication. 1.2 Low-rank arithmetic To compress a low-rank factorization ZYZ^{*} , we follow [ 20 ] and compute a thin QR-decomposition (pivoted Householder [ 16 , 13 ] ) of Z=Q\hat{Z} using precision \varepsilon_{Z} , and truncate based on an eigendecomposition of \hat{Z}Y\hat{Z}^{*} using \varepsilon_{TY} . 2 2 2 T will be denote an inner low-rank factor akin to Y , whose exact meaning will be introduced later. To compute the norm of ZYZ^{*} , we follow, e.g., [ 27 ] and evaluate \left\lVert\smash{\hat{Z}Y\hat{Z}^{*}}\right\rVert_{\mathrm{F}} using \varepsilon_{TY} . In this sense, throughout the paper, the working precision of certain operations will always follow the storage precision of the matrices involved. We refer the reader to our implementation [ 32 ] for further details. We call ZYZ^{*} with Z\in\mathbb{R}^{n\times z} an order- z approximation. Note that z is only an upper bound to \operatorname{rank}(ZYZ^{*}) . After low-rank compression as described above, the order and rank of a low-rank factorization coincide. 2 Mixed-precision low-rank factorization Let \operatorname{sizeof}(\cdot) denote the number of Bytes needed to store a certain object. Furthermore, let ZYZ^{*} be a proper low-rank factorization, i.e., Z\in\mathbb{R}^{n\times z} with z\ll n . Assuming uniform precision and dense storage for Z and Y , it holds \operatorname{sizeof}(Z)\gg\operatorname{sizeof}(Y). (2) A natural choice to reduce the total storage required is to permit a coarser precision for the factor Z . Now let ZYZ^{*} be an approximation of the true solution X to \ac ALE ( 1 ) obtained via the \ac ADI method, and let RTR^{*} be the corresponding residual, i.e., \mathcal{L}(ZYZ^{*})=RTR^{*}. Recall from [ 20 , Algorithm 3.1] that the inner solution factor Y can be represented as a Kronecker product, Y=-2\operatorname{diag}(\operatorname{Re}(\alpha_{0}),\ldots,\operatorname{Re}(\alpha_{k}))\otimes T. (3) Thus, assuming uniform precision, z\leq n , and dense storage for all matrices but Y , we conclude \displaystyle\operatorname{sizeof}(Z) \displaystyle\geq\operatorname{sizeof}(V) \displaystyle=\operatorname{sizeof}(R) (4) \displaystyle\geq\operatorname{sizeof}(T) \displaystyle=\mathcal{O}(\operatorname{sizeof}(Y)), where \mathcal{O}(\cdot) denotes Landau notation. Similarly, a natural choice to minimize the overall storage required is to permit three precisions \varepsilon_{Z}\geq\varepsilon_{V\!R}\geq\varepsilon_{TY}. (5) \Autoref alg:adi shows a simplified summary of the resulting mixed-precision \ac ADI. For brevity, we omit the handling of complex shifts [ 7 ] . To solve the linear systems in Algorithm 1 , we use a column-wise applied GMRES [ 29 , 22 ] with ILU(0) preconditioner [ 21 , 12 ] . 1 A current limitation of our implementation of Algorithm 1 , see DifferentialRiccatiEquations.jl [ 32 ] , is that the matrices E and A as well as the shifts \alpha_{k} must all be converted to \varepsilon_{V\!R} beforehand. This conversion is necessary to ensure type stability, and thus reduce the number of allocations inside Krylov.jl [ 22 ] , the package that implements GMRES. Input: system matrices A , E , G , and S , parameters \{\alpha_{0},\alpha_{1},\ldots\} , relative tolerance \tau Output: Z:=Z_{k+1}\in\mathbb{C}^{n\times z} and Y:=Y_{k+1}\in\mathbb{C}^{z\times z} such that X\approx ZYZ^{*} solves A^{*}XE+E^{*}XA=-GSG^{*} Initialize solution and residual factors: \hbox{\pagecolor{fill1 bg}\color[rgb]{1,1,1}$Z_{0}$}\leftarrow[\,],\qquad\hbox{\pagecolor{fill3 bg}\color[rgb]{1,1,1}$Y_{0}$}\leftarrow[\,],\qquad\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$R_{0}$}\leftarrow G,\qquad\hbox{\pagecolor{fill3 bg}\color[rgb]{1,1,1}$T$}\leftarrow S 1 for k\leftarrow 0,1,\ldots do 2 Compute increment factor \hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$V_{k}$}\leftarrow{(A^{*}+\alpha_{k}E^{*})}^{-1}\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$R_{k}$} 3 Update residual factor \hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$R_{k+1}$}\leftarrow\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$R_{k}$}-2\operatorname{Re}(\alpha_{k})E^{*}\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$V_{k}$} 4 Augment solution factors: \hbox{\pagecolor{fill1 bg}\color[rgb]{1,1,1}$Z_{k+1}$}\leftarrow\Big[\hbox{\pagecolor{fill1 bg}\color[rgb]{1,1,1}$Z_{k}$}\Big|\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$V_{k}$}\Big],\qquad\hbox{\pagecolor{fill3 bg}\color[rgb]{1,1,1}$Y_{k+1}$}\leftarrow\begin{bmatrix}\hbox{\pagecolor{fill3 bg}\color[rgb]{1,1,1}$Y_{k}$}\\ &-2\operatorname{Re}(\alpha_{k})\hbox{\pagecolor{fill3 bg}\color[rgb]{1,1,1}$T$}\end{bmatrix} 5 if \left\lVert\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$R_{k+1}$}\hbox{\pagecolor{fill3 bg}\color[rgb]{1,1,1}$T\vphantom{R_{k+1}}$}\hbox{\pagecolor{fill2 bg}\color[rgb]{0,0,0}$R_{k+1}$}^{*}\right\rVert_{\mathrm{F}}\leq\tau\left\lVert GSG^{*}\right\rVert_{\mathrm{F}} then break 6 end for 7 Algorithm