Breaking the Exponential Scaling of Grid-Based Solvers

87 concepts87 papers1 proposal

For decades, the primary obstacle in computational science has been the "curse of dimensionality." When we attempt to simulate physical systems—whether the flow of air over a wing, the movement of a plasma, or the pricing of a complex financial derivative—we usually rely on a grid. We divide space into a mesh of points and calculate how the system evolves at each intersection.

The problem is that grids do not scale. If a one-dimensional line requires 100 points, a three-dimensional cube requires $100^3$ (one million) points. By the time we reach the six-dimensional phase space required for kinetic simulations, we need $100^6$ (one trillion) points, exceeding the memory capacity of modern supercomputers. As noted by Einkemmer et al., this exponential growth makes traditional deterministic solvers prohibitively expensive for practical engineering.

To solve high-dimensional Partial Differential Equations (PDEs), researchers are moving away from fixed grids toward methods that exploit the underlying structure of the solution.

Mesh-free Representations via Neural Networks

The most significant shift in this field is the use of deep neural networks as "mesh-free" function approximators. Unlike a grid, which must be defined before the simulation begins, a neural network can be evaluated at any point in a continuous domain.

This approach works because neural networks are not bound by the geometry of a mesh; they learn to represent the solution manifold itself. Berner et al. provided a rigorous mathematical foundation for this, proving that deep learning can overcome the curse of dimensionality for Black-Scholes and Kolmogorov equations by achieving errors that do not explode as dimensions increase. Similarly, Lu demonstrated that for certain elliptic PDEs, the generalization error of neural solvers remains tractable even in high-dimensional spaces.

By treating the PDE as a training objective—often called Physics-Informed Neural Networks (PINNs)—researchers can sample points randomly or adaptively. For instance, Zeng et al. developed an adaptive sampling strategy that focuses training on high-density regions, allowing them to solve fractional Fokker-Planck equations in unbounded spaces where a grid would be impossible to define.

Exploiting Hidden Simplicity with Low-Rank Methods

While neural networks offer a flexible way to represent functions, another strategy involves identifying that high-dimensional data is often "simpler" than it looks. In many physical systems, the variables are not independent; they are highly correlated.

Low-rank methods exploit this by decomposing a massive high-dimensional tensor into a product of smaller, low-dimensional components. Einkemmer et al. applied this to the Boltzmann-BGK equation, capturing complex fluid dynamics like shock waves at a fraction of the cost of traditional solvers. In the realm of quantum chemistry and electromagnetics, Marcati proved that functions with point singularities can be approximated with exponential efficiency using quantized tensor formats, where the computational complexity grows only polylogarithmically with the desired accuracy.

These methods work because they restrict the search for a solution to a low-dimensional manifold, effectively filtering out the "noise" of the high-dimensional space that doesn't contribute to the physics.

Reformulating PDEs as Optimization Problems

A third pillar of this research direction involves changing the mathematical framing of the problem. Traditional solvers try to satisfy the PDE at every point on a grid. Newer methods, however, frame the PDE as an optimization or a game.

For example, Zang et al. introduced Weak Adversarial Networks (WAN), which frame the PDE as a minimax game between a "solution" network and a "test function" network. This bypasses the need for strong derivatives and grids entirely, making it effective for high-dimensional problems with singularities.

In other cases, researchers swap discretization for optimization techniques borrowed from compressive sensing. Darbon et al. showed that high-dimensional Hamilton-Jacobi equations—critical for control theory—can be solved orders of magnitude faster by using optimization algorithms that do not rely on spatial grids. Similarly, Park et al. paired an implicit solution formula with deep learning to solve 40-dimensional problems on a single GPU, a feat that would require more grid points than there are atoms in the universe using classical methods.

The Path Forward

The common thread across these papers is a move away from local, discrete representations (grids) toward global, continuous ones (neural networks and tensors). Whether through the polynomial complexity of Multilevel Picard schemes proposed by Jentzen or the axial factorization in Transformers used by Li et al., the goal remains the same: to make high-dimensional physics as computationally tractable as the three-dimensional world we inhabit.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_exponential_comp_098bd59b,
  title = {curse of dimensionality (exponential complexity scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-exponential-complexity-scaling/rdr_098bd59bb2464087ba7f2803f99f4b30},
  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_curse_of_dimensionality_exponential_comp_098bd59b_v1,
  title = {curse of dimensionality (exponential complexity scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-exponential-complexity-scaling/rdr_098bd59bb2464087ba7f2803f99f4b30/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake