OP-00194 Partially resolved

Positive diagonal preconditioning with a nilpotent stiff limit

Let $s \ge 2$ and $0 < c_1 < \dots < c_s \le 1$, and let $A \in \mathbb{R}^{s \times s}$, $A_{ij} = \int_0^{c_i} \ell_j(t)\,dt$, be the coefficient matrix of the collocation Runge–Kutta method with these nodes, where $\ell_1, \dots, \ell_s$ are the Lagrange basis polynomials of the nodes. For the test equation $y' = \lambda y$, step size $h$ and a diagonal matrix $D$ with positive entries, the diagonally preconditioned iteration for the collocation equations multiplies the error by $z(I_s - zD)^{-1}(A - D)$, where $z = h\lambda$; its limit as $|z| \to \infty$ is $I_s - D^{-1}A$. The condition below holds exactly when $\det((1 - t)D + tA) = \det D$ for every $t \in \mathbb{R}$. For $s = 2$ and nodes $a < b$, the entries $d_1 = a(2b - a)/(2(b - a) + \sqrt{2ab})$ and $d_2 = ab/(2d_1)$ satisfy it. For the Radau IIA nodes, Lioen computed such matrices $D$, all with positive entries, for $s \le 8$, numerically for $s \ge 3$. The determinant condition also underlies the diagonal MIN-SR-S preconditioner of Čaklović, Lunet, Götschel and Ruprecht for spectral deferred corrections, whose entries they compute numerically.

Problem. For every $s \ge 2$ and all nodes $0 < c_1 < \dots < c_s \le 1$, is there a real diagonal matrix $D = \operatorname{diag}(d_1, \dots, d_s)$ with $d_1, \dots, d_s > 0$, in any order, such that $$\rho(I_s - D^{-1}A) = 0,$$ that is, such that $I_s - D^{-1}A$ is nilpotent?

Source: van der Houwen and de Swart (1997), Section 3.2.1, for collocation-based Runge–Kutta correctors; for every node set 0 < c₁ < ⋯ < c_s ≤ 1, as stated by OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Keywords: collocation methods, diagonal preconditioners, OpenProblemsInNLA, Runge–Kutta methods
Literature checked: Oct. 8, 2026 by clemens-admin

References

@article{vanderhouwen1997,
  author  = {van der Houwen, P. J. and de Swart, J. J. B.},
  title   = {Triangularly implicit iteration methods for {ODE}-{IVP} solvers},
  journal = {SIAM J. Sci. Comput.},
  volume  = {18},
  number  = {1},
  year    = {1997},
  pages   = {41--55},
  doi     = {10.1137/S1064827595287456},
}
@article{lioen1996,
  author  = {Lioen, Walter M.},
  title   = {On the diagonal approximation of full matrices},
  journal = {J. Comput. Appl. Math.},
  volume  = {75},
  number  = {1},
  year    = {1996},
  pages   = {35--42},
  doi     = {10.1016/S0377-0427(96)00054-4},
}
@article{caklovic2025,
  author        = {{\v{C}}aklovi{\'c}, Gayatri and Lunet, Thibaut and G{\"o}tschel, Sebastian and Ruprecht, Daniel},
  title         = {Improving Efficiency of Parallel Across the Method Spectral Deferred Corrections},
  journal       = {SIAM J. Sci. Comput.},
  volume        = {47},
  number        = {1},
  year          = {2025},
  pages         = {A430--A453},
  doi           = {10.1137/24M1649800},
  eprint        = {2403.18641},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie28,
  author       = {Townsend, Alex},
  title        = {{IE-28}: Positive diagonal preconditioning with a nilpotent stiff limit},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-28/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

Extensions and Exact Certificates: all-stage local existence, an explicit node family, and a limitation of the eigenpolynomial construction v1 GitHub ↗

Sidney Holden

For the collocation integration matrix $A$ on distinct positive nodes, the target is one positive diagonal $D$ for which $I-D^{-1}A$ is nilpotent. We give a self-contained all-stage existence theorem for nodes sufficiently close to a common positive point. The proof regularizes a determinant at coincident nodes, constructs an algebraic confluent seed by a triangular recursion, and applies the implicit function …

Partial resolution · not verified · fidelity not established · posted on GitHub 13 Sep 2026

Status history

When	Change	By	Reason
2026-10-08	Open → Partially resolved	The registry's curators	Extensions and Exact Certificates: all-stage local existence, an explicit node family, and a limitation of the eigenpolynomial construction v1 recorded from OpenProblemsInNLA @ eb7c9d6, IE-28/report.pdf.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00194, "Positive diagonal preconditioning with a nilpotent stiff limit", clopen.solutions.