Faster thin singular value decomposition

Compute the thin singular value decomposition of a dense rectangular matrix faster than NumPy, keeping orthonormal factors that reconstruct the matrix. The SVD underlies least squares, low-rank approximation and principal component analysis.

Task

Input: a matrix $A\in\mathbb{R}^{r\times c}$ whose sizes $r$ and $c$ are drawn uniformly from the integers in $[n,2n]$ and whose entries are independent standard normal; in the benchmark $n=474$. Output: $U\in\mathbb{R}^{r\times k}$, $S\in\mathbb{R}^{k}$ and $V\in\mathbb{R}^{c\times k}$ with $k=\min(r,c)$ and

$$A=U\,\mathrm{diag}(S)\,V^\top.$$

An output is accepted when the shapes are right, every entry is finite, $S\ge0$, both $U^\top U$ and $V^\top V$ match the identity, and $U\,\mathrm{diag}(S)\,V^\top$ matches $A$, the last three under NumPy's allclose with absolute tolerance $10^{-6}$. The singular values need not be sorted. The reference solver is numpy.linalg.svd(A, full_matrices=False).

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

Dense SVD solvers reduce the matrix to bidiagonal form, as introduced by Golub and Kahan (1965), and then diagonalize the bidiagonal matrix; LAPACK provides several drivers for this (Anderson et al., 1999). The checker asks only for an exact-enough factorization, not for any particular algorithm, so routes through eigendecompositions, QR or iterative refinement are all allowed if they meet the tolerances.

Data and evaluation

• Instances: 100 test and 100 development instances from the task's generator at $n=474$, in the AlgoTune dataset; the reference needs about 118 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: 1.62×, by the AlgoTuner agent driven by o4-mini, ahead of GPT-5 Mini (1.61×) and GPT-5.2 (1.16×).
• 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 1.62× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
• A numerical-stability note for the best solver, for example its orthogonality error compared with LAPACK's on ill-conditioned matrices.

References

1. O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. arXiv:2507.15887
2. G. Golub, W. Kahan. Calculating the singular values and pseudo-inverse of a matrix. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis 2, 205–224 (1965). doi:10.1137/0702016
3. E. Anderson et al. LAPACK Users' Guide, 3rd edition. SIAM (1999). doi:10.1137/1.9780898719604

Source

Imported from AlgoTune task svd, 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.