Timing Data

This is a reference page for MAPC timing data, as we improve the speed of the code. All timings are on the SGI Cystine. We begin with a brief description of the speedups being applied.

The Pseudoroot Algorithm

The pseudoroot algorithm is a floating point filter for univariate polynomial root isolation.

Shankar Krishnan's Precise library

Precise is a library for arbitrary precision floating point numbers. All calculations are done with a specified number of digits. After a number of steps, the number of significant digits will of course be less than the number of digits used, but if the final result is not known to sufficient precision, the whole calculation is redone with more digits.

Preliminary Data

Preliminary timing data using early versions of the pseudoroot code.

Curve topology

Results for the program ctop. For each curve on which the test was performed, there is a link to a reference page giving the polynomial and its graph (i.e., the graph of its zero set). For some of the curves, there is also a link to a graphical display of the output of ctop. The results shown are for each optimization independently.

• fun1: reference   output

  	Total time	Sturm	Pseudoroot
  Without Speedups	97.23	45.72
  With Pseudoroot	5.59	0.0	0.03
  With Precise	5.51	0.0

ESOLID

This is really the acid test. (Until the MA code is ready.)

• The union of two cubes.

  	Total time	Sturm	Pseudoroot
  Without Pseudoroot	4.53	0.0	0.0
  With Pseudoroot	4.47	0.0	0.0

• A difference of two cylinders.

  	Total time	Sturm	Pseudoroot
  Without Pseudoroot	16.32	1.53
  With Pseudoroot	12.21	0.0	0.24
  With Precise	13.68	0.0

• A union of two cylinders.

  	Total time	Sturm	Pseudoroot
  Without Pseudoroot	32.1	3.03	0.0
  With Pseudoroot	21.84	0.0	0.57

Last modified: November 28, 1999