加入
Faster method-of-lines solve of Burgers' equation
Advance a shock-forming viscous Burgers' equation on a 240-point grid to t = 5 faster than SciPy's RK45 integrator, matching its answer.
shoal 2周前提交
0 个父提交
提交 05e9f391a3743f4d8ff530edd4f1dbcf3f5f2f6e
+44 −0 README.md 新增 查看文件
| @@ -0,0 +1,44 @@ | ||
| 1 | +# Faster method-of-lines solve of Burgers' equation | |
| 2 | + | |
| 3 | +Advance a shock-forming solution of the viscous Burgers' equation on a 240-point grid faster than SciPy's RK45 integrator, while matching its answer. Burgers' equation is the simplest model that combines nonlinear advection with diffusion and a standard test for numerical schemes. | |
| 4 | + | |
| 5 | +## Task | |
| 6 | + | |
| 7 | +The equation is $u_t+u\,u_x=\nu\,u_{xx}$ on $[-1,1]$ with $\nu=0.005$, $u=0$ at both ends, and $t$ from 0 to 5. It is discretized on $N=20n$ interior points ($N=240$ in the benchmark, $n=12$) with spacing $\Delta x=2/(N+1)$: | |
| 8 | + | |
| 9 | +$$\frac{du_i}{dt}=-u_i\,D_iu+\nu\,\frac{u_{i+1}-2u_i+u_{i-1}}{\Delta x^2},$$ | |
| 10 | + | |
| 11 | +where $D_iu=(u_i-u_{i-1})/\Delta x$ if $u_i\ge0$ and $(u_{i+1}-u_i)/\Delta x$ otherwise (upwinding). The initial condition is one of three shapes chosen at random, $0.5\sin(\pi x)$, a Gaussian bump, or a pair of opposite-signed bumps, plus uniform noise of amplitude 0.05. Output: $u_i$ at $t=5$. An output is accepted when it is finite and matches the reference under NumPy's `allclose` with relative tolerance $10^{-5}$ and absolute tolerance $10^{-8}$. The reference solver is `scipy.integrate.solve_ivp` with RK45, rtol and atol $10^{-6}$. | |
| 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 | +Burgers (1948) introduced the equation as a mathematical model illustrating the theory of turbulence; at low viscosity its solutions steepen into thin shock layers, which makes it a classic test for numerical methods. Here the spatial scheme is fixed, so the task is purely about integrating the resulting system of ordinary differential equations quickly. Note that the checker compares with RK45's own answer, not with the exact solution of the equation, and that the task's text says $t_1=0.5$ while the generator and the published instances use $t_1=5$. | |
| 18 | + | |
| 19 | +## Data and evaluation | |
| 20 | + | |
| 21 | +- **Instances:** 100 test and 100 development instances from the task's generator at $n=12$ (240 grid points), in the [AlgoTune dataset](https://huggingface.co/datasets/oripress/AlgoTune); the reference needs about 117 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: 125.44×, by the AlgoTuner agent driven by Gemini 3.1 Pro Preview, ahead of GPT-5.4 (5.81×) and GPT-5.2 (5.29×). | |
| 28 | +- The best result is more than twenty times the second best, so one run found something the others did not; its full trajectory, with code, is published on the leaderboard site. | |
| 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 125.44× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing. | |
| 34 | +- An independent explanation of where the large speed-ups come from, for example step-size control versus per-step cost, backed by timings. | |
| 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. J. M. Burgers. A mathematical model illustrating the theory of turbulence. Advances in Applied Mechanics 1, 171–199 (1948). [doi:10.1016/S0065-2156(08)70100-5](https://doi.org/10.1016/S0065-2156(08)70100-5) | |
| 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 pde_burgers1d](https://github.com/oripress/AlgoTune/tree/main/AlgoTuneTasks/pde_burgers1d), 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. | |