[Indigo]<CaminoReal>Cads.mesa!1

Cads.mesa

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

DIRECTORY

Rope,

IO,

Graphs,

GraphOps,

AlgebraClasses,

BigRats,

Variables,

Polynomials,

Formulas,

QETypes,

QEIO;

Cads: CEDAR DEFINITIONS

IMPORTS

~ BEGIN OPEN AC: AlgebraClasses, BR: BigRats, VARS: Variables, POL: Polynomials, QFF: Formulas, QET: QETypes, QEIO;

Types

Adjacency: TYPE = RECORD[

lowerDimCell, higherDimCell: QET.Cell

];

Main Algorithm

BuildCad: PROC [inputPolynomials: POL.PolynomialSeq, minPolyVariable: VARS.VariableSeq, localizationFormula: QFF.Formula ← NIL] RETURNS [cad: QET.Cad];

Projection Phase

CoarsestSqFreeBasis: PROC [inputPolynomials: POL.PolynomialSeq, localizationFormula: QFF.Formula ← NIL] RETURNS [contents, basis: POL.PolynomialSeq];

Projection: PROC [basis: POL.PolynomialSeq] RETURNS [basisProjection: POL.PolynomialSeq];

Base Phase

BasePhase: PROC [cad: QET.Cad];

cad is of r>=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.

Adjacencies and Clusters

ExtractClusters: PROC [cad: QET.Cad, numComponents: CARDINAL] RETURNS [clusters: QET.SignedRegionSeq];

components assumed to be of cad, and not some induced cad thereof.

MaximalSignedRegions: PROC [dimension: CARDINAL, cad: QET.Cad, primary: BOOL];

Depth-First Search connected components computation in the dimension-space cad graph, filling in the (IF primary THEN primaryRegion ELSE secondaryRegion) fields of cells.

ExtractSignedRegions: PROC [dimension: CARDINAL, cad: QET.Cad, primary: BOOL] RETURNS [QET.SignedRegionSeq];

Extract from the dimension-space cad graph, the (IF primary THEN primaryRegion ELSE secondaryRegion) cell-field-defined regions.

AdjacenciesOverAdjacency: PROC [dimension: CARDINAL, adjacency: Adjacency, cad: QET.Cad] RETURNS [newAdjacencies: LIST OF Adjacency];

For i = 2 or 3 only, returns all interstack adjacencies in i-space over an adjacency in dimension-1 space. cad is i-space cad. newAdjacencies = NIL if no adjacencies in dimension space can be built, either because needed auxiliary E^(i-1) cell-cell adjacencies, or non-NIL sample points, cannot be found.

Converts extended to primitive sample points as needed.

May build adjacencies over appropriate auxiliary E^(i-1) cell-cell adjacencies if necessary, and/or query i-space cad for existing adjacency information.

Extension Phase

RegionExtendCadToCad: PROC [cad: QET.Cad];

Extend cad of dimension-1 space to dimension space, using the largest signed regions (wrt primarySignatures) that can be constructed in the graph for dimension-1 space.

Let i = dimension.

Assume that in E^(i-1), with primaryPolynomials ← CompleteFactors(inputPolynomials), primarySignatures of cells are set.

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;

If currentRegion is a 0-cell, then as each element of (trivariate) basis is evaluated at sample point, check for identically zero; if so, then add that basis element to identicallyZeroBasisElements field of the 0-cell. If identicallyZeroBasisElements#NIL when all basis elements have been evaluated, i.e. if this is a degenerate 0-cell, then do the extra work required to determine the elements of the stack over this cell (RES sets, etc.), otherwise just isolate the roots of the algebraic basis of evaluated (trivariate integral) basis.

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.

Note that there is no need to worry about whether regions have the boundary property; Note the specification that we try to find an adjacency (that we can build adjacencies over) between each pair of adjacent regions; the lower dimensional cell in such an adjacency necessarily belongs to the portion of the lower dimensional region contained in the boundary of the larger dimensional 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: QET.SignedRegion, cad: QET.Cad] RETURNS [newCells: QET.CellSeq];

Extend region in dimension-1 space to cells in dimension-space. cad is dimension-space cad.

Fill in basisSignatures, and, if desired, (with primaryPolynomials ← CompleteFactors(inputPolynomials)), primarySignatures, of newCells. Also fill in induced adjacencies, and intrastack adjacencies, among newCells.

(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: QET.Cell, cad: QET.Cad] RETURNS [StacksInEi: QET.StackSeq];

Return a StackSeq of length one consisting of the stack over cell in E^(i-1).

ExtendStacksToStacks: PROC [i: CARDINAL, StacksInEiM1: QET.StackSeq, cad: QET.Cad] RETURNS [StacksInEi: QET.StackSeq];

StacksInEi returned in lexicographical order by base

RatApproxSamplePoint: PROC [cell: QET.Cell, ratApproxBound: BR.BigRat] RETURNS [PTS.Point];

Return a rational approximation to cell sample point, each coordinate accurate to within ratApproxBound. Should have the property that always produces the same RatPoint for given RealFieldPoint and ratApproxBound inputs.

END.