Superlinear growth conjecture for complete pivoting

About 3 years old · traced to

For each positive integer nn, let g[CPn(R)]g\big[\mathbf{CP}_n(\mathbb{R})\big] denote the maximum growth factor for complete pivoting over real n×nn\times n matrices. Recall that f(n)=ω(h(n))f(n)=\omega(h(n)) means

lim⁡n→∞f(n)h(n)=∞.\lim_{n\rightarrow\infty}\frac{f(n)}{h(n)}=\infty.

Superlinear growth conjecture. The maximum growth factor is superlinear:

g[CPn(R)]=ω(n).g\big[\mathbf{CP}_n(\mathbb{R})\big]=\omega(n).

The conjecture is motivated by numerical evidence for matrix sizes up to 7575 and 100100; the paper also reports a lower bound on the limiting superior ratio, but an exact asymptotic estimate remains elusive.

References

Primary source

Alan Edelman and John Urschel, “Some New Results on the Maximum Growth Factor in Gaussian Elimination”, arXiv:2303.04892 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.