CS Paper Radar

Maxwell's equations are universal for sparse linear algebra

Yannick Augenstein

cs.CC physics.optics ·submitted 2026-10-28 21:05 UTC · v2
theorycode/dataunusual

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.

Comment
109 pages (18 pages main text, 91 pages Supplementary Information), 8 figures, 4 tables. v2: adds numerical illustrations (Fig. 3, SI Part VI), Lean verification records, and corrected continuum degree bounds. Code, data and Lean proofs: https://github.com/yaugenst/maxwell-universality

Closest papers

Nearest neighbours by meaning across the whole index.

Finite-Element Electromagnetic Analysis and Evaluation of Antenna Performance Metrics Using a Quantum Linear System Solver

cs.CE quant-ph ·2026-10-28 ·Hiroaki Ominato, Takahiro Ohyama, Shiro Kawabata
similarity 0.57
Abstract · 10 pages, 5 figures

Electromagnetic analysis based on the finite element method is widely used in antenna design. At higher frequencies, however, the required mesh refinement makes solving large sparse linear systems the main contributor to computational cost. Quantum linear system solvers offer a potential means of accelerating this step, but their output is a superposition state: reconstructing all components of the classical solution vector would forfeit the quantum speedup. Prior studies have proposed methods for obtaining physical quantities such as scattering cross sections and scattering parameters from the solution state. To support antenna design using fault-tolerant quantum computers, we formulate the total radiated power, the radiated power within a prescribed solid angle, and the dielectric and conductive losses as observables for efficient evaluation from a quantum solution state. These observables avoid the measurement cost of reconstructing all components of the output quantum state. We develop an end-to-end hybrid quantum--classical workflow that combines finite-element electromagnetic analysis, matrix preconditioning, a quantum linear system solver, and the evaluation of antenna design metrics. To validate the workflow, we performed numerical experiments evaluating these observables for an axisymmetric coaxially fed monopole antenna. Under idealized conditions, the relative errors in the total radiated power and the dissipated power with respect to the classical finite-element solution were on the order of $10^{-3}$, confirming the consistency of the workflow. The proposed method is expected to provide a basis for using quantum linear system solvers to evaluate antenna performance and, in the future, to design high-frequency wireless devices.

0.29

Electromagnetic Information Theory for Programmable Metasurfaces

eess.SP physics.optics ·2026-11-02 ·Philipp del Hougne, Marco Di Renzo, Owen D. Miller, David A. B. Miller
position similarity 0.55
Abstract · 17 pages with 3 figures

Programmable metasurfaces enable fine-grained control of electromagnetic waves and are creating new opportunities for information extraction, information transfer and information processing. Yet, despite exciting experimental demonstrations, their fundamental capabilities remain poorly understood. In this Perspective, we argue that programmable metasurfaces, and programmable wave systems more generally, call for an electromagnetic information theory that addresses limits at two levels, in a unified manner across applications like communications, sensing and computing. First, for a given physical platform, such a theory should bound achievable information manipulations, such as sensing precision, information-transfer rates, and computational performance. Second, at a more fundamental level, it should determine what non-programmable and programmable physical resources bound these system-specific limits, and what minimum resources are required to attain a prescribed level of performance. We discuss emerging theoretical approaches to these questions, and their connection to experimentally realizable systems. We examine how device thickness, programmable degrees of freedom, nonlocality, coupling and multiple scattering constrain these limits. Establishing the envisioned framework could clarify the ultimate capabilities of programmable metasurfaces and guide the design of future wave-based information systems.

0.27

A Hierarchically Compressed Immittance Operator Formulation for Fast Statics-to-Full-Wave Electromagnetic Simulation with the Boundary Element Method

cs.CE physics.comp-ph ·2026-11-16 ·Shashwat Sharma
similarity 0.54
Abstract · 15 pages, 12 figures. Submitted to the IEEE Transactions on Antennas and Propagation

The boundary element method allows the electromagnetic simulation of three-dimensional problems with a two-dimensional discretization, using a surface integral representation of Maxwell's equations. For applications involving broadband simulations or multiscale geometries, the well-known low-frequency breakdown of conventional integral equation formulations must be addressed, while ensuring that dielectric, semiconducting, and lossy metallic regions are modeled rigorously, including the skin effect. In this work, a new boundary element formulation based on an immittance operator is proposed, where the underlying integral equations are inherently valid from statics to the full-wave regime. To enable efficient matrix assembly and solution, a hierarchical matrix compression strategy is devised, leveraging fast direct factorization as an intermediate step, and fast matrix-vector products for the iterative solution of the final system of equations. The proposed formulation is capable of electrostatic, magnetostatic, quasistatic, and full-wave simulations of dielectrics, semiconductors, and lossy metals. Representative numerical examples drawn from a variety of applications demonstrate the accuracy and efficiency of the proposed method.

0.41

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

cs.DS cs.CCmath.NA ·2026-09-29 ·Jonathan A. Kelner
similarity 0.50
Abstract

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.

0.09

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

cs.DS ·2026-11-06 ·Marco Pirazzini, Daniel A. Spielman
similarity 0.49
Abstract · 31 pages, 6 figures

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)$ (Objois and Vladu, 2026), which is slower when high accuracy solutions are desired. Our algorithm employs a surprising application of Laplacian solvers inside an Interior Point Method (IPM). We formulate the problem as a linear optimization problem over a product of power cones, and show that the Newton updates of the IPM can be computed by solving a Laplacian system in a Schur complement after subtracting a rank-2 matrix. We also discuss an implementation of our algorithm, showing that it is practical and it outperforms optimized solvers such as MOSEK by factors of up to $20\times$ on a variety of tasks.

0.31

Diffusion-Based Inverse Design of Dielectric Resonator Metasurfaces for Shaping Smart Electromagnetic Environments

cs.LG physics.app-phphysics.comp-ph ·2026-08-30 ·M. Tsukerman, K. Grotov, D. Vovchuk, P. Ginzburg
similarity 0.49
Abstract

Future wireless systems are expected to transform the surrounding space from a passive propagation medium into a smart electromagnetic environment, where engineered surfaces control wave propagation, support wireless sensing, and create programmable electromagnetic fingerprints. A key challenge in realizing this vision is the inverse design of metasurfaces for tailored electromagnetic propagation. While forward analysis evaluates the response of a known geometry, the inverse task starts from a prescribed scattering signature and seeks a physically realizable structure that produces it. This inverse task is inherently nonlinear and often high-dimensional, while candidate solutions may be non-unique and provide no direct indication of practical realizability. Here, we introduce a conditional diffusion framework for inverse design of dielectric resonator metasurfaces from target angular scattering patterns. Trained on T-matrix simulated geometry-response pairs, the model learns a conditional distribution of geometries instead of a deterministic mapping, enabling multiple candidate designs for the ill-posed inverse problem. The best generated metasurface achieves a mean percentage error of 1.39%, outperforming CMA-ES optimization (4.1% after 10 h) while requiring only about one minute for after-training inference. The model also produces lower error distributions than deterministic neural baselines for out-of-distribution spectra, highlighting the potential of diffusion models for efficient metasurface design.

0.28

Energy Efficiency in Microwave Linear Analog Computer (MiLAC)-Enabled Communications

eess.SP ·2026-08-31 ·Ahmed Magbool, Marco Di Renzo
similarity 0.49
Abstract · Submitted to the IEEE for possible publication

Microwave linear analog computers (MiLACs) have emerged as a promising architecture for energy-efficient wireless communications by shifting signal processing from the digital to the analog domain using tunable impedance networks. Several MiLAC architectures have recently been proposed, including the single-layer MiLAC (SLM), two-layer MiLAC (TLM), and hybrid digital-MiLAC (HDM). In this paper, we investigate the energy efficiency (EE) of these architectures. Specifically, we formulate EE maximization problems for the SLM, TLM, and HDM architectures under transmit power, user rate, and architecture-specific constraints, and develop a dimensionality reduction technique with successive convex approximation (SCA)-based algorithms to efficiently solve the resulting non-convex problems. We further derive a computationally efficient solution for EE maximization based on a search over only $(K+1)$ closed-form candidate solutions, where $K$ is the number of users, and analyze the asymptotic EE in the large-antenna regime under negligible quantization noise. Our analysis shows that the EE of the SLM, TLM, and HDM architectures scales as $\ln(N)/N^2$, whereas conventional digital beamforming (DBF) scales as $\ln(N)/N$, where $N$ denotes the number of transmit antennas. Despite these different scaling laws, the faster EE decay of MiLAC-based architectures becomes relevant only at very large antenna dimensions, typically involving thousands of antennas, while they maintain superior EE over practically relevant finite antenna regimes. Finally, we derive an approximation of the number of antennas required to achieve the maximum EE for each architecture and the corresponding EE. Simulation results show that, over practically relevant antenna regimes, MiLAC-based architectures achieve substantially higher EE than conventional fully digital and hybrid analog-digital beamforming.

0.42

Bounds on Shaping Partially Coherent Microwaves with Programmable Scattering Systems

eess.SP physics.app-ph ·2026-08-31 ·Philipp del Hougne
similarity 0.49
Abstract · 15 pages with 3 figures

We derive bounds on manipulating partially coherent microwaves with programmable scattering systems. We first consider the concentration of power from a partially coherent input into a single output port and derive a prototype-aware bound by combining multiport network theory (MNT) with semidefinite relaxation (SDR). We then address general coherency-matrix synthesis, deriving architecture-independent bounds on fidelity and useful strength, prototype-specific scalar refinements thereof, and fully prototype-aware SDR bounds on the useful-strength--fidelity Pareto frontier. The prototype-aware formulations account for mutual coupling, loss, discrete tunability, and static scattering. We evaluate the bounds on four experimental RIS-parametrized MIMO systems with up to 100 1-bit-programmable elements, using proxy-MNT models estimated from measurements. The resulting bounds are generally tight compared with feasible discrete-optimization outcomes. Interestingly, for coherency synthesis, the simpler bounds can in some cases be tighter than the fully prototype-aware bounds, highlighting their complementarity. Our results provide certified limits for wave-domain processing and harvesting of partially coherent microwaves.

0.48