Computing the Kalman form

Clément Pernet, Aude Rondepierre, Gilles Villard

Abstract

We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the characteristic polynomial. The cost is a logarithmic number of matrix multiplications. To our knowledge, this improves the best previously known algebraic complexity by an order of magnitude. Then we also present a cubic algorithm proven to more efficient in practice.

Introduction: The Challenge of Kalman Decomposition

In linear control theory, the Kalman decomposition is a fundamental tool for understanding system dynamics. It partitions a system into controllable and uncontrollable components, a necessary step for designing effective controllers or filters. Despite its importance, computing this form for large-scale systems has historically been a significant computational bottleneck.

The primary difficulty lies in the "Krylov matrix"—a large matrix constructed by repeatedly applying a system matrix $A$ to an input matrix $B$. Traditional methods for identifying the linearly independent columns of this matrix to find the controllable subspace are computationally expensive, often scaling poorly as the system size $n$ increases. This paper bridges the gap between abstract control theory and modern high-performance computer algebra to accelerate these computations.

Algorithmic Approaches

The authors propose two distinct algorithmic strategies to address these challenges:

1. The Keller-Gehrig Adaptation

By adapting an algorithm originally designed for computing characteristic polynomials, the authors utilize a "doubling" scheme. This involves computing powers of the matrix $A$ (e.g., $A, A^2, A^4, \dots, A^{2^i}$) to build Krylov iterates using fast matrix multiplication. This approach leverages the matrix multiplication exponent $\omega$ (where $\omega \approx 2.37$), achieving a theoretical complexity of $O(n^\omega \log n)$.

2. LQUP Factorization and Compressed Krylov Matrices

To maintain compatibility with fast matrix multiplication, the authors define a "compressed" version of the Krylov matrix containing only the first $r$ linearly independent columns. They employ LQUP factorization—a variation of LU decomposition—to perform block eliminations efficiently.

Transformation of the Krylov matrix into a structured form using LQUP factorization.

3. Kalman-LUK (LU-Krylov)

Recognizing that high-performance "fast" algorithms can have significant overhead, the authors also propose a cubic ($O(n^3)$) variant. This version, Kalman-LUK, utilizes matrix-vector products rather than matrix-matrix products. While asymptotically "slower," it avoids the $\log n$ factor and is generally more efficient for matrices of practical, real-world sizes.

Key Insights

  • Algorithmic Symmetry: A core insight is that computing the Kalman form is algorithmically similar to computing the characteristic polynomial. This allows the application of advanced computer algebra techniques to control theory.
  • Lexicographical Maximality: By selecting the first linearly independent columns from left to right, the authors ensure a unique basis that reveals the system's structure in a "Hessenberg polycyclic form."
  • Efficiency through Sparsity: Once the compressed Krylov matrix is identified, the remaining blocks of the Kalman form can be recovered using triangular system solves, which are computationally cheaper than general matrix inversions.

Results and Complexity Breakthrough

The paper establishes a new upper bound for the algebraic complexity of the Kalman form: $O(n^\omega \log n)$. This represents a major theoretical advancement over previous results. Furthermore, the authors provide a method to recover the Hessenberg polycyclic form in only $O(\phi n^2)$ operations, where $\phi$ is the number of blocks.

The resulting Kalman form showing the block-diagonal structure.

The resulting structure, as shown in the figure above, clearly delineates the controllable subspaces through its block-diagonal arrangement, facilitating further system analysis and control design.

Limitations and Future Work

While the paper makes significant strides in algebraic complexity, it primarily focuses on field operations and does not extensively explore numerical stability. In floating-point arithmetic, rounding errors can impact the results of "fast" matrix algorithms. Additionally, while the cubic variant is expected to be faster in practice, the paper lacks empirical benchmarks against standard libraries like SLICOT or LAPACK. Future research should involve implementing these algorithms in high-performance libraries to determine the crossover point where the $O(n^\omega \log n)$ algorithm begins to outperform the $O(n^3)$ version.

Summary updated

Abstract

We present two algorithms for the computation of the Kalman form of a linear control system. The first one is based on the technique developed by Keller-Gehrig for the computation of the characteristic polynomial. The cost is a logarithmic number of matrix multiplications. To our knowledge, this improves the best previously known algebraic complexity by an order of magnitude. Then we also present a cubic algorithm proven to more efficient in practice.
BibTeX
@misc{pernet2005computing,
  author = {Clément Pernet and Aude Rondepierre and Gilles Villard},
  title = {{Computing the Kalman form}},
  year = {2005},
  eprint = {cs/0510014},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0510014},
}
Figure