加入
Faster stiff ODE solve: Robertson's chemical kinetics
Integrate Robertson's stiff three-species reaction system to t = 9,999,999 faster than SciPy's Radau solver, at matching accuracy.
shoal 2周前提交
0 个父提交
提交 d25bcbbb45ba5443c211dfcb16d2f7459a5d3fe4
+44 −0 README.md 新增 查看文件
| @@ -0,0 +1,44 @@ | ||
| 1 | +# Faster stiff ODE solve: Robertson's chemical kinetics | |
| 2 | + | |
| 3 | +Integrate Robertson's three-species reaction system, a classic stiff test problem, out to a final time of about ten million, faster than SciPy's Radau solver and to the same accuracy. Stiff kinetics of this kind arise in combustion, atmospheric chemistry and systems biology. | |
| 4 | + | |
| 5 | +## Task | |
| 6 | + | |
| 7 | +Solve, for $t$ from 0 to $t_1$, | |
| 8 | + | |
| 9 | +$$\dot y_1=-k_1y_1+k_3y_2y_3,\qquad \dot y_2=k_1y_1-k_2y_2^2-k_3y_2y_3,\qquad \dot y_3=k_2y_2^2,$$ | |
| 10 | + | |
| 11 | +with $y(0)=(1,0,0)$ and $t_1=n=9{,}999{,}999$ in the benchmark. Each instance draws $k_1=0.04\,u_1$, $k_2=3\times10^{7}u_2$ and $k_3=10^{4}u_3$ with $u_1,u_2,u_3$ uniform on $[0.5,2]$, $[0.7,1.5]$ and $[0.8,1.3]$. Output: $y(t_1)$. An output is accepted when it is finite, every component is at least $-10^{-10}$, $\lvert y_1+y_2+y_3-1\rvert\le5\times10^{-6}$, and it agrees with two reference solutions from `scipy.integrate.solve_ivp`, Radau (rtol $10^{-11}$, atol $10^{-9}$) and BDF (rtol $5\times10^{-10}$, atol $10^{-9}$), to relative tolerance $3\times10^{-6}$ and absolute tolerance $3\times10^{-9}$ (loosened to $10^{-5}$ and $10^{-8}$ if the two references disagree). The reference solver is the Radau run. | |
| 12 | + | |
| 13 | +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. | |
| 14 | + | |
| 15 | +## Background | |
| 16 | + | |
| 17 | +Robertson's 1966 model of an autocatalytic reaction has rate constants that differ by about nine orders of magnitude, so explicit methods need extremely small steps and implicit methods are required; it is a standard test in the literature on stiff solvers (Hairer and Wanner, 1996). The very long horizon, out to $10^7$, probes how well a solver grows its step size once the fast transients have died out. | |
| 18 | + | |
| 19 | +## Data and evaluation | |
| 20 | + | |
| 21 | +- **Instances:** 100 test and 100 development instances from the task's generator at $n=9{,}999{,}999$ (that is, $t_1=9{,}999{,}999$), in the [AlgoTune dataset](https://huggingface.co/datasets/oripress/AlgoTune); the reference needs about 90 ms per instance on the authors' machine. | |
| 22 | +- **Evaluation code:** the AlgoTune harness (`./algotune.sh evaluate` in the [repository](https://github.com/oripress/AlgoTune)), which runs the task's checker on every output. | |
| 23 | +- **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. | |
| 24 | + | |
| 25 | +## What is known | |
| 26 | + | |
| 27 | +- Best on the [AlgoTune leaderboard](https://algotune.io) as of 2026-10-20: 100.81×, by the AlgoTuner agent driven by Claude Opus 4.5, ahead of Claude Opus 4.6 (76.85×) and DeepSeek R1 (68.88×). | |
| 28 | +- The task's checker was tightened on 2026-02-08, adding the second (BDF) reference and the sign and mass-conservation tests. The top run was added to the results on 2026-02-02, before that change, and has not been shown to pass the current checker. | |
| 29 | +- 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. | |
| 30 | + | |
| 31 | +## What would count as progress | |
| 32 | + | |
| 33 | +- A solver beating 100.81× that passes the current, tightened checker on all 100 test instances, with its code; anyone can rerun the checker and the timing. | |
| 34 | +- An error study comparing the solver's $y(t_1)$ with a high-precision reference, showing it is accurate rather than merely close to SciPy's answer. | |
| 35 | + | |
| 36 | +## References | |
| 37 | + | |
| 38 | +1. O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. [arXiv:2507.15887](https://arxiv.org/abs/2507.15887) | |
| 39 | +2. E. Hairer, G. Wanner. Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd edition. Springer (1996). [doi:10.1007/978-3-642-05221-7](https://doi.org/10.1007/978-3-642-05221-7) | |
| 40 | +3. P. Virtanen et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17, 261–272 (2020). [doi:10.1038/s41592-019-0686-2](https://doi.org/10.1038/s41592-019-0686-2) | |
| 41 | + | |
| 42 | +## Source | |
| 43 | + | |
| 44 | +Imported from [AlgoTune task ode_stiff_robertson](https://github.com/oripress/AlgoTune/tree/main/AlgoTuneTasks/ode_stiff_robertson), 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. | |