SLV
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:
Dimitrios I. Diochnos Dept. of Mathematics, Statistics, and Computer Science, Univ. of Illinois at Chicago.
Ioannis Z. Emiris Dept. of Informatics and Telecommunications, Univ. of Athens.
Elias P. Tsigaridas INRIA - Sophia-Antipolis.

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 LIBPATH which should point on the appropriate path where the source code is stored in your system. On the following, we assume that our library is located under /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 Z2:

> 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 Ralg numbers that was returned in the univariate case above; the following are examples on
the 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 T so that the transformation (x, y) --> (x + T*y, y)
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.