The Test Database of Polynomial Systems

The progress on solving polynomial system has always been motivated by the poor performance of the existing technology on practical examples. To make the benchmarking more meaningful and relevant, most systems are taken from practical applications, cited in the literature. We refer to [Traverso 1993] and [Bini and Mourrain 1998] for similar collections.

In Tables 4 and 5 an overview of the application database is given. To save space, the algebraic description is omitted. Either the reference or the PHC distribution file can be consulted. Some systems appear in different guises, such as the cyclic n-roots and the economics problem. It allows us to see how the particular formulation of a problem can influence the solution process.

Some important characteristics of the systems are listed in Tables 6 and 7. Most systems arising from practical applications are deficient, i.e.: have fewer roots than the root count. The improvement of the mixed volume compared to the Bézout bounds is in many cases really significant. The black-box solver of PHC does not contain facilities to treat affine roots properly, therefore it may miss some isolated solutions with zero components.

The parameters of the black-box solver have been set to handle all examples of the database. In Tables 8 and 9 timings are listed for a SPARCserver-1000. We count 33 little examples, that require less than one minute to solve. There are 38 larger examples, for which PHC needs between one minute and an hour. Five big examples require more than one hour to solve.

Timings only have a temporary value. They are only good to measure the difficulty of solving one system compared to another one. The exponential gains from selecting a sharp root count are more important. The black-box solver is certainly not the optimal way to solve a particular system, although the timings give a good impression of the general performance of the package.

 

name reference title with description of the application

boon [Boon 1992] neurophysiology, posted by Sjirk Boon

butcher [Traverso 1993] Butcher's problem, from PoSSo test suite

butcher8 [Boege et al.1986] 8-variable version of Butcher's problem

camera1s [Emiris 1997] camera displacement between 2 positions, frame 1

caprasse [Traverso 1993] the system caprasse of the PoSSo test suite

cassou [Li et al. 1996] the system of Pierrette Cassou-Noguès

chemequ [Meintjes and Morgan 1990] chemical equilibrium of hydrocarbon combustion

cohn2 [Traverso 1993] the system cohn2 from the PoSSo test suite

cohn3 [Traverso 1993] the system cohn3 from the PoSSo test suite

comb3000 [Morgan 1987] Model A combustion chemistry example

conform1 [Emiris 1997] conformal analysis of cyclic molecules, instance 1

cpdm5 [Gatermann 1990] 5-dimensional system of Caprasse and Demaret

cyclic5 [Björk and Fröberg 1991] cyclic 5-roots problem

cyclic6 [Björk and Fröberg 1991] cyclic 6-roots problem

cyclic7 [Backelin and Fröberg 1991] cyclic 7-roots problem

cyclic8 [Björk and Fröberg 1994] cyclic 8-roots problem

d1 [Van Hentenryck et al. 1997] a sparse system, known as benchmark D1

des18_3 [Nauheim 1998] a "dessin d'enfant", called des18_3

des22_24 [Nauheim 1998] a "dessin d'enfant", called des22_24

discret3s [Traverso 1993] system discret3, scaled by average coefficients

eco5 [Morgan 1987] 5-dimensional economics problem

eco6 [Morgan 1987] 6-dimensional economics problem

eco7 [Morgan 1987] 7-dimensional economics problem

eco8 [Morgan 1987] 8-dimensional economics problem

extcyc5 [Verschelde and Gatermann 1995] extended cyclic 5-roots to exploit symmetry

extcyc6 [Verschelde and Gatermann 1995] extended cyclic 6-roots to exploit symmetry

extcyc7 [Verschelde and Gatermann 1995] extended cyclic 7-roots to exploit symmetry

extcyc8 [Verschelde and Gatermann 1995] extended cyclic 8-roots to exploit symmetry

fourbar [Morgan and Wampler 1990] four-bar design problem, so-called 5-point problem

fbrfive4 [Wampler 1996] Four-bar linkage through 5 points, n=4 version

fbrfive12 [Wampler 1996] Four-bar linkage, coupler curve through 5 points

gaukwa2 [Stroud and Secrest 1966] Gaussian quadrature formula 2 knots, 2 weights

gaukwa3 [Stroud and Secrest 966] Gaussian quadrature formula 3 knots, 3 weights

gaukwa4 [Stroud and Secrest 1966] Gaussian quadrature formula 4 knots, 4 weights

geneig [Chu et al. 1988] generalized eigenvalue problem

heart [Nelsen and Hodgkin 1981] heart-dipole problem

i1 [Van Hentenryck et al. 1997] Benchmark i1 from Interval Arithmetic Benchmarks

ipp [Morgan and Sommese 1987b] six-revolute-joint problem of mechanics

 

 

 

name reference title with description of the application

ipp2 [Wampler and Morgan 1991] 6R inverse position problem

katsura5 [Boege et al. 1986] a problem of magnetism in physics

kinema [Bellido 1992] robot kinematics problem

kin1 [Van Hentenryck et al. 1997] kinematics problem

ku10 [Steenkamp 1982] 10-dimensional system of Ku

lorentz [Li 1987] equilibrium of 4-dimensional Lorentz attractor

lumped [Li and Wang 1991] lumped-parameter chemically reacting system

mickey [Verschelde and Cools 1996] Mickey-mouse example as illustration

noon3 [Noonburg 1989] neural network, Lotka-Volterra system, n=3

noon4 [Noonburg 1989] neural network, Lotka-Volterra system, n=4

noon5 [Noonburg 1989] neural network, Lotka-Volterra system, n=5

proddeco [Morgan et al. 1995] system with a product-decomposition structure

puma [Morgan and Shapiro 1987] hand position and orientation of PUMA robot

quadfor2 [Verschelde and Gatermann 1995] Gaussian quadrature with 2 knots and weights

quadgrid [Sweldens 1994] interpolating quadrature formula on a grid

rabmo [Moore and Jones 1977] optimal multi-dimensional quadrature formulas

rbpl [Mourrain 1993] parallel robot, the so-called left-hand problem

rbpl24 [Mourrain 1996] parallel robot with 24 real solutions

redcyc5 [Emiris 1994] reduced cyclic 5-roots problem

redcyc6 [Emiris 1994] reduced cyclic 6-roots problem

redcyc7 [Emiris 1994] reduced cyclic 7-roots problem

redcyc8 [Emiris 1994] reduced cyclic 8-roots problem

redeco5 [Morgan 1987] reduced 5-dimensional economics problem

redeco6 [Morgan 1987] reduced 6-dimensional economics problem

redeco7 [Morgan 1987] reduced 7-dimensional economics problem

redeco8 [Morgan 1987] reduced 8-dimensional economics problem

rediff3 [Iserles 1995] 3-dimensional reaction-diffusion problem

reimer5 [Traverso 1993] The 5-dimensional system of Reimer

rose [Traverso 1993] a general economic equilibrium model

s9_1 [Nauheim 1998] small system from constructive Galois theory

sendra [Traverso 1993] the system sendra of the PoSSo test suite

solotarev [Traverso 1993] the system solotarev of the PoSSo test suite

sparse5 [Verschelde and Gatermann 1995] 5-dimensional sparse symmetric polynomial system

speer [Gatermann 1990] the system of E.R. Speer

trinks [Traverso 1993] system of Trinks from the PoSSo test suite

virasoro [Schrans and Troost 1990] the construction of Virasoro algebras

wood [Moré et al.1981] system derived from optimizing Wood function

wright [Wright 1985] system of A.H. Wright

 

$$\char93$$ name n D B_Z B_S V

boon 6 1024 344 216 20 8

butcher 7 4608 2090 605 24 5

butcher8 8 4608 1461 587 26 16

camera1s 6 64 20 20 20 20

caprasse 4 144 62 94 48 48

cassou 4 1344 368 361 24 16

chemequ 5 108 56 44 16 16

cohn2 4 900 468 358 124 18

cohn3 4 1080 484 358 213 102

comb3000 10 96 66 28 16 16

conform1 3 64 16 16 16 16

cpdm5 5 243 243 243 242 157

cyclic5 5 120 120 106 70 70

cyclic6 6 720 720 588 156 156

cyclic7 7 5040 5040 4200 924 924

cyclic8 8 40320 40320 30365 2560 1152

d1 12 4068 320 896 192 48

des18_3 8 324 544 241 46 46

des22_24 10 256 128 82 42 42

discret3s 8 256 128 128 128 128

eco5 5 54 20 16 8 8

eco6 6 162 48 36 16 16

eco7 7 486 112 80 32 32

eco8 8 1458 256 176 64 64

extcyc5 5 120 120 106 70 70

extcyc6 6 720 720 588 156 156

extcyc7 7 5040 5040 4200 924 924

extcyc8 8 40320 40320 30365 2560 1152

fbrfive12 12 4096 96 96 36 36

fbrfive4 4 256 96 194 36 36

fourbar 4 256 96 96 80 36

gaukwa2 4 24 11 11 5 2

gaukwa3 6 720 225 225 49 6

gaukwa4 8 40320 6769 6769 729 24

geneig 6 243 10 10 10 10

heart 8 576 193 193 121 4

i1 10 59049 452 437 66 66

ipp 8 256 96 96 64 48

 

 

$$\char93$$ name n D B_Z B_S V

ipp2 11 1024 576 848 288 16

katsura5 6 32 32 32 32 32

kin1 12 4608 320 896 192 48

kinema 9 64 240 64 64 40

ku10 10 1024 2 2 2 2

lorentz 4 16 14 12 12 11

lumped 4 16 8 11 7 4

mickey 2 4 4 4 4 4

noon3 3 27 29 21 21 21

noon4 4 81 81 73 73 73

noon5 5 243 243 233 233 233

proddeco 4 256 96 96 26 6

puma 8 128 16 32 16 16

quadfor2 4 24 11 11 4 2

quadgrid 5 120 10 10 10 5

rabmo 9 36000 22740 7090 136 16

rbpl 6 486 160 160 160 150

rbpl24 9 576 80 80 80 40

redcyc5 4 24 24 19 14 14

redcyc6 5 120 96 83 26 26

redcyc7 6 720 720 511 132 132

redcyc8 7 5040 3960 3107 320 144

redeco5 5 8 12 8 8 8

redeco6 6 16 28 16 16 16

redeco7 7 32 64 32 32 32

redeco8 8 64 144 64 64 64

rediff3 3 8 8 8 7 7

reimer5 5 720 720 720 720 144

rose 3 216 144 136 136 136

s9_1 8 16 41 10 10 10

sendra 2 49 49 46 46 46

solotarev 4 36 10 8 6 6

sparse5 5 100000 3840 3840 160 160

speer 4 625 384 246 96 43

trinks 6 24 24 18 10 10

virasoro 8 256 3072 256 200 200

wood 4 36 25 16 9 9

wright 5 32 32 32 32 32

 

 

name root counts start system continuation total time

boon 0h 0m 0s 190 0h 0m 5s 868 0h 0m 14s 394 0h 0m 20s 937

butcher 0h 0m 13s 267 0h 0m 29s 23 0h 1m 44s 962 0h 2m 28s 449

butcher8 0h 0m 50s 513 0h 0m 25s 188 0h 4m 20s 602 0h 5m 38s 507

camera1s 0h 0m 8s 258 0h 0m 0s 110 0h 0m 34s 406 0h 0m 44s 682

caprasse 0h 0m 0s 769 0h 0m 10s 4 0h 0m 17s 80 0h 0m 28s 888

cassou 0h 0m 1s 145 0h 0m 10s 688 0h 1m 3s 439 0h 1m 15s 972

chemequ 0h 0m 1s 116 0h 0m 4s 827 0h 0m 6s 886 0h 0m 13s 378

cohn2 0h 0m 3s 989 0h 0m 49s 953 0h 2m 49s 74 0h 3m 46s 619

cohn3 0h 0m 4s 991 0h 1m 12s 618 0h 16m 15s 864 0h 17m 37s 282

comb3000 0h 0m 7s 814 0h 0m 5s 630 0h 0m 18s 162 0h 0m 33s 118

conform1 0h 0m 0s 42 0h 0m 0s 45 0h 0m 3s 880 0h 0m 4s 310

cpdm5 0h 0m 18s 683 0h 2m 27s 225 0h 9m 51s 598 0h 12m 43s 370

cyclic5 0h 0m 0s 562 0h 0m 11s 768 0h 0m 32s 469 0h 0m 45s 993

cyclic6 0h 0m 6s 40 0h 1m 15s 816 0h 2m 44s 292 0h 4m 9s 434

cyclic7 0h 1m 15s 74 0h 15m 49s 391 0h 27m 50s 521 0h 45m 21s 434

cyclic8 0h 14m 41s 38 1h 25m 14s 851 2h 54m 28s 884 4h 35m 54s 367

d1 0h 0m 15s 182 0h 5m 34s 397 0h 13m 30s 348 0h 19m 25s 426

des18_3 0h 3m 51s 209 0h 1m 19s 587 0h 1m 44s 25 0h 6m 57s 913

des22_24 0h 0m 23s 538 0h 0m 50s 660 0h 1m 22s 251 0h 2m 40s 53

discret3s 0h 2m 20s 4 0h 0m 0s 719 0h 56m 20s 922 0h 58m 52s 121

eco5 0h 0m 0s 281 0h 0m 1s 222 0h 0m 2s 829 0h 0m 4s 686

eco6 0h 0m 2s 217 0h 0m 4s 132 0h 0m 6s 771 0h 0m 13s 785

eco7 0h 0m 22s 215 0h 0m 20s 511 0h 0m 34s 19 0h 1m 18s 249

eco8 0h 5m 28s 66 0h 1m 1s 471 0h 1m 55s 472 0h 8m 27s 528

extcyc5 0h 0m 2s 355 0h 0m 36s 607 0h 0m 37s 521 0h 1m 17s 726

extcyc6 0h 0m 30s 15 0h 1m 45s 137 0h 2m 56s 572 0h 5m 15s 706

extcyc7 0h 9m 15s 674 0h 17m 22s 278 0h 30m 29s 581 0h 57m 33s 835

extcyc8 1h 58m 58s 816 1h 36m 57s 179 3h 58m 54s 943 7h 36m 30s 580

fbrfive12 0h 1m 30s 161 0h 1m 6s 686 0h 2m 18s 859 0h 4m 58s 570

fbrfive4 0h 0m 0s 463 0h 0m 17s 283 0h 1m 2s 690 0h 1m 21s 972

fourbar 0h 0m 0s 625 0h 0m 8s 706 0h 2m 1s 20 0h 2m 12s 565

gaukwa2 0h 0m 0s 55 0h 0m 0s 705 0h 0m 1s 460 0h 0m 2s 391

gaukwa3 0h 0m 1s 430 0h 0m 22s 803 0h 0m 52s 615 0h 1m 17s 674

gaukwa4 0h 1m 18s 940 0h 27m 42s 595 0h 52m 30s 671 1h 21m 42s 787

geneig 0h 0m 0s 476 0h 0m 0s 303 0h 0m 11s 314 0h 0m 14s 648

heart 0h 1m 10s 899 0h 3m 14s 236 0h 4m 39s 75 0h 9m 6s 712

i1 0h 0m 37s 869 0h 0m 49s 215 0h 1m 59s 959 0h 3m 29s 913

ipp 0h 1m 4s 541 0h 1m 21s 14 0h 1m 47s 940 0h 4m 16s 287

 

 

name root counts start system continuation total time

ipp2 0h 8m 21s 346 0h 11m 59s 944 0h 27m 18s 539 0h 47m 48s 632

katsura5 0h 0m 12s 382 0h 0m 0s 8 0h 0m 27s 511 0h 0m 41s 303

kin1 0h 2m 2s 926 0h 5m 39s 399 0h 11m 37s 403 0h 19m 25s 259

kinema 0h 2m 28s 847 0h 0m 0s 22 0h 3m 11s 205 0h 5m 42s 168

ku10 0h 0m 1s 547 0h 0m 2s 253 0h 0m 3s 611 0h 0m 8s 357

lorentz 0h 0m 0s 173 0h 0m 0s 23 0h 0m 6s 633 0h 0m 7s 256

lumped 0h 0m 0s 289 0h 0m 0s 714 0h 0m 1s 975 0h 0m 3s 255

mickey 0h 0m 0s 8 0h 0m 0s 2 0h 0m 0s 175 0h 0m 0s 248

noon3 0h 0m 0s 58 0h 0m 0s 33 0h 0m 4s 639 0h 0m 5s 154

noon4 0h 0m 0s 399 0h 0m 0s 103 0h 0m 51s 160 0h 0m 53s 163

noon5 0h 0m 2s 922 0h 0m 0s 316 0h 7m 9s 741 0h 7m 17s 834

proddeco 0h 0m 0s 299 0h 0m 10s 135 0h 0m 42s 488 0h 0m 54s 26

puma 0h 0m 2s 457 0h 0m 0s 420 0h 0m 34s 43 0h 0m 40s 105

quadfor2 0h 0m 0s 24 0h 0m 0s 183 0h 0m 0s 910 0h 0m 1s 271

quadgrid 0h 0m 4s 451 0h 0m 0s 159 0h 0m 14s 627 0h 0m 20s 443

rabmo 0h 1m 10s 899 0h 3m 14s 236 0h 4m 39s 75 0h 9m 6s 712

rbpl 0h 1m 32s 693 0h 0m 0s 670 0h 10m 24s 859 0h 12m 4s 957

rbpl24 3h 19m 40s 323 0h 0m 1s 331 0h 9m 55s 836 3h 29m 47s 764

redcyc5 0h 0m 0s 348 0h 0m 2s 767 0h 0m 3s 505 0h 0m 6s 995

redcyc6 0h 0m 3s 559 0h 0m 9s 911 0h 0m 17s 549 0h 0m 31s 863

redcyc7 0h 0m 54s 118 0h 1m 56s 885 0h 3m 12s 794 0h 6m 7s 216

redcyc8 0h 9m 58s 283 0h 10m 54s 911 0h 18m 11s 414 0h 39m 14s 893

redeco5 0h 0m 0s 290 0h 0m 0s 3 0h 0m 3s 109 0h 0m 3s 671

redeco6 0h 0m 2s 389 0h 0m 0s 6 0h 0m 7s 958 0h 0m 10s 860

redeco7 0h 0m 22s 751 0h 0m 0s 10 0h 0m 24s 990 0h 0m 48s 725

redeco8 0h 4m 30s 648 0h 0m 0s 18 0h 1m 20s 991 0h 5m 53s 618

rediff3 0h 0m 0s 28 0h 0m 0s 225 0h 0m 0s 568 0h 0m 1s 2

reimer5 0h 0m 0s 913 0h 0m 0s 65 0h 9m 20s 820 0h 9m 30s 537

rose 0h 0m 0s 86 0h 0m 0s 347 0h 2m 26s 320 0h 2m 30s 262

s9_1 0h 0m 0s 663 0h 0m 0s 65 0h 0m 14s 843 0h 0m 17s 344

sendra 0h 0m 0s 50 0h 0m 0s 131 0h 0m 18s 328 0h 0m 19s 474

solotarev 0h 0m 0s 79 0h 0m 0s 365 0h 0m 1s 37 0h 0m 1s 695

sparse5 0h 0m 0s 396 0h 0m 21s 672 0h 3m 45s 456 0h 4m 11s 36

speer 0h 0m 1s 554 0h 0m 52s 9 0h 13m 35s 109 0h 14m 31s 786

trinks 0h 0m 0s 666 0h 0m 1s 855 0h 0m 5s 962 0h 0m 8s 967

virasoro 3h 40m 50s 731 0h 7m 0s 273 0h 7m 42s 993 3h 55m 41s 856

wood 0h 0m 0s 55 0h 0m 0s 761 0h 0m 2s 860 0h 0m 3s 912

wright 0h 0m 1s 332 0h 0m 0s 6 0h 0m 13s 251 0h 0m 15s 210

 

The demonstration database of polynomial systems is still growing in order to increase the awareness of the importance and relevance of solving polynomial systems to applied mathematics and scientific computing.

In closing some user applications of PHC are mentioned. PHC was used actively by Charles Wampler  [1996] to count the roots of various systems in mechanical design. Frank Sottile applied PHC to compute root counts for linear subspace intersections of the Schubert calculus, see [Sottile 1998] for various tables. A third example comes from computer graphics. To show that the 12 lines tangent to four given spheres can all be real, Thorsten Theobald used PHC, choosing appropriate parameters in the algebraic formulation set up by Cassiano Durand.