next up previous contents
Next: Strategy Up: Strategies and Applications Previous: Unitary case of Parrot's

Strategies and motivated unknowns

In a prestrategy unknowns refers to the original unknowns presented in the problem. However, it is often the case that there will be some combination of variables which is a ``natural'' unknown for the problem. A particular class of these new unknowns, called motivated unknowns, are gotten from the 1-Decompose operation. Unfortunately, the Decompose operation is an idealization and the authors do not know an approximation to it which is implementable.

Also, even if Decompose were implementable, one would not be able to use it effectively, since the operation associates a composition of polynomials (and therefore, motivated unknowns) to a particular polynomial and applying Decompose to each polynomial in the ideal would not be practical.

For example, suppose that a polynomial tex2html_wrap_inline5338 appears on a spreadsheet and has the property that there are other polynomials tex2html_wrap_inline5340 and tex2html_wrap_inline5342 for which L p R has a 1-decomposition


where k is a polynomial in one unknown. By the definition of an ideal, L p R is in the ideal represented by the output of the spreadsheet. The polynomial L p R will not appear on the spreadsheet, since p appears on the spreadsheet. gif Therefore, in practice, a person must recognize the L and R which yield the 1-decomposition. We formalize this as follows.

Definition 5.1 A polynomial p motivates an unknown y via the equations y = q(a, ..., a, x, ..., x) if there exists polynomials L(a, ..., a, x, ..., x) and R(a, ..., a, x, ..., x) and there exists a polynomial in one unknown k(a, ..., a, y) such that LpR = k(a, ..., a, q(a, ..., a, x, ..., x)).

Of course, from the perspective of finding zeros on collections of polynomials, if p has a zero, then L p R has a zero and so k has a zero. Since k is a polynomial in only one unknown variable, finding the zeros of k is bound to be easier than finding the zeros of p.

The definition we give here is not the most general useful definition which we could have given. A more general definition would involve finding a 1-decomposition using any polynomial in the ideal generated by p rather than those of the form L p R. We have found that the definition we give above is sufficient for the problems which we are considering.

While we do not know how to implement the Decompose operation (§), there is a certain type of ``collect'' command which we have found very helpful. This ``collect'' command assists the user in performing decompositions of the polynomial at hand and helps in finding other polynomials in the ideal which would produce motivated unknowns. (See the discussion around equations in §.)

This section gives a definition of a strategy and then describes a command which ``collects'' knowns and products of knowns out of expressions. For example, suppose that A and B are knowns and X, Y and Z are unknowns. The collected form of

(5.2)               X A B X + X A B Y + Y A B X + Y A B Y + A X + A Y


(5.3)                             (X + Y) A B (X + Y) + A (X + Y).

Clearly this suggests a decomposition of (5.2) and indeed the collect command helps find decompositions of much more complicated polynomials.

Next we give a demonstration of how collect enters the NCProcess commands.

next up previous contents
Next: Strategy Up: Strategies and Applications Previous: Unitary case of Parrot's

Wed Jul 3 10:27:42 PDT 1996