Faster matrix exponential

Compute the exponential $e^{A}$ of a dense random matrix faster than SciPy's expm, to five significant digits. The matrix exponential solves linear systems of differential equations and appears in control theory, Markov chains and quantum dynamics.

Task

Input: $A\in\mathbb{R}^{n\times n}$ with independent standard normal entries; in the benchmark $n=555$ . Output:

e^{A}=\sum_{k=0}^{\infty}\frac{A^k}{k!}.

An output is accepted when it matches scipy.linalg.expm(A) entrywise under NumPy's allclose with relative tolerance $10^{-5}$ and absolute tolerance $10^{-8}$ . The reference solver is scipy.linalg.expm, which implements the scaling-and-squaring algorithm with Padé approximants of Al-Mohy and Higham (2009).

Score: the reference's run time divided by the candidate's, averaged over the test instances; it is 1 if any output fails the check, and speed-ups below 1 count as 1. Higher is better.

Background

Moler and Van Loan's classic survey, "Nineteen dubious ways to compute the exponential of a matrix", was updated in 2003; SciPy uses scaling and squaring with Padé approximants, as refined by Al-Mohy and Higham (2009), who choose the scaling and the Padé degree from the data. Its cost is a handful of matrix products, a linear solve and the squarings, so speed-ups must come from fewer products, cheaper ones, or a different method that still meets the tolerance.

Data and evaluation

Instances: 100 test and 100 development instances from the task's generator at $n=555$ , in the AlgoTune dataset; the reference needs about 107 ms per instance on the authors' machine.
Evaluation code: the AlgoTune harness (./algotune.sh evaluate in the repository), which runs the task's checker on every output.
Hardware: speed-ups depend on the machine, so reference and candidate are timed in the same environment. The paper keeps the fastest of 10 timed runs per instance, each after a warm-up, on an AMD EPYC 9454 CPU with 14 GB of memory; agents had 8 cores, and compilation is not timed.

What is known

Best on the AlgoTune leaderboard as of 2026-10-20: 2.13×, by the AlgoTuner agent driven by Gemini 3.1 Pro Preview, ahead of Gemini 3 Pro Preview (2.12×) and Claude Opus 4.5 (1.01×).
Only two models' runs exceed 1.1×; the next best is 1.01×.
Press et al. (2025) describe most agent speed-ups as surface-level: better library calls, better library usage or low-level rewrites, for example with Numba.

What would count as progress

A solver beating 2.13× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
An error analysis showing that the faster method stays within the tolerance for matrices with larger norms than the test inputs.

References

O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. arXiv:2507.15887
A. H. Al-Mohy, N. J. Higham. A new scaling and squaring algorithm for the matrix exponential. SIAM Journal on Matrix Analysis and Applications 31, 970–989 (2009). doi:10.1137/09074721X
C. Moler, C. Van Loan. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review 45, 3–49 (2003). doi:10.1137/S00361445024180

Source

Imported from AlgoTune task matrix_exponential, curated by Ori Press and the AlgoTune contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.