Revisiting The PBH Test: Fast Uncontrollability Certificates via Krylov Methods

Technical Summary: Revisiting the PBH Test via Fast Uncontrollability Certificates

Problem Statement
The paper addresses the challenge of efficiently certifying the uncontrollability of discrete-time linear time-invariant (LTI) systems, particularly in large-scale networks where the state dimension $n$ is in the thousands. Traditional methods for assessing controllability face significant computational bottlenecks:

1. Rank Condition: Constructing the controllability matrix $\mathcal{C}_n = [B, AB, \dots, A^{n-1}B]$ is memory-intensive and computationally prohibitive ($O(n^3)$ or worse) for large sparse systems.
2. PBH Test: While the Popov-Belevitch-Hautus (PBH) test avoids forming $\mathcal{C}_n$, it typically requires a global eigendecomposition of $A$ or iterative spectral routines. These approaches are computationally expensive ($O(n^3)$ for dense matrices) and can be numerically ill-conditioned, especially when dealing with weakly damped modes or systems where only specific state maneuvers are of interest.

Existing approaches often remain "mode-centric," requiring the computation of invariant subspaces over spectral regions even when the user only needs to determine if a specific target displacement is reachable.

Methodology
The authors propose a "target-centric" approach that reframes the controllability problem through the lens of finite-horizon reachability and convex duality.

1. Primal Formulation: The problem is cast as a Minimum Energy Control Problem (MECP). The system is driven from an initial state $x_0$ to a target $x_N$ in $N$ steps. The displacement $\Delta x = x_N - A^N x_0$ must satisfy the linear constraint $\mathcal{C}_N u = \Delta x$. If $\Delta x$ lies outside the range of the controllability matrix $\mathcal{C}_N$, the MECP is primal infeasible.
2. Dual Certificates: Drawing on the Fredholm Alternative (a specific instance of Farkas' Lemma), the paper establishes that primal infeasibility is certified by a dual vector $y$ such that:
   • $\mathcal{C}_N^\top y = 0$ (orthogonality to the reachable subspace)
   • $y^\top \Delta x \neq 0$ (the target requires movement in an unreachable direction)
     Crucially, this certificate $y$ can be computed without explicitly forming $\mathcal{C}_N$.
3. Spectral Interpretation: The core theoretical contribution is proving that any such infeasibility certificate $y$ is a linear combination of the uncontrollable generalized left eigenvectors of $A$. Specifically, $y$ lies in the uncontrollable subspace $\mathcal{V}_{unc} = \text{Null}(\mathcal{C}_N^\top)$.
4. Algorithmic Framework:
   • Algorithm 1 (Certification): Uses shifted inverse iteration on $A^\top$ with a set of candidate shifts $\Sigma$ (derived from Gershgorin bounds) to find a vector $y$ that is nearly orthogonal to $B$ ($B^\top y \approx 0$) and violates the target constraint ($|y^\top \Delta x| > \tau$). This avoids global eigendecomposition and uses only matrix-vector products.
   • Algorithm 2 (Spectral Extraction): Once a certificate $y$ is found, the algorithm constructs a Krylov subspace $\mathcal{K}_r(A^\top, y)$. By solving a small-scale least-squares problem to find the coefficients of the minimal polynomial of $A^\top$ restricted to this subspace, the specific uncontrollable eigenvalues associated with $y$ are extracted as roots of a low-degree polynomial ($r \ll n$).

Key Contributions

• Theoretical Link: The paper establishes a rigorous connection between geometric infeasibility certificates (from convex optimization) and the spectral characterization of uncontrollability (PBH test). It proves that the null space of $\mathcal{C}_N^\top$ is spanned by uncontrollable generalized left eigenvectors.
• Target-Aware Diagnosis: Unlike the classical PBH test which identifies all uncontrollable modes, the proposed method isolates only the modes that obstruct a specific desired maneuver ($\Delta x$).
• Scalable Implementation: The authors develop a "certificate-and-extraction" (C+E) framework that:
  • Avoids forming the controllability matrix $\mathcal{C}_N$.
  • Avoids global eigendecomposition.
  • Reduces spectral computation to finding roots of a polynomial of degree $r$ (where $r$ is the number of obstructing modes), rather than solving an $n \times n$ eigenvalue problem.
• Numerical Validation: The method is validated on large-scale traffic/routing networks (up to $n=1000$) with both dense and sparse topologies.

Results
Experimental results on benchmark systems demonstrate significant computational advantages:

• Efficiency: In dense systems with $n=1000$, the C+E approach is approximately 3 times faster than the classical PBH test (using full eigendecomposition) and the controllability Gramian method.
• Sparse Systems: The advantage is more pronounced in sparse networks, where C+E is roughly 18 times faster than PBH and Gramian methods.
• Accuracy: The method successfully recovers planted uncontrollable eigenvalues. The "nearest-mode error" for extracted eigenvalues remains low, confirming that the certificates accurately encode the obstructing spectral information.
• Comparison: The proposed method outperforms least-squares approaches (both dense and matrix-free) which were found to be the slowest among the tested methods.

Significance and Claims
The paper claims to provide a "fast uncontrollability certificate" that bridges the gap between optimization-based feasibility testing and modal analysis. Its significance lies in:

1. Scalability: Enabling controllability analysis for large-scale dynamic networks (thousands of nodes) where traditional spectral methods are impractical.
2. Diagnostic Precision: Offering a diagnostic tool that identifies which specific modes prevent a specific maneuver, rather than just providing a binary "controllable/uncontrollable" verdict.
3. Computational Economy: Demonstrating that one can extract spectral information (uncontrollable eigenvalues) from optimization certificates without the heavy cost of global eigendecomposition.

The authors note limitations, specifically that the spectral extraction (Algorithm 2) relies on the number of obstructing modes ($r$) being modest. As $r$ increases, the Krylov matrix may become ill-conditioned, and root-finding for the minimal polynomial becomes sensitive to numerical perturbations. The work is focused on discrete-time systems, though the authors note the conceptual extension to continuous time is straightforward.