Sharp partial-pivoting growth for unequal bandwidths
Recorded by the registry's curators from GitHub; the authors did not submit it here.
Matthew J. Colbrook
For lower bandwidth $p \ge 1$ and upper bandwidth $q \ge 0$, the manuscript
proves that the optimal dimension-independent growth factor of Gaussian
elimination with partial pivoting is $h_{p+q}$, where $h_t = 0$ for $t \le 0$ and
$h_t = 1 + \sum_{r=1}^{p} h_{t-r}$ for $t \ge 1$; for $p = 0$ it is $1$. A
sorted-front argument gives an upper bound, and an explicit nonsingular real
band matrix of order $2p + q + 1$ attains it. The proof covers fixed column
order, real and complex matrices, and arbitrary permitted pivot ties, with
growth measured over all active Schur-complement entries. The recurrence gives
$G(p, 0) = 2^{p-1}$, $G(1, q) = q + 1$ and, for equal bandwidths,
$2^{2p-1} - (p-1) 2^{p-2}$.
Claims
Files and sources
- Paper
- OpenProblemsInNLA @ eb7c9d6, manuscripts/IE-13.pdf ↗
- Posted on GitHub
- 11 September 2026
No verification run is on record for this version.