Selected bidiagonal singular directions with fixed-format linear output work
Recorded by the registry's curators from GitHub; the authors did not submit it here.
Kaiwen Jin
Computing a few singular vectors of a bidiagonal matrix requires control of orthogonality as well as residuals when singular values cluster. We give a rational-filter construction for any requested set of $k$ ordered singular triplets of a real $n\times n$ upper bidiagonal matrix. For $\epsilon=2^{-p}$, $16\le p\le53$ and $n\epsilon\le1/64$, its represented unit directions satisfy both singular-vector residual bounds, ordered-value accuracy and separate left and right orthogonality bounds with a universal constant, independent of the input gaps. The work is $O(p^4nk)$ operations on $O(p)$-bit numbers, or conservatively $O(p^6nk)$ bit operations. Thus the work is linear in $nk$ after the format is fixed. The sufficient core precision is 220224 bits for a binary64 target; practical speed superiority is not claimed. Count-separated spectral intervals, positive rational filters and joint Schur-complement columns avoid a final vector reorthogonalization. A common cut near zero permits recovery of left directions without a small-singular-value assumption. The arithmetic model and the distinction between floating carriers and exact unit directions are explicit. A research implementation supplies separate proof and diagnostic configurations with optional exact checks of finite outputs.
Claims
Files and sources
- Paper
- AIM @ 24edaad, paper/main.pdf ↗
- Posted on GitHub
- 15 October 2026
No verification run is on record for this version.