:: software :: SLV

• Home
• Research
• Software
• Contact

software for Real Solving

SLV is an open source C library for isolating and approximating the real roots of univariate polynomials with integer coefficients.
Given a square-free polynomial with integer coefficients it computes disjoint intervals with rational endpoints, each containing one and only one real root of the polynomial.
Currently SLV is using Descartes' algorithm. In the near future an implementation of the Continued Fraction algorithm (CF) will be also available.

SLV

(version 0.5)

Get source code

• Download SLV
• Unzip and ...
  > tar -zxvf slv-0.5.tar.gz
  
  In the makefile adjust the variables to point to your installation of gmp, e.g.
  GMP_INC=/usr/local/include
GMP_LIB=/usr/local/lib
  
  Finally, compile
  > make
  
  
  
  An executable slv should be available.

Short Tutorial

• Input format
  A input file contains the degree of polynomial and then the coefficients in ascending order.
  For example the file test.dat is as follows
  > more test.dat
  5 -120 600 -600 200 -25 1
  which corresponds to the polynomial -120 + 600*x - 600*x^2 + 200*x^3 -25*x^4 + x^5
• Assume that you have downloaded SLV, then type
  > slv -h
  The syntax is:
  slv [-h] [-f file] [-i prec] [-p]
  Details:
  -h : prints help message
  -f fname : read the coeffs from the fname
  -i prec : the output intervals have width 2^(-prec)
  -p : print roots (Default: no print)
  
• Assuming the there is a file named test.dat
  A sample run and output of the program is
  
  > ./slv -f ../test.dat -i 20 -p
  Isolating test.dat
  Finish isolating
  /*------------------------------------------------------------*/
  Statistics:
  #degree : 5
             Neg     Pos   Total
  #bound :    -1     6
  #roots :     0     5     5
  
  #nodes :     0     10    10
  #depth :     0     5     5
  #trans :     0     5     5
  #homo :      0     9     9
  #pos_h_1 :   0     2     2
  #pos_h_2 :   0     3     3
  #half_h :    0     1     1
  /*------------------------------------------------------------*/
  Refinement process...
  #roots = 5
  [
   -1 (276363/2^20, 276364/2^20)
    1 (1482060/2^20, 1482061/2^20)
   -1 (3771125/2^20, 3771126/2^20)
    1 (7430010/2^20, 7430011/2^20)
   -1 (13254840/2^20, 13254841/2^20)
  ]
  
  Solving time: 0.000100 s
  Refinement time: 0.000103 s
  Total time: 0.000203 s
  
  
  
  

Relevant publications and links: [EMT10] [TE08] [T12] [RZ04] SYNAPS