SYNAPS (SYmbolic Numeric ApplicationS) » Univariate Polynomial

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> > 
   SturmSeq

which is parameterised by

C, the type of coefficients of the polynomials

UPOL, the type of univariate polynomials. The default value is UPolDse<C>.

SEQ, the type of the container used to store the sequence. The default value is std::vector<UPOL>.

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

EUCLIDEAN is the usual Sturm sequence where $\alpha_i = 1$ ,

HABICHT is the Sturm Habicht sequence, which compute sub-resultants.

Here is an example of construction of a Sturm Habicht sequence of two polynomials:

UPolDse<ZZ> p,q; SturmSeq<ZZ> s(p,q,HABICHT());

The euclidean construction requires coefficients coefficient in a field.

The Sturm-Habicht construction can be applied with coefficients in a ring (for instance integers, univariate polynomials,...)

See also:: synaps/upol/SturmSeq.h

Sign variations

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

This function computes the number of sign variation of the sequence s at the value x.

The number type used during this computation is R.

It is based on the function UPOLDAR::sign_at.

Example

#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());  
  std::cout<<s<<std::endl;
  //| [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): "
            <<variation(s,0)-variation(s,Infinity(1))<<std::endl;
  //| Number of positive root: 1

  std::cout <<"Number of negative root(s): "
            <<variation(s,Infinity(-1))-variation(s,0)<<std::endl;
  //| Number of negative root: 0
}

SYNAPS DOCUMENTATION