Maxwell's equations are universal for sparse linear algebra
In the authors' words
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 nonzero coefficients, the volume of the structure and the cost of writing it down and reading out the answer scale as , coefficients require only 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.
In plain words AI summary
The cavity's time-harmonic response encodes the solution to the system. For m nonzero coefficients, the volume and setup cost scale as O-tilde of m to the 3/2 power. Reversing this shows that fast electromagnetic simulation would mean faster sparse linear solving.
Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source. 2 sentences were removed for not being supported by the abstract.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 102 pages (16 pages main text, 86 pages Supplementary Information), 6 figures, 2 tables