Sturm Subdivision Solver

Another criterion to detect the number of roots in an interval, can be used. It is based on Sturm's theorem. Here is the simplifed version, that we exploit:

Theorem: Let $f \in \mathbbm{R}[x]$ and $S (x) = [f (x), f' (x), S_2 (x), \ldots, S_N (x)]$ be the Sturm sequence of $f$ and $f'$(x). Let $V (a)$ be the number of sign variation of $S (a)$ for $a \in \mathbbm{R}$. Then, for any $a, b \in \mathbbm{R}$, $V (a) - V (b)$ is the number of roots in ]a,b[.

This leads to the following schema of algorithms, (which applies event to polynomials with multiple roots):

Algorithm: Isolation of the roots of $f$ on the interval $[a, b]$.

INPUT: A polynomial $f \in \mathbbm{R}[x]$.

  • Compute the Sturm sequence $S (x)$ of $f$ and $f'$.
  • Compute the number of sign changes $r = V (a) - V (b)$.
  • If $r = 0$ remove the interval.
  • If $r > 1$ and compute $V ( \frac{a + b}{2})$ and apply recursively the algorithm to the two halves of the input interval.
OUTPUT: a list of subintervals of $[a, b]$ containing exactly one real root of $f$.

Sturm Approximation Solver

Seq<O> solve(const UPOL& p, SlvSturm<O,C> mth);

Sturm Isolation Solver

Seq< Interval<O> > solve(const UPOL& p, IslSturm<O,C> mth);



#include <synaps/upol.h>
#include <synaps/arithm/QQ.h>
#include <synaps/usolve/sturm/IslSturm.h>
int main()
  using std::cout;  using std::endl;

  UPolDse<QQ> P("2*x^7+3*x^6+2*x^5+x^4-x^3-2*x^2-3*x+1");
  cout <<"Testing: "<<P<<endl;
  //| Testing: 2*x^7+3*x^6+2*x^5+1*x^4-1*x^3-2*x^2-3*x+1

  cout <<solve(P,IslSturm<QQ>())<<endl;
  //| [ -5/2,0 ], [ 0,5/8 ], [ 5/8,5/4 ]

  cout <<solve(P,IslSturm<QQ>(),0,1)<<endl;
  //| [ 0,1/2 ], [ 1/2,1 ]