Maxwell equations can solve sparse linear systems in physics
Maxwell's equations are universal for sparse linear algebra
Computational Complexity
Summary
Solving large sets of equations is fundamental in science and engineering. The authors show that any sparse linear system with certain properties can be transformed into a 3D physical setup of materials where electromagnetic waves solve the system naturally. This means Maxwell’s equations, which govern light and electromagnetism, can represent and solve these problems efficiently. Their findings link electromagnetic simulations directly to sparse linear algebra computations.
What this means in practice
- •For computational physicists: Use electromagnetic simulation to solve large sparse linear systems within physical material designs.
- •For hardware architects: Design metamaterial or photonic circuits that implement sparse linear algebra problems via Maxwell’s equations.
A theory result. No direct application yet.
Authors
Yannick Augenstein
Abstract
Optical and wave-based analog computing has re-emerged as a route to accelerating linear algebra, with metamaterials and photonic circuits shown to invert matrices and solve integral equations. However, it has remained unclear which problems such passive structures can represent, and at what cost, once encoding, precision, conditioning and readout are accounted for. Here, we show that every polynomially conditioned sparse linear system can be compiled into a three-dimensional dielectric -- a cavity filled with lossless, isotropic material of bounded permittivity -- whose time-harmonic response encodes its solution. For $m$ nonzero coefficients, the volume of the structure and the cost of writing it down and reading out the answer scale as $\tilde O(m^{3/2})$, coefficients require only $O(\log m)$ bits, and every field that approximately satisfies Maxwell's equations decodes to an approximate solution. We prove the construction for the continuum equations and give a computer-assisted version for the Yee discretization underlying finite-difference solvers. Read in reverse, it implies that electromagnetic simulation is, up to this overhead, as hard as general sparse linear algebra: a sufficiently fast general-purpose Maxwell solver would yield a faster sparse linear solver.