# MPSolve benchmarks

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

• MPSolve v.2.1
• NSolve (Mathematica(TM) v. 3.01)
• fsolve (MAPLE(TM) V v. 5.0)
• rootpol (PARI)

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

#### 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, 25The 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

#### p(x) = (x+1) (x+a) (x+a2) ... (x+an-1), a = 100 i,   i2 = -1,   n = 10, 15, 20, 40The 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

#### p(x) = (x+1)(x+a)(x+a2)...(x+an-1), a = i/100,   i2 = -1,   n = 10, 15, 20, 40The 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

#### p(x) = 1 + x/1! + x2/2! + ... + xn/n!, n = 50, 100, 200The 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

#### p(x) = 1 + 2x + 3x2 + ... + (n+1)xn, n = 50, 100, 200, 400, 800, 1600The 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

#### p(x) = xn -1, n = 50, 100, 200, 400, 800The 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

#### p(x) = (x-1) (x-2) ... (x-n), n = 20, 40, 80, 160All 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 of a n×n band Toeplitz matrixwhose 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 of a n×n band Toeplitz matrixwhose 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

#### p(x) = (c2 x2 - 3)2 + c2 x9, c = 10n,   n = 6, 10, 20Two 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

#### p(x) = xn + (a x + 1)m, a = 100 i,  m = 3,   n =20, 100, 200, 500The polynomial is a modification of Mignotte's polynomials havingclustered 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

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

#### 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)

#### p(x) defined according to the recurrence equationp0(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

#### p(x) defined according to the recurrence equationp0(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 programUses 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

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

#### 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 perturbationof 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