Sturm Sequences
Implement exact real root counting via Sturm chains and compare with Descartes' rule.
- Suitable for
- Undergraduate research
Master's thesis - Supervision
- Zafeirakis Zafeirakopoulos
Sturm’s theorem (1835) gives a procedure to count the exact number of distinct real roots of a polynomial \(f \in \mathbb{R}[x]\) in any interval \([a,b]\), using only arithmetic on the coefficients — no numerical approximation needed.
The Sturm chain
Given \(f\) with no repeated roots, construct the sequence:
\[f_0 = f,\quad f_1 = f',\quad f_{i+1} = -\,\text{rem}(f_{i-1}, f_i)\]where \(\text{rem}\) is the polynomial remainder. The chain terminates when a constant is reached.
Sturm’s theorem: The number of distinct real roots of \(f\) in \((a, b]\) equals
\[\sigma(a) - \sigma(b)\]where \(\sigma(c)\) is the number of sign changes in the sequence \(f_0(c), f_1(c), \ldots\) (zeros are ignored).
Comparison with Descartes’ rule
Descartes’ rule counts sign changes in the coefficient sequence to bound the number of positive roots, but gives an upper bound, not an exact count. Sturm gives an exact count but requires computing the full remainder sequence, which can be expensive for large-degree polynomials due to coefficient growth.
The practical comparison:
| Method | Output | Cost | Coefficient growth |
|---|---|---|---|
| Descartes | upper bound | \(O(n)\) | none |
| Sturm (naïve) | exact count | \(O(n^2)\) | exponential |
| Sturm (subresultant) | exact count | \(O(n^2)\) | polynomial |
Using subresultant pseudo-remainder sequences controls the coefficient growth and makes Sturm practical.
Goal
Implement Sturm’s theorem using subresultant remainders, verify on a suite of polynomials, and produce a head-to-head comparison with the Descartes/Collins–Akritas isolator on running time and output quality.
Milestones
| ID | Title |
|---|---|
| M1 | Implement naïve Sturm chain |
| M2 | Subresultant version |
| M3 | Comparison suite vs. Descartes |
| M4 | Final report |
Tasks
| ID | Title | Status |
|---|---|---|
| T1 | Naive Sturm chain + root count | todo |
| T2 | Subresultant remainder sequence | todo |
| T3 | Descartes isolator for comparison | todo |
| T4 | Benchmark suite + write-up | todo |
Deliverables
- Julia implementation with tests
- Benchmark comparing Sturm and Descartes on random and structured inputs
- Short report (4–6 pages)
References
-
G. E. Collins and A. G. Akritas. Polynomial real root isolation using Descartes’ rule of signs. SYMSAC 1976, pp. 272–275, ACM. DOI 10.1145/800205.806346
-
M. Sagraloff and K. Mehlhorn. Computing real roots of real polynomials. Journal of Symbolic Computation, 73:46–86, 2016. DOI 10.1016/j.jsc.2015.03.004 · arXiv:1308.4088