Krylov Projections for High Dimensional Reachability Analysis

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 213 papers20 conceptsfrozen 2026-10-04

In modern engineering, we often need to predict the behavior of systems with an overwhelming number of variables. Whether it is the heat distribution in a complex processor, the electromagnetic interference in an integrated circuit, or the safety of a high-speed braking system, these models can easily reach millions of dimensions.

The fundamental challenge is that as the number of states ($n$) grows, the computational cost of simulating or verifying these systems grows even faster. Traditional methods for solving linear differential equations rely on the matrix exponential, $e^{At}$, an operation that becomes prohibitively expensive when $n$ is large. This "state explosion" makes formal verification—proving that a system will never enter an unsafe state—seem impossible for real-world complexity.

Recent research has overcome this bottleneck by shifting the focus from the full state space to a much smaller, carefully chosen Krylov subspace.

The Bottleneck of Matrix Exponentials

To understand why this works, we first need to see why standard methods fail. In a linear system $\dot{x} = Ax + Bu$, the state at any time $t$ is determined by the action of the matrix exponential $e^{At}$ on the initial state.

For a system with a million variables, $A$ is a $10^6 \times 10^6$ matrix. Calculating $e^{At}$ directly is computationally impossible. Even "conservative time discretization"—the process of overapproximating reachable states over small intervals—suffers from a trade-off between precision and cost. As Christian Schilling and Marcelo Forets demonstrated in Conservative Time Discretization: A Comparative Study, simple first-order methods are fast but lose precision, while more accurate methods struggle to scale.

Intuition: Finding the Relevant Subspace

The key insight is that even in a million-dimensional system, the dynamics we care about often live in a much smaller subspace. If we want to know how a system evolves from an initial state $v$, we don't need the full matrix $e^{At}$; we only need the result of the product $e^{At}v$.

This product can be approximated by looking at the Krylov subspace: $$\mathcal{K}_m(A, v) = \text{span}\{v, Av, A^2v, \dots, A^{m-1}v\}$$ By repeatedly applying the matrix $A$ to the vector $v$ (a relatively cheap operation), we build a basis that captures the most significant directions of the system's evolution. As Matthias Althoff explains in Reachability Analysis of Large Linear Systems With Uncertain Inputs in the Krylov Subspace, we can use the Arnoldi iteration to project the high-dimensional matrix $A$ into a tiny, dense matrix $H$ in the Krylov subspace.

Instead of computing $e^{At}$ for a million-dimensional matrix, we compute $e^{Ht}$ for a matrix that might only be $50 \times 50$. This reduces computation times from days to hours, or even minutes, while maintaining rigorous error bounds.

Scaling to Millions of Dimensions

This projection approach has transformed the field of formal verification. The annual ARCH-COMP competitions highlight this progress. In ARCH-COMP20 and ARCH-COMP21, researchers including Goran Frehse and Stanley Bak showed that tools using Krylov and Lanczos projections can verify safety properties for models with one million dimensions in under a minute.

The power of this method isn't just speed; it's the ability to handle uncertainty. By projecting not just the dynamics but also the input sets, researchers can verify how a system responds to "arbitrarily varying uncertain inputs," ensuring safety even when the environment is unpredictable.

Applications Across Domains

While reachability analysis is a primary driver, the intuition of Krylov projection applies wherever large-scale linear dynamics appear:

  • Model Order Reduction (MOR): In integrated circuit design, Dimitrios Garyfallou and colleagues used an "Extended Krylov Subspace" (EKS) to make mathematically rigorous methods like Balanced Truncation viable for million-element circuits, as detailed in MORCIC.
  • Quantum Physics: Li Jingze and Xiantao Li applied these projections to Stochastic Schrödinger equations, allowing for larger time steps in quantum simulations by replacing massive matrix operations with small-scale approximations.
  • Parameter Varying Systems: For systems where dynamics change based on external parameters (LPV systems), Mert Bastug and Roland Tóth showed in Moment matching based model reduction for LPV state-space models that iterative subspace methods bypass the exponential memory requirements that previously caused standard algorithms to fail.

Why It Works

Krylov subspace methods work because they exploit the structure of the problem. We rarely need to know what a million-dimensional system does in every possible direction; we only need to know what it does in the directions it is actually moving. By iteratively building a basis from the system's own operators, we create a "custom fit" low-dimensional map that preserves the essential dynamics while discarding the computational noise of the full state space.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 15 papers
  2. Version 1 · 2026-10-04 · 13 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_krylov_subspace_projection_85947691,
  title = {Krylov subspace projection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/krylov-subspace-projection/rdr_85947691a3ca49cf892c941adb33429b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_krylov_projections_for_high_dimensional__85947691_v1,
  title = {Krylov Projections for High Dimensional Reachability Analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/krylov-projections-for-high-dimensional-reachability-analysis/rdr_85947691a3ca49cf892c941adb33429b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}