The McCallum Projection, Lifting, and Order-Invariance
NAVAL ACADEMY ANNAPOLIS MD DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 k1-level projection factor vanishes identically over a k-level cell. According to McCallums paper, when this happens and the k1 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 neve been implemented. In this paper we give easily computable criteria that often allow us to conclude that McCallums projection is valid even though a projection factor vanishes identically over a cell. WE also improve on McCallums modified lifting method. We have incorporated the ideas contained in this paper into QEPCAD, the most complete implementation of CAD. When McCallums 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 McCallums 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.
- Numerical Mathematics