QECadStructure.mesa
Last Edited by: Arnon, October 8, 1986 11:38:33 am PDT
DIRECTORY
Rope,
IO,
AlgebraClasses,
BigRats,
RatIntervals,
VariableSequences,
Polynomials,
AlgebraicNumbers,
Sequences,
Formulas,
SamplePoints,
CoveringSets,
Cells;
QECadStructure: CEDAR DEFINITIONS
~ BEGIN OPEN AC: AlgebraClasses, BR: BigRats, RI: RatIntervals, AN: AlgebraicNumbers, SEQ: Sequences, POL: Polynomials, QFF: Formulas, SP: SamplePoints, CS: CoveringSets;
Cad Representation
Cad: TYPE = AC.Object;
CadData: TYPE = REF CadDataRec;
CadDataRec: TYPE = RECORD [
dimension: CARDINAL, -- Define r = dimension
givenInputPolynomials: SEQ.Sequence, -- r-variate polynomials in inputVariables
localizationFormula: QFF.Formula ← NIL, -- involving r-variate polynomials in inputVariables
inputPolynomials: SEQ.Sequence, -- givenInputPolynomials + localizationFormula polynomials; localizationFormula = NIL => inputPolynomials = givenInputPolynomials. Initial subsequence assumed to be Contents[parentCad.inputPolynomials], to facilitate computation of inputSignatures for Cells of parentCad
basis: SEQ.Sequence, -- finest squarefree basis
inputPolynomialFactorizations: SEQ.Sequence, -- of CompleteFactorization's, in 1-1 correspondence with inputPolynomials
basisIndividualProjections: SEQ.Sequence, -- of OnePolynomialProjection's; dimension = 1 => NIL. Need not be in same order as basis.
basisPairwiseProjections: SEQ.Sequence, -- of TwoPolynomialProjection's; dimension = 1 => NIL
minPolyVariable: VariableSequences.VariableSequence,
cells: SEQ.Sequence ← NIL, -- of cells, in lexicographic order (for binary searching)
inducedCad: Cad ← NIL, -- dimension = 1 => NIL
parentCad: Cad ← NIL -- if any
signatures: LIST OF SIGNATURES
primaryPolynomials: SEQ.Sequence ← NIL, -- irreducible (<= r)-variate rational polynomials, all of which occur in the bases of some (possibly 0th) induced cad (and hence are invariant on all cells of the r-space cad), whose signs on each cell constitute its primarySignature
In other words, the polynomials in primaryPolynomials may be in different numbers of vars. Poly eval routines are assumed to be able to cope with this, i.e. if asked to eval a poly in i variables at a point with i+j coordinates, will use first i coordinates.
secondaryPolynomials: SEQ.Sequence ← NIL, -- same specs as primaryPolynomials, signs on each cell constitute its secondarySignature. Typically a superset of primaryPolynomials.
projectionType: ProjectionType, -- dimension = 1 => projectionType = none
abstractGraph: Graphs.Graph ← nullGraph,
basisClusters: SEQ.Sequence ← NIL, -- of SignedRegions
otherClusters: SEQ.Sequence ← NIL, -- of SignedRegions
statistics: CadStatisticsRec, -- to be added later
];
ProjectionType: TYPE = QEProjectionStructure.ProjectionType;
Adjacency: TYPE = RECORD[
lowerDimCell, higherDimCell: Cells.Cell
];
SignedRegion: TYPE = REF;
Stack: TYPE = REF;
Instance Data for Cad Structures
CadStructureData: TYPE = REF CadStructureDataRec;
CadStructureDataRec: TYPE = RECORD [
samplePointVariable: Variables.Variable, -- = variable of appropriate Sample Point Structure, i.e. variable in terms of which the minimal polynomials of sample point primitive elements will be expressed, and so also SamplePoint coordinates
polynomialRing: AC.Object -- for the input polynomials and the polynomials occurring in cell defining formulas. Length[allVariables] of this polynomial ring = ambientSpaceDimension of cell = ambientSpaceDimension of appropriate Covering Set Structure = dimension of appropriate Sample Point Structure.
];
Cad Structure Ops
MakeCadStructure: AC.TrueNullaryOp;
PrintName: AC.ToRopeOp;
ShortPrintName: AC.ToRopeOp;
IsCadStructure: AC.UnaryPredicate;
Conversion and IO
Recast: AC.BinaryOp;
CanRecast: AC.BinaryPredicate;
ToExpr: AC.ToExprOp;
LegalFirstChar: AC.LegalFirstCharOp;
Read: AC.ReadOp;
FromRope: AC.FromRopeOp;
ToRope: AC.ToRopeOp;
Write: AC.WriteOp;
Selectors
Dimension: AC.UnaryOp;
InputPolynomials: AC.UnaryOp;
MinPolyVariable: AC.UnaryOp;
Basis: AC.UnaryOp;
Contents: AC.UnaryOp; -- If r = 1, then returns empty Sequence
BasisProjection: AC.UnaryOp; -- If r = 1, then returns empty Sequence. Otherwise returns a Sequence of polynomials obtained from basisIndividualProjections and basisPairwiseProjections
CadCells: AC.UnaryOp;
InducedCad: AC.UnaryOp;
ParentCad: AC.UnaryOp;
BasisClusters: AC.UnaryOp;
OtherClusters: AC.UnaryOp;
Operations
LookupCell: AC.BinaryOp;
Args are a Sequence of Cells and a Cell Index
ReadCoveringSets: PROC [in: IO.STREAM, cad: Cads.Cad];
Read a covering set file, and for each cell in the cad, hang its covering set off it.
CoveringSetsFromLinearRope: AC.BinaryInPlaceOp;
CellsWithSignature: AC.BinaryOp;
Find all cells having a given signature. Need to be able to specify whether we mean basis signature or input polynomial signature.
Cluster: AC.BinaryOp; -- extract the clusters of a cad. Need to be able to specify whether we mean basis signature or input polynomial signature.
END.