> BuildCad: PROC [inputPolynomials: SEQ.Sequence, cadStructure: AC.Structure] RETURNS [cad: Cad]; <> CoarsestSqFreeBasis: PROC [inputPolynomials: SEQ.Sequence, localizationFormula: QFF.Formula _ NIL] RETURNS [contents, basis: SEQ.Sequence]; Projection: PROC [basis: SEQ.Sequence] RETURNS [basisProjection: SEQ.Sequence]; <> <<(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.>> <> <> <> <<(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.>> <> <<(1) Compute P1 = contents and K = basis(pp) of inputs.>> <> <> <<(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).>> <> <> <<(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. >> <> BasePhase: PROC [cad: Cad]; <=1 space; follow chain of induced cad's down to 1-space, contruct cells there. Fill in basisSignature's = primarySignature's of cells. If 1-space cad.localizationFormula # NIL, then discard cells which don't satisfy it.>> <> ExtractClusters: PROC [cad: Cad, numComponents: CARDINAL] RETURNS [clusters: SEQ.Sequence]; <> <> << User specifies polynomials with respect to which to cluster by (*,*,@,*,*,@) tuples (@ is new FormulaOperators.Op).>> <> <> <> <> <<};>> <> <> <> <> <<};>> <<>> <> <> <<>> <> <> <<>> AdjacenciesOverAdjacency: PROC [dimension: CARDINAL, adjacency: Adjacency, cad: Cad] RETURNS [newAdjacencies: LIST OF Adjacency]; <> <> <> <> <> <> <> <> RegionExtendCadToCad: PROC [cad: Cad]; <> <> <> <<1. MaximalSignedRegions[i-1, cad, TRUE]; regions _ ExtractSignedRegions[i-1, cad, TRUE]; sort regions in order of decreasing dimension (for i-1 = 2, put degenerate 0-dimensional regions after nondegenerate).>> <<2. cad.cells _ NIL; Go down sorted list of regions, for each:>> <<2a. currentCells _ ExtendRegionToCells[i, currentRegion, cad]; newAdjacencies _ NIL;>> <> <<2b. Do this step only if i = 2 or 3. If dimension of currentRegion < i-1, then determine adjacent regions of larger dimension. Sort these into order of increasing dimension. Go down this list, and for each region on it, find all cell-cell adjacencies between currentRegion and this region. Sort these adjacencies into decreasing sum of cell dimensions. For the next such adjacency, newAdjacencies _ AdjacenciesOverAdjacency[i, adjacency, cad]. If newAdjacencies = NIL, i.e. if needed auxiliary E^(i-1) cell-cell adjacencies, or non-NIL sample points, cannot be found, then go to the next cell-cell adjacency between current region and this region. If needed auxiliary adjacencies and/or non-NIL sample points cannot be found for any cell-cell adjacency between current region and this region, give up on building adjacencies in E^i between stacks over current region and this region. >> <> <<2c. Insert cells of currentCells into cad.cells in lexicographical order. IF newAdjacencies # NIL, then enter its adjacencies into the appropriate cells of cad.cells. >> <<3. If i-space cad.localizationFormula # NIL, then delete all cells of cad.cells which don't satisfy it, and all adjacencies involving those cells .>> <<4. For i = 1, 2 or 3, if no localization, we now have a graph for the cad of E^i in which a maximal signed regions computation will yield (signed) components (in 1 and 2-space, we can have all adjacencies, in 3-space, probably only a proper subset of all adjacencies.) >> ExtendRegionToCells: PROC [dimension: CARDINAL, region: SignedRegion, cad: Cad] RETURNS [newCells: SEQ.Sequence]; <> <> <<(Let i = dimension). Method: Evaluate polys at base sample point, irreducible basis of algebraic polys, isolate roots, construct extended sample points, eval gsfd of i-variate polynomial at endpoints of isolating interval, or i-variate polynomial itself at easy primitive sector sample point, when we want its sign.>> ExtendCellToStacks: PROC [i: CARDINAL, cell: Cells.Cell, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; <> ExtendStacksToStacks: PROC [i: CARDINAL, StacksInEiM1: SEQ.Sequence, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; <> <> <> END.