Sturm sequences

Sturm sequences for two polynomials $f (x), g (x) \in \mathbbm{K}[x]$ are sequences of polynomials defined as follows

\[ R_0 = f, R_1 = g, R_2, \ldots \ldots, R_N \]

such that $R_i (x) = 0$ implies that for the first term such that$R_{i - k} (x) \neq 0$ and $R_{i + l} (x) \neq 0$, we have $R_{i - k} (x) R_{i + l} (x) < 0$, we. One can chose for instance

\begin{eqnarray*} R_{i + 1} = - \alpha_{i + 1} \tmop{rem} (R_{i - 1}, R_i) & & \end{eqnarray*}

where $\tmop{rem} (p, q)$ is the remainder in the Euclidean division of a polynomial $p$ by $q$, and $\alpha_i$ is a positive number.

The class computing the Sturm sequence

The corresponding class used to store the result is
template<class C, class UPOL=UPolDse<C>, class SEQ=std::vector<UPOL> > 
which is parameterised by

Several scheme of construction of such type of sequences are available:

Here is an example of construction of a Sturm Habicht sequence of two polynomials:
UPolDse<ZZ> p,q; SturmSeq<ZZ> s(p,q,HABICHT());

See also:

Sign variations

int variation(const SturmSeq<C,UPOL,S>& s, const R& x)



#include <synaps/arithm/gmp.h>
#include <synaps/upol.h>
#include <synaps/upol/SturmSeq.h>
typedef UPolDse<ZZ> upol_t;

int main(int argc, char** argv) 
  upol_t p("x^3-234234*x^2+32332334554*x-12221118723");
  SturmSeq<ZZ> s(p,diff(p),HABICHT());  
  //| [1*x^3-234234*x^2334554*x-12221118723,3*x^2-468468*x+334554,
  //|  109729126188*x+31626146871,-628213673160260696955282507]

  std::cout <<"Number of positive root(s): "
  //| Number of positive root: 1

  std::cout <<"Number of negative root(s): "
  //| Number of negative root: 0