<> <> AlgebraStructures Cad Facilities Dennis Arnon © Copyright 1986 Xerox Corporation. All rights reserved. 3. Cad implementation 3.1. New operations Request for any AlgebraicSurfaces display op starts up the tool if not already started. Or have it running all the time, and each display request creates a new surfaceDisplay viewer. AlgebraClasses has proc to add an op to a structures property list. Or MakeSequenceStructure proc takes procs to add to prop list as args. Cad ops induced cad Alternate display showTriangulationAll (valid only for cad's of 1-, 2- and 3-space) showTriangulationSections showTriangulation0Cells showTriangulation1Cells showTriangulation2Cells rayTraceInputPolynomials (valid only for cad's of 3-space) show cells show statistics Cad's should have names, statistics Store only basis signatures with cells. Both clustering during cad construction, and clustering for disambiguation of signatures, are done with basis signatures (if basis signatures with ordinary projections don't suffice to get unambiguous clusters, then we have to go back and refine cad with respect to augmented projections). Cluster ops select containing cad rayTrace (valid only for 2-cluster in 3-space) showTriangulation (valid only for clusters in cad's of 1-, 2- and 3-space) Cell ops select containing cad rayTrace (valid only for 2-section in 3-space) showTriangulation (valid only for cells in cad's of 1-, 2- and 3-space) Polynomial sequence ops, for base coeffs that are ints or bigrats rayTraceZeros (valid only 3-variate polys) decomposeZeros (forks Vax computation; pop up menu for options (including covering set parameters); inserts cad in Active MessageSet) showZerosTriangulation (valid only for 1-, 2- and 3-variate polys) New Polynomial ops, for base coeffs that are ints or bigrats rayTrace (valid only for 3-variate poly) decomposeZeros (forks Vax computation; pop up menu for options (including covering set parameters); inserts cad in Active MessageSet) showZeroTriangulation (valid only for 1-, 2- and 3-variate poly) Sequences Basic display is one line: "sequence of n shortPNames" Alternate display: Slider bar onto popup menu popup menu entries are shortPNames of sequence elements Insert creates a blank entry in popup menu; then select item to be inserted as an operand, it is type checked, inserted. Delete modifies pop up menu Selection of Insert or Delete forces Alternate display 3.2. Adjacencies and Clusters, Graph ops, read adjacencies, compute clusters We have made a basic decision to go with basis signatures. First step is the current "cells with signature" op. This assumes that every cell in the cad has a basis signature, then this is a binary op that takes a legal (i.e. correct length) basis signature (perhaps with * elements) and returns a sequence of cells with that sig. Subr for boundary of 2-sector (i, j) in E2 I3=lelt(I,3); I2=lelt(I,2); Pass I#, I3, and I2 to a routine For each 2-sector (i, j, k) in I# Subr for boundary of 2-sector (i, j) in E2: L1 _ U1 _ 0; L1L _ L1R _ U1L _ U1R _ 0; for each 1-cell (a,b) adjacent to 2-sector (i, j) if a = i then if b = j-1 then L1 _ j-1 else if b = j+1 then U1 _ j+1 else ERROR; if L1#0 then for each 0-cell (a,b) adjacent to 1-section (i, L1) if a = i-1 then L1L _ b else if a = i+1 then L1R _ b else ERROR; if U1#0 then for each 0-cell (a,b) adjacent to 1-section (i, U1) if a = i-1 then U1L _ b else if a = i+1 then U1R _ b else ERROR; Return[ LIST(L1, LIST(L1L, L1R), U1, LIST(U1L, U1R) ) ]. 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]; <> <> <> 3.3. Cad statistics records SmartInfo about the cad (0-cell bounding box, singularities, turning points). 3.4. New cell Ops: read covering set, display covering set 3.5. AlgebraStructures Rootfinder, new cell op: generate covering set 3.6. Compute and add adjacencies to an existing cad in Cedar Do we want to separate adjacency computation from cad computation? If so, set up a SAC-2 routine to do it; allow ComputeServer to queue up a succession of jobs, to be done in background. Step two: implement the computation in Cedar. 2D case first. 3.7. Cad databases Reading such files is slow. Need command to read some more cells of this cad and add them to the database. Cypress database? Once have distributed computations, we want to be able to do incremental updates of the database. <<3.8. RefineCad operation (Real algebraic variety Combiner)>> This is a great example for implementing cad computation related stuff in Cedar by forking off appropriate subcommands to remote SAC-2 systems. RefineCad: PROC [inCad: Cad, refiningPoly: Polynomial, cellsToRefine: Sequence] RETURNS [outCad: Cad]; <> <> <<3.9. Projection Phase>> 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. >> <<3.10. Base Phase>> 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.>> <<3.11. Extension Phase>> <> <> <> <> 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.>> <> <> <> <> <> <<];>> ExtendCellToStack: PROC [cell: Cells.Cell, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; <> ExtendStacksToStacks: PROC [i: CARDINAL, StacksInEiM1: SEQ.Sequence, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; <> <> <> 3.12. QE phase <> <> <> <> <> <> <> <<];>> MakeQEProblem: PROC [inputFormula: QFF.Formula, localizationFormula: QFF.QFFormula, inputVariables: VARS.VariableSeq, minPolyVariable: VARS.VariableSeq _ AN.defaultMinPolyVariable, fieldElementVariable: VARS.VariableSeq _ RF.defaultFieldElementVariable] RETURNS [QET.QEProblem]; EliminateQuantifiers: PROC [QET.QEProblem]; <<1. Extract polynomials of formula and localizationFormula; cad _ ProjectionPhase[polynomials, inputVariables, localizationFormula]. >> <<2. Cad.BasePhase[cad];>> <<3. For i in [2,...,k] do Cad.RegionExtendCadToCad[i, cad].>> <<4. Cad.MaximalSignedRegions[k, cad, TRUE]; regions _ Cad.ExtractSignedRegions[k, cad, TRUE]; Sort regions into order of decreasing dimension (for k = 3, put degenerate 0-dimensional regions after nondegenerate), since qe for larger dimensional regions should go faster, since they are likely to have lower degree sample points.>> <<5. For each region of regions, using representative cell = cellInEk (which has extended or primitive sample point), do:>> <<5.1 StacksInEk+1 _ Cad.ExtendCellToStacks[k+1, cellInEk, cad];>> <<5.2 For i in [k+2,...,r] do StacksInEi _ Cad.ExtendStacksToStacks[i, StacksInEiM1, cad].>> <<5.3. EliminateInnermostQuantifier[StacksInEr, formula]; >> <<5.4. For i decreasing in [k+1,...,r-1] do EliminateInnerQuantifier[i, StacksInEi, StacksInEiM1, formula]; >> <<5.5 If StacksInEk+1.baseTruthValue then insert this signed component into SignatureTable. >> <<6. DisambiguateSignatureTable, extract signatures corresponding to regions in solution set, bundle them up as a SignatureSeq>> <<7. Apply SimplifySignatureSeq; Return SignatureSeqToFormula and the final SignatureTable.>> <<>> EliminateInnermostQuantifier: PROC [StacksInEr: QET.StackSeq, formula: QFF.Formula]; <> <<>> EliminateInnerQuantifier: PROC [i: CARDINAL, StacksInEi, StacksInEiM1: QET.StackSeq, formula: QFF.Formula]; <> <<>> 3.13. Simplifier The basic strategy is to assume cells in r-space invariant with respect to bases in all dimensions. No effort to separate complete factors of input polynomials from factors of projection polynomials. If we have unambiguous signatures at this point, i.e. if for each signature, either every cluster with that signature is in solution set, or no cluster with that signature is in solution set, then we just have to simplify. If not, we have to refine the cad with respect to augmented projections and get clusters invariant with respect to these new larger bases in each dimension. Having done this we know we'll get unambiguous clusters. <> <> <> <> <> <> <<];>> <> <> <> <> <> <<];>> DisambiguateSignatureTable: PROC [inTable: QET.SignatureTable] RETURNS [outTable: QET.SignatureTable]; <> <> <> <<1. Select some polynomial P from the basis of some (proper) induced cad, such that P is not an element of outTable.polynomials (use hashing).>> <<2. Augment the secondarySignature's of all cells of all regions of this entry by sign(P).>> <<3. For each region of this entry, form the subgraph it induces, and construct signed components in this subgraph wrt secondarySignature.>> <<4. Collect the cumulative data: if the sign(s) of P on all newly formed components which are contained in the solution set differ from the sign(s) of P on all newly formed components which are external to the solution set, then we have succeeded in disambiguating this entry with P.>> <<5. Delete this entry, and create two new appropriate unambiguous entries, with appropriately augmented signatures.>> <<6. For all unambiguous entries, augment their signatures with "don't care" in the P position, and augment appropriately (i.e. with the correct P sign) the secondarySignature's of all constituent cells of all entry regions.>> <<7. For each ambiguous entry, carry out steps 2,3,4, and see if we have succeeding in disambiguating that entry with P. If so, then carry out step 5 for this entry. If not, then split this entry into up to three or more (each of which may be ambiguous or unambiguous, but at least one of which must be ambiguous if we are here) entries, corresponding to splitting each of the prior entry regions into up to three or more new regions by the sign of P.>> SimplifySignatureSeq: PROC [QET.SignatureSeq] RETURNS [QET.SignatureSeq]; <> <> SignatureSeqToFormula: PROC [QET.SignatureSeq] RETURNS [QFF.QFFormula]; <> <<3.14. CadCoodTransform>> Actually is an op on a set of polys so that we end up with a decomposition which is cylindrical with respect to two coordinate systems. 3.15. Application of Cedar cad algorithm 1. Demonstrate topologically reliable display of algebraic and parametric curves and surfaces, and display of fat plane and space curves. 2. Application of distributed cad algorithm to qe problems involving roots of quartic polynomials (full Kahan ellipse, root configuration-coefficient classification for quartics) 3. Study of parametric curves and surfaces: spline analyzer, spline combiner. 3.16. Expert system for directing problem solving by cad computation Has the knowledge base of info about root configuration from evaluation of coefficients. Tries heuristics, e.g. detecting common zeros by Grobner basis computation. Knows what computations to do to build a sufficient database for solving the qe or decision problem.