SLV is a project aiming to create a library in Maple based on operations with Real Algebraic Numbers.

It currently provides solutions in Isolating Interval Representation, for univariate polynomials or well constrained systems of bivariate polynomials. In every case we assume the polynomials have integer coefficients. The solvers are based on Sturm Sequences to compute all real solutions.

GRUR is based on Modular GCD, Computer Algebra Group @ SFU.

The library is based on On the complexity of real solving bivariate systems, ISSAC 2007.

Our work also appeared on On the asymptotic and practical complexity of solving bivariate systems over the reals, JSC 2008.

An extended version of the above papers is available here.

The authors can be found in the following pages:

Usage Terms

Users are free to copy and use this code but proper acknowledgment to its authors should be given. Please send any comments to any of the 3 authors. Contact information is available in their respective homepages.

Source Code

Source code can be obtained here. [ UPDATED: Jul 2, 2007 ]

Sample Usage

Our library requires a definition for variable

`/opt/AlgebraicLibs/SLV/`

.Univariate Solving

The following is an example for univariate solving:

`> LIBPATH := "/opt/AlgebraicLibs/SLV/":`

> read cat ( LIBPATH, "system.mpl" ):

> f := 3*x^3 - x^2 - 6*x + 2:

> sols := SLV:-solveUnivariate( f ):

> SLV:-display_1 ( sols );

< x^2-2, [ -93/64, -45/32], -1.414213568 >

< 3*x-1, [ 1/3, 1/3], 1/3 >

< x^2-2, [ 45/32, 93/64], 1.414213568 >

Note, that the multiplicities of the roots do not appear, although they have been computed. Instead, the third argument of each component in the printed list is an approximation of the root. However, whenever possible we provide rational representation of the root.

Bivariate Solving

The following is an example for bivariate solving, where the second root lies in Z

`> LIBPATH := "/opt/AlgebraicLibs/SLV/":`

> read cat ( LIBPATH, "system.mpl" ):

> f := 1+2*x+x^2*y-5*x*y+x^2:

> g := 2*x+y-3:

> bivsols := SLV:-solveGRID ( f, g ):

> SLV:-display_2 ( bivsols );

< 2*x^2-12*x+1, [ 3, 7], 5.915475965 > , < x^2+6*x-25, [ -2263/256, -35/4], -8.830718995 >

< x-1, [ 1, 1], 1 > , < x-1, [ 1, 1], 1 >

< 2*x^2-12*x+1, [ 3/64, 3/32], .8452400565e-1 > , < x^2+6*x-25, [ 23179/8192, 2899/1024], 2.830943108 >

Again, just like in the case of univariate solving, the third argument that is printed on the component that describes each algebraic number is an approximation of the number and not the multiplicity of the root. Similarly, one could have used one of the other solvers on the above example by referring to their names, i.e. call the solvers with one of the following commands:

`> bivsols := SLV:-solveMRUR ( f, g ):`

> bivsols := SLV:-solveGRUR ( f, g ):

Floating-Point Output

For those interested in the numerical values or rough approximations of the solutions one can get the appropriate output via

`display_float_1`

and `display_float_2 `

procedures. Hence, for the above examples we have:`> SLV:-display_float_1 ( sols );`

< -1.4142136 >

< 0.3333333 >

< 1.4142136 >

> SLV:-display_float_2 ( bivsols );

[ 5.9154759, -8.8309519, ]

[ 1.0000000, 1.0000000, ]

[ 0.0845241, 2.8309519, ]

Consider the list

`sols`

of Rthe usage of the

`signAt`

function provided by our Filtered Kernel (Located in file: FK.mpl):`> FK:-signAt( 2*x + 3, sols[1] );`

1

> FK:-signAt( x^2*y + 2, sols[3], sols[1] );

-1

Polynomial Remainder Sequences

Our class on Polynomial Remainder Sequences (Located in file: PRS.mpl) exports functions allowing the computation of

Subresultant and Sturm-Habicht sequences. Let f, g \in Z[x, y], then you can use any of the following commands in order to compute the desired PRS:

`L := PRS:-StHa ( f, g, y ):`

L := PRS:-StHaByDet ( f, g, y ):

L := PRS:-subresPRS ( f, g, y ):

L := PRS:-SubResByDet ( f, g, y ):

Moreover, one can compute Euclid as well as Primitive-Part Polynomial Remainder Sequences with the following:

`L := PRS:-euclidPRS( f, g, x ):`

L := PRS:-primpartPRS( f, g, y):

`PrintPRS`

is used for viewing the PRS. For example, let f, g be those from the example on Bivariate Solving above:`> L := PRS:-subresPRS ( f, g, y ):`

> PRS:-PrintPRS( L );

/
2 \
2

\x - 5 x/ y + 1 + 2 x + x

y + 2 x - 3

3 2

2 x - 14 x + 13 x - 1

Finally, the variance of the above sequence evaluated at (1,0) can be computed by:

`> G := PRS:-Eval ( L, 1, 0 );`

G := [4, -1, 0]

> PRS:-var( G );

1

In order to compute the number of sign variations of an evaluated Sturm-Habicht sequence one can use the following:`> PRS:-varStHa ( G );`

Shear Transformation

One can compute a value

makes the given bivariate system arbitrary. For example:

```
> SLV:-computeShear( f, g );
```

0

Note that the above system is in Generic Position.

As a comment, keep in mind that the above operation is usually very costly.

More options will soon be available.

Updated: Nov 10, 2009.