# 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](https://huggingface.co/datasets/oripress/AlgoTune); the reference needs about 118 ms per instance on the authors' machine.
- **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.
- **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](https://algotune.io) 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](https://arxiv.org/abs/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](https://doi.org/10.1137/0702016)
3. E. Anderson et al. LAPACK Users' Guide, 3rd edition. SIAM (1999). [doi:10.1137/1.9780898719604](https://doi.org/10.1137/1.9780898719604)

## Source

Imported from [AlgoTune task svd](https://github.com/oripress/AlgoTune/tree/main/AlgoTuneTasks/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.