Dataset supporting the paper: Truth table invariant cylindrical algebraic decomposition

Data collection method:

The data collection was by recording cell counts and timings of various CAD algorithms. A full explanation can be found in the associated paper. Regarding the example set in Section82-ExampleSet.txt, we note that the timings for Maple reported in the paper were from running Maple in command line mode. The same example set was tested in Qepcad. Here explicit ECs for a parent formula were entered in dynamically as products of the individual sub-formulae ECs, in cases where an explicit EC exists. Finally, the example set was also tested in Mathematica. Mathematica's CAD command does not return cell counts - these were obtained upon request to a Mathematica developer. Hence they are not recreatable using the information here (something outside the control of the present authors).

Technical details and requirements:

To run the Maple worksheet you will need a copy of the commercial computer algebra software Maple. This is currently available from http://www.maplesoft.com/products/maple/. The examples were run in Maple 16 (released Spring 2012). It is likely that the same results would be obtained in Maple 17, 18, 2015 and future versions, but this cannot be guaranteed. An additional code package, developed at the University of Bath and included in this dataset as `ProjectionCAD.mpl`, is required. If you do not have a copy of Maple you can still read the PDF printout of the worksheets. Qepcad-B is a free piece of software for Linux which can be obtained from http://www.usna.edu/CS/qepcadweb/B/QEPCAD.html.

Additional information:

Within the zipped directories Section1to7-Qepcad.zip and Section83-Qepcad.zip, all the files end in either "-in.txt" or "-out.txt". The former give input for Qepcad and the latter record output. Hence readers without access to Qepcad (e.g. on a Windows system) can still observe the output in the latter files. Within the file Section82-ExampleSet.txt, the 29 examples are defined in the following syntax, used by the TTICAD algorithm that is the subject of the paper: (a) First a line starting with "#" giving the full example name followed in brackets by the shortened name used in Table 2. (b) Then a second line in which the example is defined as a list of two sublists: (i) The first sublist defines the polynomials used. They are sorted into further lists, one for each formulae in the example. Each of these has two entries. The first is either a polynomial defining an equational constraint (EC); a list of polynomials defining multiple ECs; or an empty list (signalling no ECs). The second is a list of any non ECs. (ii) The second sublist is the variable ordering from highest (eliminate first in projection) to lowest. Note that Maple algorithms use this order by Qepcad-B the reverse. This text file doubles as a Maple function definition. When read into Maple the command GenerateInput is defined which can provide the input in formats suitable for the three Maple algorithms tested.

Methodology link: