QEProjectionStructure.mesa
Last Edited by Arnon: January 28, 1988 2:13:03 pm PST
Projections
Note: Projection operators, i.e. methods, should be added to PolynomialSequences class.
DIRECTORY
Rope,
AlgebraClasses;
QEProjectionStructure: CEDAR DEFINITIONS
~ BEGIN
Element Representation
ProjectionType: TYPE = { standard, augmented, mccallum, none };
OnePolynomialProjection: TYPE = AlgebraClasses.Object;
TwoPolynomialProjection: TYPE = AlgebraClasses.Object;
OnePolynomialProjectionData: TYPE = REF OnePolynomialProjectionDataRec;
OnePolynomialProjectionDataRec: TYPE = RECORD [
input: Object,
leadingCoefficient: Object,
polynomials: Sequences.Sequence ← NIL -- of Polynomial's
];
TwoPolynomialProjectionData: TYPE = REF TwoPolynomialProjectionDataRec;
TwoPolynomialProjectionDataRec: TYPE = RECORD [
input1, input2: Object,
polynomials: Sequences.Sequence ← NIL -- of Polynomial's
];
Element Operations
Projection: PROC [basis: SEQ.Sequence] RETURNS [basisIndividualProjections: SEQ.Sequence, basisPairwiseProjections: SEQ.Sequence];
The requirements are:
(1) we have a certain set K of polynomials in E^r which we need to make delineable on each cell and each signature-cluster in E^(r-1).
(2) The collection of cells we end up with in E^r must have the boundary property: the boundary of any cell must equal the union of some collection of lower-dimensional cells.
Question: why does the boundary property really matter?
Possible answer: then it doesn't matter where you probe when slicing an adjacency. To be more precise, boundary property is required for the "decoding" phase of our (0,1) adjacency determination in 3-space to work - we have to know that the 0-cells we see in our 2-space projection are images of 0-cells in the 3-space decomposition.
Given these, our approach is:
(1) Compute contents and basis(pp) = K of inputs, pull off initial sequences of non-constant coeffs of all basis elts, compute basis for contents union initial sequences, do a signature-invariant decomp D of E^(r-1) to get regions on which each element of K has constant degree. Note that if any element of K is identically zero at some point of E^r-1, D will have maximal regions for this property.
(2) using the appropriate reducta of elements of K (ignore identically zero elements), compute projection sets for each reducta pattern that occurs on a positive-dimensional regions, compute basis. For each positive-dimensional region, use this basis to break it up to be signature-invariant with respect to its projection basis. We end up with a new decomposition D'.
(3) Assume now r <= 3; maybe works for general r.
(4) On each region in E^(r-1), evaluate the appropriate non-identically zero reducta of elements of K to get a set of algebraic polys; compute its basis. If any element of K is
identically zero on this region, determine the appropriate algebraic polynomials whose roots we need to take account of to insure boundary property, compute their basis, merge the two bases. Isolate roots of the final basis to determine the stack over this region.
Simpler version, to get a single basis set in each E^i:
(1) Compute P1 = contents and K = basis(pp) of inputs.
Compute P2 = initial sequences of non-constant coeffs of all basis elts,
Compute each Pijk, where suppose K has three elements, 0 <= i < length of initial sequences of non-constant coeffs of K1, 0 <= j < etc., Qijk is projection computed using ith, jth, and kth reducta of respective elements of K, and Pijk is the result of simplifying Qijk with respect to the side relations that the appropriate initial non-constant coeffs of the elements of K are equal to zero.
(Possible precomputation for each Pijk: do a heuristic test (e.g. Groebner basis to check emptiness of complex variety), or cad, to check that real varieties stay nonempty as you take progressively larger sequences of initial non-constant coeffs; if such a variety is empty, then you don't need to continue. It could happen that appropriate tails of initial sequences of elements of K could be thrown out of P2).
Set P = P1 un P2 un (all Pijk's).
Compute P-invariant decomposition of E^(r-1).
(2) Assume now r <= 3; maybe works for general r.
(3) Extension phase: On each region in E^(r-1), evaluate the appropriate non-identically zero reducta of elements of K to get a set of algebraic polys; compute its basis. If any element of K is identically zero on this region, determine the appropriate algebraic polynomials whose roots we need to take account of to insure boundary property, compute their basis, merge the two bases. Isolate roots of the final basis to determine the stack over this region. Record K-signature of each element of the stack.
END.