SignatureTable Representation
SignatureTable: TYPE = AlgebraClasses.Object;
SignatureTableData: TYPE = LIST OF SignatureTableEntry;
SignatureTableEntryRec:
TYPE =
RECORD[
signature: Signature,
clustersWithThisSignature: LIST OF Clusters.Cluster -- each of which has this signature
];
Obvious consistency requirement: the signatures of the entries of a SignatureTable are all with respect to the same set of signature polynomials.
SacCad.tioga routines
MakeSignatureTable:
PROC;
Get CurrentDimension, get CurrentDimClusters, make table in obvious way and set InSignatureTable to it.
DisambiguateSignatureTable:
PROC;
Get table from InSignatureTable;
While there is an ambiguous entry (i.e. some of its clusters are in the solution set, some not) in table, do the following:
1. Select some basis polynomial F (in any dimension) that is not currently a signature polynomial. Initialize newTable ← NIL;
2. For each current table entry E, create between 1 and 3 new table entries by calling RefineSignatureTableEntryByPolynomial[E, F], add to newTable.
3. Set table ← newTable;
Set OutSignatureTable to table.
RefineSignatureTableEntryByPolynomial:
PROC [
E: SignatureTableEntry,
F: Polynomial]
RETURNS [
LIST
OF SignatureTableEntry];
Initializes lists Pos, Zero, Neg to NIL, looks up F in bases to get (i, j) reference to it (jth element of i-dimensional basis), for each cluster C of E, sets [neg, zero, pos] ← RefineClusterByPolynomial[C, (i, j)], adds whichever of neg, zero, pos nonNIL to appropriate list. When done, for each of Pos, Zero, Neg which is nonempty, creates a new SignatureTableEntry with appropriate signature, adds to return list.
RefineClusterByPolynomial:
PROC [
C: Cluster, (i, j): RefToBasisElement]
RETURNS [negativeSign, zeroSign, positiveSign: Cluster];
For each constituent cell c, applies GetCellSignAtBasisElement[c, (i, j)], adds c to whichever of pos, zero, or neg lists is appropriate. When done, for each of the three lists, if nonempty, makes a new cluster (picks rep cell, new PolynomialSequenceFile of augmented signature polynomials, augmented signature, same value of truthValue, list of constituent cells, appropriate intracluster adjacencies), and returns it as the appropriate output, else returns NIL for that output.
GetCellSignAtBasisElement:
PROC [c: Cell, (i, j): RefToBasisElement]
RETURNS [Sign];
c is cell in r >= i space, (i, j) is a reference to (jth element of i-dimensional basis), looks into stack file for rep cell e of i-space cluster containing i-space cell d induced by c (how do we know in what file to find that cluster?), and returns jth element of e's basis signature
ExtractSolutionSignatures:
PROC [
T: SignatureTable]
RETURNS [solutionSignatures, dontOccur:
LIST
OF Signature];
T is assumed to be a disambiguated SignatureTable. solutionSignatures is a list of the signatures whose clusters are all in the solution set. dontOccur is signatures which don't occur at all.
SimplifySignatures:
PROC [
LIST
OF Signature]
RETURNS [
LIST
OF Signature];
Sort into lexicographical order and combine.
SignaturesToFormula:
PROC [
LIST
OF Signature]
RETURNS [Formula];
Convert to a formula.
MakeSolutionFormula:
PROC;
MakeSignatureTable, DisambiguateSignatureTable, [solutionSignatures, dontOccur] ← ExtractSolutionSignatures, S ← SimplifySignatures[CONC[solutionSignatures, dontOccur]]; Phi ← SignaturesToFormula[S]; Set environment variable SolutionFormula to Phi.
QE.mesa routines
DisambiguateSignatureTable:
PROC [inTable:
QET.SignatureTable]
RETURNS [outTable:
QET.SignatureTable];
Assume that initially inTable.polynomials ← inTable.cad.primaryPolynomials.
outTable ← copy(inTable).
While there is an ambiguous entry in outTable, do for each such ambiguous entry:
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];
First determine signatures which do not occur, and use them when helpful.
Sort into lexicographical order and combine.
SignatureSeqToFormula:
PROC [
QET.SignatureSeq]
RETURNS [
QFF.QFFormula];
Convert to a formula.