| Abstract: | The McCallum Projection for Cylindrical Algebraic Decomposition (CAD)
produces a smaller projection factor set than previous projections,
however it does not always produce a sign-invariant CAD for the set of
input polynomials. Problems may arise when a (k+1)-level projection
factor vanishes identically over a k-level cell. According to
McCallum's paper, when this happens (and k+1 is not the highest
level in the CAD) we do not know whether the projection is valid,
i.e. whether or not a sign-invariant CAD for the set of input
polynomials will be produced when lifting is performed in the usual
way. When the k-level cell in question has dimension 0, McCallum
suggests a modification of the lifting method that will ensure the
validity of his projection, although to my knowledge this has never
been implemented.
In this paper we give easily computable criteria that often
allow us to conclude that McCallum's projection is valid even though a
projection factor vanishes identically over a cell. We also improve
on McCallum's modified lifting method.
We've incorporated the ideas contained in this paper into QEPCAD, the
most complete implementation of CAD. When McCallum's projection is
invalid because of a projection factor not being order-invariant over
a region on which it vanishes identically, at least a warning message
ought to be issued.
Currently, QEPCAD may print warning messages that are not needed, and
may fail to print warning messages when they are needed. Our
implementation in QEPCAD ensures that warning messages are printed
when needed, and reduces the number of times warning messages are
printed when not needed.
Neither McCallum's modified lifting method nor our improvement of it have
been implemented in QEPCAD --- the design of the system would make
implementing such a feature quite difficult. |