Sharpness conjecture for Orthomin(k) on root-of-unity diagonal systems

About 15 years old · traced to

Let k∈Nk\in\mathbb{N}. For each d∈Nd\in\mathbb{N}, let U=diag⁡(1,ζd,ζd2,…,ζdd−1)U=\operatorname{diag}(1,\zeta_d,\zeta_d^2,\dots,\zeta_d^{d-1}), where ζd=exp⁡(2πi/d)\zeta_d=\exp(2\pi \mathbf{i}/d) is a primitive root of unity of order dd. For 0<ρ<10<\rho<1, consider the linear system from the source with matrix UU and initial value x0=0x_0=0, and let rn(k)r_n^{(k)} denote the residuals produced by Orthomin(k)(k). Sharpness conjecture. For every k∈Nk\in\mathbb{N}, there exist dk∈Nd_k\in\mathbb{N} and 0<ρk<10<\rho_k<1 such that, for every ρ∈(0,ρk)\rho\in(0,\rho_k) and every d≥dkd\ge d_k,

lim⁡n→∞∥rn+1(k)∥∥rn(k)∥=ρ.\lim_{n\to\infty}\frac{\lVert r_{n+1}^{(k)}\rVert}{\lVert r_n^{(k)}\rVert}=\rho.

The result is proved in the paper for k=1k=1, while for k≥2k\geq 2 the authors report strong numerical evidence. If true, it shows that Orthomin(k)(k) need not converge asymptotically faster than Orthomin(1)(1) in general.

References

Primary source

Andrei Draganescu and Florin Spinu, “Sharp estimates for the convergence rate of Orthomin(k) for a class of linear systems”, arXiv:1109.2669 (2025).

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.