Q E P C A D - The Projection Phase

NOTE: This section of the documentation is out of date!
In the Projection Phase, QEPCAD computes a set of polynomials that implicitly defines the CAD that it will later explicitly construct in the Stack Construction Phase. This set of polynomials, the projection factor set, must satisfy some special properties in order to define a CAD. So the goal of this phase is to construct as small a set as we can while ensuring that it defines a CAD and contains certain polynomials we'll need to solve the quantifier elimination problem. A projection operator is a function that's used to define a projection factor set, and several are available in QEPCAD.

The Average User

=======================================================
Enter an informal description  between '[' and ']':
[ Using Hong's Projection at level 4 ]
Enter a variable list:
(a,b,d,c)
Enter the number of free variables:
4
Enter a prenex formula:
[ 
54 c^3 - 27 a b c^2 + 6 a^3 c^2 - 144 b d c + 
6 a^2 d c + 4 b^3 c - a^2 b^2 c + 96 a d^2 + 40 a b^2 d 
- 9 a^3 b d = 0 
].
=======================================================

Before Normalization >
go

Before Projection (c) >
proj-op (m,m,h)

Before Projection (c) >
go

Before Choice >
go

Before Solution >
From the perspective of the average user, two projection operators are important: Hong's projection and McCallum's projection. McCallum's projection produces a smaller projection factor set, but QEPCAD sometimes discovers during the Stack Construction Phase that it cannot be sure of the validity of McCallum's projection and prints out an error message (actually a "possible error" message). Hong's projection is always valid, but produces a larger projection factor set. QEPCAD's default behaviour is to use a slightly improved version of McCallum's projection operator. [ Essentially it makes a half-hearted attempt to apply the Reduced McCallum projection. It's only half-hearted because it has a very weak system for trying to determine whether the system of coefficients for a projection factor is consistent. ] If QEPCAD later prints out an error message, it's up to the user to restart the computation and explicitly use Hong's projection operator instead of McCallum's. (Note: McCallum's projection operator is always valid when projecting in 2 or 3 variables.) In the example to the right, we show how to specify which projection operator should be used. Running this same example with the default (McCallum's projection used at every step) produces the error message "Error! Delineating polynomial should be added over cell(2,2)!" during the stack construction phase. In this case it turns out that McCallum's projection is not invalid, it's just that QEPCAD can't prove that it's valid. Thus we must rerun the example with Hong's projection for all but the last two projection steps. In general, if McCallum's projection produces an error message for a problem involving variables (x1,x2,...,xk) you should issue the command proj-op (m,m,h,h,h,...,h) where the list has k-1 elements, all but the first two of which are 'h'.

The Advanced User
If you know some things about different projection operators you can interact with QEPCAD to do better - specifically by removing projection factors during the projection process. I'll add some info on that in the future!


Christopher W Brown
Last modified: Tue Mar 13 13:33:34 EDT 2007