Krylov Subspace Projection for High Dimensional Dynamical Systems

22 concepts18 papers1 proposal

Imagine trying to verify the safety of a modern integrated circuit, a massive power grid, or a complex chemical reaction. These systems are frequently modeled as linear differential equations:

$$\dot{x}(t) = Ax(t) + Bu(t)$$

where the state vector $x(t)$ represents the system's variables at time $t$. For realistic systems, the dimension $n$ of the matrix $A$ can easily scale from thousands to billions of variables (Bak et al.).

To simulate or formally verify this system, we must compute its analytical solution, which fundamentally relies on the matrix exponential:

$$x(t) = e^{At}x(0) + \int_0^t e^{A(t-\tau)}Bu(\tau)d\tau$$

Here lies the computational bottleneck: evaluating the matrix exponential $e^{At}$ directly for a dense matrix requires $O(n^3)$ operations and $O(n^2)$ memory. When $n$ is in the millions, standard numerical methods exhaust available memory and become completely intractable.

However, a profound insight changes the problem entirely: we rarely need to compute the full matrix $e^{At}$. Instead, we only need to compute how $e^{At}$ acts on a specific vector $v$ (such as the initial state $x(0)$ or the input matrix $B$). The trajectory of a physical system does not wander aimlessly through its high-dimensional state space; rather, its evolution is tightly constrained by its underlying dynamics. Krylov subspace projection exploits this property to map massive systems into tiny, computationally manageable spaces.


The Intuition: Trajectories are Trapped in Subspaces

To understand why Krylov subspaces naturally capture system dynamics, consider the Taylor series expansion of the matrix exponential acting on a vector $v$:

$$e^{At}v = v + tAv + \frac{t^2}{2!}A^2v + \frac{t^3}{3!}A^3v + \dots$$

Notice the structure of the vectors in this infinite sum. Every single term is a scalar multiplied by a vector generated by repeatedly applying the matrix $A$ to the initial vector $v$. If we truncate this series at $k$ terms, the resulting approximation lives entirely within the subspace spanned by these vectors:

$$\mathcal{K}_k(A, v) = \text{span}\{v, Av, A^2v, \dots, A^{k-1}v\}$$

This is the Krylov subspace. The core idea of Krylov subspace projection is to construct an orthonormal basis for $\mathcal{K}_k(A, v)$, project the massive $n \times n$ matrix $A$ down to a tiny $k \times k$ matrix, compute the exponential of that tiny matrix exactly, and then lift the result back up to the original high-dimensional space.

High-Dimensional Space (Dimension n)
┌────────────────────────────────────────────────────────┐
│  Initial Vector v                                      │
│   │                                                    │
│   ▼                                                    │
│  [ Arnoldi / Lanczos Iteration ]                       │
│   │                                                    │
│   └───────────────┐                                    │
│                   ▼                                    │
│         Low-Dimensional Subspace (Dimension k << n)    │
│         ┌────────────────────────────────────┐         │
│         │  Projected Matrix: H_k = V_k^T A V_k│        │
│         │  Compute exact exponential: e^{H_k}│         │
│         └────────────────────────────────────┘         │
│                   │                                    │
│   ┌───────────────┘                                    │
│   ▼                                                    │
│  Lifted Solution: v_approx = V_k e^{H_k} e_1           │
└────────────────────────────────────────────────────────┘

The Mechanism: Arnoldi and Lanczos Projections

To perform this projection robustly, researchers use iterative algorithms like the Arnoldi iteration (for general matrices) or the Lanczos iteration (for symmetric matrices).

Starting with a normalized vector $v$, the Arnoldi iteration systematically builds an orthonormal basis $V_k = [v_1, v_2, \dots, v_k] \in \mathbb{R}^{n \times k}$ for the Krylov subspace. Crucially, the algorithm satisfies the fundamental relation:

$$A V_k = V_k H_k + h_{k+1,k} v_{k+1} e_k^T$$

where $H_k = V_k^T A V_k$ is a $k \times k$ upper Hessenberg matrix (a nearly triangular matrix), and $e_k$ is the $k$-th standard basis vector. Because $V_k$ consists of orthonormal columns ($V_k^T V_k = I_k$), $H_k$ represents the direct projection of the massive operator $A$ onto our low-dimensional Krylov subspace.

We can now approximate the action of the matrix exponential by substituting this projection:

$$e^{At}v \approx V_k e^{H_k t} V_k^T v = \|v\| V_k e^{H_k t} e_1$$

By choosing a small subspace dimension (e.g., $k = 30$), we replace the impossible task of exponentiating a matrix of size $1,000,000 \times 1,000,000$ with a trivial calculation on a dense $30 \times 30$ matrix.


Scaling Reachability Analysis and Formal Verification

One of the most impactful applications of this technique is in the formal verification of safety-critical systems. In reachability analysis, the goal is to prove that a system, starting from a set of initial states and subject to uncertain inputs, can never enter an unsafe region of the state space.

As documented in successive paradigm reports from the ARCH competition (Althoff et al.; Althoff et al.; Althoff et al.), standard set-propagation algorithms fail due to memory exhaustion when tracking high-dimensional geometry. Forets et al. note that Krylov subspace methods bypass these bottlenecks entirely by operating on the reduced state space, enabling tools to scale to models with hundreds of thousands of variables.

Turning Approximations into Guarantees

For formal verification, an approximation is insufficient; we require mathematical certainty. To bridge this gap, Althoff and Bak et al. introduce a posteriori error bounds. By analyzing the remainder term of the Krylov truncation (the $h_{k+1,k}$ factor from the Arnoldi relation), the authors calculate a rigorous, conservative bound on the maximum possible approximation error. This error is then bloated onto the reachable set as an extra uncertainty zone, preserving the mathematical rigor required for safety verification while unlocking massive speedups.


Handling Stiff Systems: Rational Krylov Methods

While standard Krylov projections excel for many systems, they encounter difficulties when dealing with stiff systems—models containing dynamics that operate across wildly different timescales, such as high-frequency parasitic oscillations alongside slow thermal trends. To capture high-frequency behaviors, a standard Taylor-series-based Krylov subspace requires an impractically large dimension $k$.

To solve this, Zhuang et al. utilize Rational Krylov subspace methods to simulate massive power delivery networks. Instead of building a subspace using powers of $A$, rational methods use a "shift-and-invert" strategy, constructing spaces from:

$$\mathcal{K}_k(A, v) = \text{span}\left\{ v, (A - \sigma_1 I)^{-1}v, (A - \sigma_2 I)^{-1}v, \dots \right\}$$

By choosing appropriate shifts $\sigma_i$, the inversion operation acts as a mathematical filter that maps the dominant long-term and high-frequency behaviors directly into a very compact subspace. This mitigates memory bottlenecks and accelerates simulations by orders of magnitude.


Broader Horizons: Model Reduction and Quantum Dynamics

The utility of Krylov projections extends far beyond reachability analysis into several domains of computational science:

  • Model Order Reduction (MOR): Instead of projecting a single trajectory, researchers use Krylov methods to permanently compress large dynamical systems into compact, real-time executable models. Antoulas et al. demonstrate how Krylov projections achieve frequency-domain moment matching, a property extended by Wang et al. to simplify complex neutral systems featuring time delays. Similarly, Elman et al. utilize block Krylov projections to solve large-scale Lyapunov equations, making the identification of bifurcations in fluid flows computationally feasible.
  • Stochastic and Quantum Simulation: In open quantum systems governed by the stochastic Schrödinger equation, Jingze et al. employ Krylov projections to evaluate large matrix exponentials stably, allowing for significantly larger simulation time steps. In molecular dynamics, Michels et al. use Krylov methods to analytically integrate stiff covalent bond forces, bridging the gap between theoretical exact solutions and practical computational speed.
  • Data-Driven Dynamics: Modern machine learning approaches also leverage these algebraic foundations. Iwata et al. integrate Krylov subspace methods with Koopman operator theory to efficiently compute infinite-dimensional operators for time-series forecasting. To handle non-linearities without combinatorial explosion, Devonport et al. show that restricting data-driven reachability analysis to a lower-dimensional subspace of interest drastically reduces sample complexity while maintaining rigorous safety bounds.

By recognizing that the complex behavior of high-dimensional systems is often trapped within low-dimensional algebraic structures, Krylov subspace projection transforms intractable differential equations into highly efficient, verifiable, and scalable models.

Key Foundational Work

Lyapunov Inverse Iteration for Identifying Hopf Bifurcations in Models of Incompressible Flow (2012) — contributed 1 concept elements to this direction.
Model Reduction of Large-Scale Dynamical Systems (2004) — contributed 1 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_krylov_subspace_projection_85947691_v2,
  title = {Krylov subspace projection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/krylov-subspace-projection/rdr_85947691a3ca49cf892c941adb33429b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake