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
Main Algorithms
DoProjection:
PROC;
Get cadInputData: CadInputFile from environment variable CadInputData. Write cadProjData: CadProjectionData to a CadProjectionFile, and set CadProjectionData environment variable to it.
DoBase:
PROC;
Gets cadProjData: CadProjectionFile from CadProjectionData environment variable.
Writes out baseCad: Stack as a StackFile; does not set any environment variable to it.
Writes out a ClusterFile that is a list of all the maximal (singleton) 1-space clusters and sets CurrentDimClusters environment variable to it.
If NOT CadType = NoAdjacencies, then writes out an AdjacencyFile of all the obvious adjacencies in 1-space and sets CurrentDimAdjacenciesToExtend environment variable to it.
ApplyLocalizationFormula:
PROC;
Get cadInputData: CadInputFile from environment variable CadInputData, get localizationFormula. Get clusters: ClusterFile from CurrentDimClusters environment variable. Write new ClusterFile that is clusters minus clusters that do not satisfy localizationFormula, and set CurrentDimClusters environment variable to it.
Also remove cells of deleted clusters from adjacency lists, if there are any.
ExtensionInitialization:
PROC;
Increments CurrentDimension environment variable. Sets LowerDimClusters ← CurrentDimClusters, CurrentDimClusters ← NIL, LowerDimAdjacenciesToExtend ← CurrentDimAdjacenciesToExtend, CurrentDimAdjacenciesToExtend ← NIL.
UnLocalizeCad:
PROC[LBDBHandle: ??]
RETURNS[LBDBHandle: ??];
Fill out an existing localized cad, i.e. construct everything that NewCad would have with no localizationFormula, i.e. fill in what the localizationFormula caused to be omitted.
ExtractSubCad:
PROC[subsetPolynomials: AlgebraClasses.Object, LBDBHandle: ??]
RETURNS[LBDBHandle: ??];
LBDBHandle names an existing cad, which must be unlocalized, for which subsetPolynomials are a subset of the effectiveInputPolynomials. E
RefineCadByAugProj:
PROC[LBDBHandle: ??]
RETURNS[LBDBHandle: ??];
Take a cad built by projections only; compute the augmented projections, and refine the cad by them.
RefineCad:
PROC[newPolynomials: AlgebraClasses.Object, LBDBHandle: ??, newLocalizationFormula: Formula ←
NIL]
RETURNS[LBDBHandle: ??];
LBDBHandle is the handle for an existing, fully constructed cad which is to be refined. newPolynomials are a Sequence of Polynomials with integer, rational, or real algebraic number field coefficients. In the latter case, it is assumed that all coefficients in all the polynomials are expressed as elements of the same field, i.e. have the same primitive element.
newPolynomials, and the input polynomials of the existing cad, must have exactly the same variables, but they need not have the same coefficient types.
RefineCad requires that the input (existing) cad be unlocalized; if this is not the case, UnLocalizeCad must be applied to it first. If newLocalizationFormula#NIL, the output (new) cad will be localized by it. Calling RefineCad with newPolynomials=NIL and a non—NIL newLocalizationFormula is one way to take localize an existing unlocalized cad.
Crucial, though perhaps fairly simple, tasks this guy can perform is to invoke AS routines to augment bases, refine root isolation lists, and augment signatures.
Basic specs. Redo the projection calcs, to get larger (integral) bases in each dimension as you go down. Get the isolation list for 1-space, refine it with the new 1-basis, determine how to output new 1-space clusters to the LB db, keep track of which ones are new. For the old 1-space clusters, refine their extensions by the new bivariate basis polynomials. For the new 1-space clusters, do new extensions of them by the new bivariate basis. Etc.
NewCad:
PROC[inputPolynomials: AlgebraClasses.Object, localizationFormula: Formula ←
NIL, buildAdjacencies:
BOOL ←
TRUE, pasteAdjacencies:
BOOL ←
TRUE]
RETURNS[LBDBHandle: ??];
inputPolynomials are a Sequence of Polynomials with integer, rational, or algebraic number field coefficients. In the latter case, it is assumed that all coefficients in all the polynomials are expressed as elements of the same field, i.e. have the same primitive element.
buildAdjacencies FALSE and pasteAdjacencies TRUE doesn't make sense.
localizationFormula assumed quantifier-free (for now).
NewCad "allocates" and hands back a LoganBerry DB into which the data for this cad have been written.
This guy manages the Sun engines. When it determines that one or more new computations can be forked, does rlogin or rexec to a selected Sun (perhaps assume that NewCad always running on one particular Dorado (thisMachine), so can be registered in YellowPages). All available Suns fire off an RPC packet every 5 seconds or so to thisMachine informing it of their load factors, so it can pick the best one to give the next job to.
basisSignatures in i-space are with respect to the i-variate basis; you follow pointers to baseCluster(s) to get signatures with respect to lower-dimensional basis.
inputSignatures in i-space are with respect to the i-variate actualInputPolynomials. Input polynomials in any dimension < r are CONT(A) U PROJ(B) of next higher dim polys; we assume that the CONT(A) polys occur first, and that CONT(A) is in one-one correspondence with A, so explicit constants occur for polys with constant content. Then in i-space, can get signatures of contents of each poly from actualInputPolynomial signatures in i-1 space, and we know i-basis signatures, then from divisibility info for each actual input poly in i-space (we assume contents carry sign info, i.e. contents are not necessarily positive), we can compute actualInputPolynomial signatures in i-space.
We assume a LBDB entry for each (non-deleted, if localized) cluster in i-space, but not necessarily for each cell. Queries for cells of the DB should be able to answer "there is no entry for that cell" (but there is a cell in the cad with that index), and "invalid index" (there is no cell in the cad with that index).
Re: localization - you should be able to delete any clusters from a cad, and extension and adjacency algorithms should be able to deal with that. Also, you should
DoProjection; -- the polynomials of the localization formula are added to the input polynomials.
Before doing each next projection, you should check global cad data to see whether this projection is a subset of any input polynomial set for which we have already built a cad. If so, then we should ExtractSubCad of it, rather than construct afresh. But note that we copy in such data; there are no pointers from one LBDB to another.
DoBase;
ApplyLocalizationFormula; -- done in Cedar. Clusters are not deleted from the LB DB, but rather are marked as deleted so will not be processed further.
For i𡤂,..., r do {
IF
NOT CadType = NoAdjacencies
THEN {
SelectAdjacenciesToExtendOver;
MarshallCurrentDimAdjacenciesForExtension;
};
MarshallCurrentDimClusters;
ExtensionInitialization;
InitialClustersOverClusterList;
IF NOT CadType = NoAdjacencies THEN BuildInterstackAdjacencies;
MarshallCurrentDimClusters;
IF CadType = PasteClusters
THEN {
MarshallCurrentDimAdjacenciesForPasting;
PasteClusters;
};
ApplyLocalizationFormula
}.
Adjacencies and Clusters
ExtractClusters:
PROC [cad: Cad, numComponents:
CARDINAL]
RETURNS [clusters:
SEQ.Sequence];
components assumed to be of cad, and not some induced cad thereof.
Components: Menus.MenuProc = {
User specifies polynomials with respect to which to cluster by (*,*,@,*,*,@) tuples (@ is new FormulaOperators.Op).
edgePredicate: GraphOps.EdgePredicate ~ {
cell1: QET.Cell ← NARROW[v.rep];
cell2: QET.Cell ← NARROW[w.rep];
RETURN[cell1.basisSignature.structure.class.equal[cell1.basisSignature, cell2.basisSignature] ];
};
inducedCad: QET.Cad ← QEIO.GetInducedCad[cad, dimension];
numComponents: CARDINAL ← GraphOps.DetermineComponents[cad.abstractGraph, Undirected, edgePredicate];
clusters: QET.SignedRegionSeq ← Cads.ExtractClusters[inducedCad, numComponents];
QEIO.WriteSignedRegionSeq[clusters, out];
};
MaximalSignedRegions: PROC [dimension: CARDINAL, cad: 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: Cad, primary: BOOL] RETURNS [SEQ.Sequence];
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: 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
Information to save to pass to adjacency algorithms:
E1 to E2: For each 0-cell in E1: isolating intervals (perhaps expanded to be strictly open) and corresponding algebraic basis elements over it; for each element F of integral bivariate basis, a sequence of length m of positive integers, such that F has m real roots over it, and ith element of sequence is section (or element) of overall stack which is ith real root of F.
Use this list to modify cell indices of section-section adjacencies produced by adjacency algorithms.
E2 to E3: For each 0-cell and 1-cell in E2: isolating intervals (perhaps expanded to be strictly open) and corresponding algebraic basis elements over it; for each element F of integral trivariate basis, a sequence of length m of positive integers, such that F has m real roots over it, and ith element of sequence is section of overall stack which is ith real root of F.
RegionExtendCadToCad:
PROC [cad: 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: SignedRegion, cad: Cad]
RETURNS [newCells:
SEQ.Sequence];
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: Cells.Cell, cad: Cad]
RETURNS [StacksInEi:
SEQ.Sequence];
Return a StackSeq of length one consisting of the stack over cell in E^(i-1).
ExtendStacksToStacks:
PROC [i:
CARDINAL, StacksInEiM1:
SEQ.Sequence, cad: Cad]
RETURNS [StacksInEi:
SEQ.Sequence];
StacksInEi returned in lexicographical order by base
RatApproxSamplePoint: PROC [cell: Cells.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.