MPSolve benchmarks


We report the CPU time, expressed in seconds, needed to compute the roots of univariate polynomials with the following functions:

The experiments have been performed on a Pentium 200 MMX with 64MB RAM under the Linux operating system.
The set of test polynomials has been divided into the following classes:


Polynomials with roots in geometric progressions

  

Spiral

p(x) = (x+1) (x+1+a) (x+1+a+a2) ... (x+1+a+a2+... +an), 
 a = i/1000,   i2 = -1,   n = 10, 15, 20, 25
The polynomial has roots along a spiral centered in 1/(1-a).
Their distance from the center decreases exponentially

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

10

1.51 

 

1.53

26.3 

20.4 

24.5 

17.5

13

16

 

1.63

73 

250 

59 

45.6

156

36.8

10

15

13.8 

 

13.7 

231 

102 

129 

16.8

7.4

9.4

 

13.8 

957 

238 

-

69

17

15

20

91 

 

84.4 

1860 

400 

22

4.7

-

 

92.4 

-

-

-

20

25

279 

 

227 

1557 

-

6.8

-

 

276 

-

-

-

25

Timings on a Pentium 200 MMX


 
  

Geometric - 1

p(x) = (x+1) (x+a) (x+a2) ... (x+an-1), 
 a = 100 i,   i2 = -1,   n = 10, 15, 20, 40
The polynomial has roots in geometric progression of ratio a, |a| > 1.

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

10

.  

0.04

3.1 

25

175

75

  . . . .      

10

15

.  

0.05 

2.9 

32.4 

14.8 

58

648

296

  . . . .      

15

20

.  

0.08 

280 

61.8 

-

3496

772

  . . . .      

20

25

.  

0.45 

>36000 

-

-

>45000

  . . . .      

25

Timings on a Pentium 200 MMX


 
  

Geometric - 2

p(x) = (x+1)(x+a)(x+a2)...(x+an-1), 
 a = i/100,   i2 = -1,   n = 10, 15, 20, 40
The polynomial has roots in geometric progression of ratio a, |a| < 1.

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

10

.  

0.03

5.9 

14.4 

197

200

480

  . . . .      

10

15

.  

0.07 

45 

54.4 

38 

643

777

543

  . . . .      

15

20

.  

0.11 

255 

424 

205 

2322

3853

1859

  . . . .      

20

25

.  

0.6 

>36000 

-

>60000

-

  . . . .      

25

Timings on a Pentium 200 MMX



Polynomials with roots along a curve

  

Truncated exponential

p(x) = 1 + x/1! + x2/2! + ... + xn/n!,
n = 50, 100, 200

The polynomial has roots along a curve.

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

50

.  

0.7

17.6 

8.2 

27.6 

25

12

39

  . . . .      

50

100

.  

7.4 

364 

726 

243 

49

98

33

  . . . .      

100

200

.  

66 

2434 

-

-

37

  . . . .      

200

.Timings on a Pentium 200 MMX


 
  

Easy polynomial

p(x) = 1 + 2x + 3x2 + ... + (n+1)xn,
n = 50, 100, 200, 400, 800, 1600

The polynomial has roots along a curve, the roots are well conditioned.

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

50

.  

0.4

15.7 

5.7 

21.3 

39

14

53

  . . . .      

50

100

.  

1.7 

164 

25 

156 

97

15

92

  . . . .      

100

200 .   8.5 772 169 >9600 91 20 >1136   . . . .       200
400 .   35                 . . .       400
800 .   150               . . . .       800

1600

.  

725 

 

 

 

 

 

 

  . . . .      

1600

Timings on a Pentium 200 MMX


 
  

Roots of unity

p(x) = xn -1,
n = 50, 100, 200, 400, 800

The polynomial has roots on the unit circle, all the roots are well conditioned.

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

50

.  

0.2

0.2 

0.7 

20 

1

3.5

100

  . . . .      

50

100

.  

0.5 

0.4 

1.4 

155 

0.8

2.8

310

  . . . .      

100

200 .   1.7 1 3.6 1823 0.6 2 1072   . . . .       200
400 .   7.4 3.5 10 - 0.5 1.4 -   . . . .       400
800 .   25.7 12.8 43 - 0.5 1.7 -   . . . .       800
Timings on a Pentium 200 MMX


 
  

Wilkinson's polynomial

p(x) = (x-1) (x-2) ... (x-n),
n = 20, 40, 80, 160

All the roots are ill conditioned.

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

20

.  

0.2

1.5 

15.1 

3.5 

8

76

18

  . . . .      

20

40

.  

1.6 

40.6 

181 

30.1 

25

113

19

  . . . .      

40

80 .   19 277 1266 357 15 67 19   . . . .       80
160 .   243 - - - - - -   . . . .       160
Timings on a Pentium 200 MMX


 
  

Characteristic polynomial - 1

Characteristic polynomial of a nn band Toeplitz matrix 
whose entries along the diagonals are given by 
(a-2, a-1, a0, a1, ..., a6) = (-i, -3, 0, 10, 1, i, 2 i, -3, 1),
n = 128, 256

Many roots cluster into accumulation points. 

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

128

.  

8.5

424 

50

-

-

  . . . .      

128

256

.  

90 

3017 

33

-

-

  . . . .      

256

Timings on a Pentium 200 MMX


 
  

Characteristic polynomial - 2

Characteristic polynomial of a nn band Toeplitz matrix 
whose entries along the diagonals are given by 
(a-2, a-1, a0, a1, ..., a6) = (-7 i, -32, 0, 10, 0, 0, 0, -32, 1),
n = 128, 256

Many roots cluster into accumulation points. 

  Isolate   Approximate 50 digits   Approximate 200 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

128

.  

23

439 

19

-

-

  . . . .      

128

256

.  

301 

>3600 

>12

-

-

  . . . .      

256

Timings on a Pentium 200 MMX



Polynomials with few clustered roots and/or large and small moduli

  

Kameny polynomial

p(x) = (c2 x2 - 3)2 + c2 x9,
c = 10n,   n = 6, 10, 20

Two extremely close real roots (with 20, 70, 247 common decimal digits),
a complex pair with small imaginary parts (10-27, 10-90, 10-315).
The remaining roots are well separated, one of them is real.

  Isolate   Approximate 50 digits   Approximate 400 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

6

0.02  

0.02

3.7 

1.8 

185

200

90

  0.2 83 36 24 415 180 120

6

10 0.12   0.05 3.2 67 5.2 64 1340 104   0.3 F 55 29 - 165 87 10

20

0.3  

0.05 

3.2 

>2000 

36.5 

64

>40000

730

  0.7 F >1300 77 - 1857 110

20

Timings on a Pentium 200 MMX


 
  

Mignotte-like polynomial

p(x) = xn + (a x + 1)m,
a = 100 i,  m = 3,   n =20, 100, 200, 500

The polynomial is a modification of Mignotte's polynomials having
clustered roots whose distance is close to the Mahler bound.
It has m roots close to -1/a and the remaining are roughly displaced along a circle.

  Isolate   Approximate 50 digits   Approximate 400 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

20

0.04  

0.09

12 

13 

9.3 

120

130

93

  0.2 83 36 24 415 180 120

20

100 0.42   0.77 1650 >2000 587 2142 >2597 726   0.3 F 55 29 - 165 87 100
200 1.5   2.13 - - - - - -   0.7 F >1300 77 - 1857 110 200

500

16.7  

19.9 

-

-

-

  .            

500

Timings on a Pentium 200 MMX


 
  

Roots with large and small moduli - 1

p(x) = x500 + 10200 x499 + 10500 x495 + 10499 x480 + 103 x3 + 3 102 x2 + 1.  

  Isolate   Approximate 50 digits   Approximate 400 digits  
  CPU   CPU Speedup   CPU

Speedup

 
 

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 
  23.1  

19.7

-

-

-

  . . . .        
Timings on a Pentium 200 MMX


 
  

Roots with large and small moduli - 2

p(x) = (x12 - (1020 x - 1)4) (1 + (1020 + x)4 x8)
4 roots of modulus 10-20, 4 roots of modulus 1020,  60 common digits.

  Isolate   Approximate 50 digits   Approximate 1000 digits  
  CPU   CPU Speedup   CPU

Speedup

 
 

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 
  0.64  

0.33

1699 

>3000 

83 

5048

>9090

251

  5.4 - - 1485 - - 275  
Timings on a Pentium 200 MMX



Polynomials with the roots in a fractal (Mandelbrot set)

  

Mandelbrot polynomial - 1

p(x) defined according to the recurrence equation 
p0(x) = 1,   pi+1(x) = x pi2(x) + 1,
i = 0, 1, ...   the degrees are n = 1, 3, 7, 15, ...
 
The polynomials have roots in the Mandelbrot set.

  Isolate   Approximate 50 digits   Approximate 1000 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

31 .   0.25 2.6 1.8 4.5 10 7.2 18   . . . .       31
63 .   1.83 26 175 26 14 95 14   . . . .       63
127 .   18.5 363 1382 356 19 74 19   . . . .       127
255 .   213 2781 - 2544 13 - 12   . . . .       255
511 .   3272               . . . .       511
Timings on a Pentium 200 MMX


 
  

Mandelbrot polynomial - 2

p(x) defined according to the recurrence equation 
p0(x) = 1,   pi+1(x) = x pi2(x) + 1,
i = 0, 1, ...   the degrees are n = 1, 3, 7, 15, ...
 
Polynomial defined by means of a straight line program
Uses a special feature of MPSolve: polynomial defined by a C program.

  Isolate   Approximate 50 digits   Approximate 1000 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

31 .   0.12               . . . .       31
63 .   0.6               . . . .       63
127 .   3.33               . . . .       127
255 .   23.7               . . . .       255
511 .   163               . . . .       511
1023 .   1122               . . . .       1023

2047

.   8537               . . . .      

2047

Timings on a Pentium 200 MMX



Polynomials with many multiple roots

  

Kirrinnis polynomial

p(x) = (x4 - 1 / 16)m   (x4 - (1 / 2 + e)4) 16m/e4,
e = 1/4096,   m = 10, 20, 40

4 multiple roots 1/2, -1/2, i/2, -i/2, of multiplicity m, 
4 roots 1/2+e, -(1/2+e), i(1/2+e), -i (1/2+e) pretty close to the former. 
Between parentheses is reported the time needed after applying a symbolic preprocessing. 

  Isolate   Approximate 50 digits   Approximate 400 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

10 .   6.9
(0.01)
54.3 0.02 0.23 8
(5430)
0.003
(2)
0.03
(23)
  . . . .       10
20 .   7.2
(0.02)
>3600 0.4 0.23 >500 (>180000) 0.05
(20)
0.03
(11)
  . . . .       20

40

.  

39.9
(0.3) 

1.1 

7.7 

-

0.03
(3.6)

0.2
(25)

  . . . .      

40

Timings on a Pentium 200 MMX



Polynomials with all the roots grouped into few clusters

  

Modified Kirrinnis polynomial

p(x) = (x4 - 1 / 16)m   (x4 - (1 / 2 + e)4)16m/e4+x4m+4,
e = 1/4096,   m = 10, 20, 40
 
 
The polynomial is obtained by a tiny relative perturbation 
of the leading coefficient of the Kirrinnis polynomials. 
They have simple roots clustered into 4 groups, and degree 4 m + 4. 

  Isolate   Approximate 50 digits   Approximate 400 digits  
  CPU   CPU Speedup   CPU

Speedup

 

n

MPSolve

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

 

MPSolve

Math

Maple

Pari

Math

Maple

Pari

n

10 .   2.4 4 110 29 1.6 45 12   . . . .       10
20 .   11 27 - 174 2.4 - 16   . . . .       20

40

.  

81 

227 

1512 

2.8

- 

19

  . . . .      

40

Timings on a Pentium 200 MMX

 


home