Introduction
In control theory and signal processing, the controllability Gramian is a fundamental object used to quantify the energy required to move a system's state. For a linear system described by $\dot{x} = Ax + Bu$, the finite horizon Gramian $G$ over an interval $[0, T]$ is defined as:
$$G(T) = \int_0^T e^{As} BB^* e^{A^*s} ds$$
While theoretically straightforward, computing $G$ accurately in finite-precision arithmetic is a significant challenge. Standard approaches often involve solving a differential equation or computing the integral directly, followed by a Cholesky decomposition ($G = U^*U$) for downstream tasks like state-space balancing or Kalman filtering. However, Gramians are frequently ill-conditioned or near-singular. Computing the full matrix $G$ before factoring it often leads to numerical instability, where rounding errors can cause the Cholesky algorithm to fail or produce inaccurate results.
This paper by Tony Stillfjord and Filip Tronarp introduces a robust "scaling-and-squaring" algorithm that simultaneously computes the matrix exponential $e^{AT}$ and the Cholesky factor $U$ of the Gramian, bypassing the unstable intermediate step of forming $G$ entirely.
Methodology: Scaling, Squaring, and QR Propagation
The authors' approach builds upon the scaling-and-squaring method, the standard numerical technique for computing the matrix exponential. The core innovation lies in applying a doubling formula to the Gramian and propagating its Cholesky factor through QR decompositions.
The Doubling Formula
Just as the matrix exponential satisfies $e^{A(2\tau)} = (e^{A\tau})^2$, the finite horizon Gramian satisfies a specific doubling relation. If $G(\tau)$ is the Gramian over interval $\tau$, then:
$$G(2\tau) = G(\tau) + e^{A\tau} G(\tau) (e^{A\tau})^*$$
By working with the Cholesky factor $U$ such that $G = U^*U$, the authors reformulate this addition as a concatenation of factors. Instead of adding matrices, they use a QR decomposition to find a new factor $U(2\tau)$ from the components of $U(\tau)$ and $e^{A\tau}$. This "factor-form" propagation ensures that the resulting Gramian is always symmetric and positive semi-definite by construction, significantly improving numerical stability.
Petrov-Galerkin Initialization
A critical component of any doubling recursion is the accuracy of the starting point. The authors derive a novel initialization scheme using a Petrov-Galerkin approximation in a shifted Legendre basis. They demonstrate a connection between diagonal Padé approximants (commonly used for $e^A$) and these polynomial approximations, providing a rigorous theoretical foundation for the initial approximations of both the exponential and the Gramian factor.
Backward Error Analysis
The paper provides a formal proof of backward stability. The authors show that the computed results are the exact solutions to a problem with slightly perturbed input matrices. This guarantee ensures that the method achieves accuracy near the limits of double-precision arithmetic ($u \approx 10^{-16}$).
Experimental Results
The method was implemented in the Julia package FiniteHorizonGramians.jl and evaluated against several benchmarks:
- MatrixDepot.jl Suite: Testing on a wide variety of 10x10 matrices from the standard Julia collection showed that the relative error remained remarkably close to machine epsilon across diverse numerical edge cases.
- Laguerre Networks: In systems where the Gramian has a known closed-form solution ($G = I - e^A e^{A^*}$), the algorithm maintained high precision even as the system dimension increased to 100. Traditional methods often struggle in these scenarios as the matrices become increasingly ill-conditioned.
- Efficiency: The computational overhead is kept low, as each doubling step requires only a small number of matrix multiplications and one QR decomposition.
Insights and Limitations
The primary insight of this work is the preservation of the "square root" form. By avoiding the formation of $BB^*$ or $G$, the algorithm maintains a manageable dynamic range for numerical values. The authors also found that computing the Gramian accurately requires slightly more "scaling" (more doubling steps) than computing the matrix exponential alone, and they provide optimized parameters to guide this process.
While highly effective for dense matrices of moderate size (up to several thousand variables), the algorithm is not designed for massive, sparse systems where Krylov subspace methods remain the preferred choice. However, for the dense problems common in control engineering and signal processing, this method provides a new gold standard for reliability and precision.
Conclusion
By rethinking the scaling-and-squaring algorithm through the lens of QR propagation and Petrov-Galerkin initialization, Stillfjord and Tronarp have developed a robust solution to a long-standing problem in computational control theory. Their method ensures that even nearly singular Gramians can be factored accurately, providing a stable foundation for complex system analysis.
Summary updated