SignatureTables.mesa
Last Edited by: Arnon, March 5, 1986 10:49:31 am PST
SignatureTables
DIRECTORY
Rope,
Basics,
IO,
MathExpr,
AlgebraClasses,
Variables,
VariableSequences,
DistribPolys;
SignatureTables: CEDAR DEFINITIONS
~ BEGIN
SignatureTable Representation
SignatureTable: TYPE = AlgebraClasses.Object;
SignatureTableData: TYPE = LIST OF SignatureTableEntry;
SignatureTableEntryRec: TYPE = RECORD[
signature: Signature,
clustersWithThisSignature: LIST OF 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.
Instance Data for SignatureTable Rings
SignatureTableRingData: TYPE = REF SignatureTableRingDataRec;
SignatureTableRingDataRec: TYPE = RECORD [
coeffRing: AlgebraClasses.Object,
variable: Variables.Variable, -- main variable
baseCoeffRing: AlgebraClasses.Object, -- not a polynomialStructure
allVariables: VariableSequences.VariableSequence -- cumulative variables over baseCoeffRing
];
SignatureTable Structure Ops
MakeSignatureTableStructure: AlgebraClasses.SignatureTableStructureConstructor;
A particular polynomial structure is defined by its coeffRing and its variables.
coeffRing can be a ring, field, algebra, or divisionAlgebra.
variableSeq is a sequence of any length, and the right thing happens.
PrintName: AlgebraClasses.PrintNameProc;
ShortPrintName: AlgebraClasses.PrintNameProc;
CoeffRing: AlgebraClasses.UnaryOp;
Variable: AlgebraClasses.UnaryOp;
BaseCoeffRing: AlgebraClasses.UnaryOp;
AllVariables: AlgebraClasses.UnaryOp;
Characteristic: AlgebraClasses.StructureRankOp;
IsSignatureTableStructure: AlgebraClasses.UnaryPredicate;
Conversion and IO
Recast: AlgebraClasses.BinaryOp;
CanRecast: AlgebraClasses.BinaryPredicate;
ToExpr: AlgebraClasses.ToExprOp;
LegalFirstChar: AlgebraClasses.LegalFirstCharOp;
Read: AlgebraClasses.ReadOp;
FromRope: AlgebraClasses.FromRopeOp;
ToRope: AlgebraClasses.ToRopeOp;
Write: AlgebraClasses.WriteOp;
PolyToRope: PROC [in: SignatureTable, termRope: Rope.ROPENIL] RETURNS [out: Rope.ROPE];
Provides for specification of a termRope.
WritePoly: PROC [in: SignatureTable, out: IO.STREAM, termRope: Rope.ROPENIL];
Provides for a termRope, and encloses poly in newlines.
PolyFromDPoly: PROC [in: DP.DSignatureTable, polynomialRing: AlgebraClasses.Object] RETURNS [out: SignatureTable];
DPolyFromPoly: PROC [in: SignatureTable] RETURNS [out: DP.DSignatureTable];
Constructors
Monomial: AlgebraClasses.BinaryImbedOp;
data1 = coeff, data2 = REF exp. Returns coeff * var ^ exp.
Selectors
LeadingCoefficient: AlgebraClasses.UnaryOp;
Leading coeff of the recursive form of this poly. Returns zero[coeffRing] for zero poly.
Degree: AlgebraClasses.ElementRankOp;
Degree in main variable. Degree[ZeroPoly] = 0.
Reductum: AlgebraClasses.UnaryOp;
Reductum of the recursive form of this poly. Reductum[ZeroPoly] = ZeroPoly.
Arithmetic
Zero: AlgebraClasses.NullaryOp;
One: AlgebraClasses.NullaryOp;
Add: AlgebraClasses.BinaryOp;
Negate: AlgebraClasses.UnaryOp;
Subtract: AlgebraClasses.BinaryOp;
Multiply: AlgebraClasses.BinaryOp;
Power: AlgebraClasses.BinaryOp;
Differentiate: AlgebraClasses.BinaryOp;
Simple or partial differentiation. firstArg is polynomial, secondArg is variable. firstArg is reordered to make secondArg its main variable, then partially differentiated, then result reordered back to original firstArg Structure.
IndefIntegrate: AlgebraClasses.BinaryOp;
Indefinite integration. firstArg is polynomial, secondArg is variable. firstArg is reordered to make secondArg its main variable, then integrated, then result reordered back to original firstArg Structure.
MainVarEval: AlgebraClasses.BinaryOp;
MainVarEval the (main) variable of in at an element of the coeffRing of in. Horner's method used.
AllVarEval: AlgebraClasses.BinaryOp;
Evaluate all variables of in at a point over the baseCoeffRing of in.
Subst: AlgebraClasses.BinaryOp;
Substitute at for the (main) variable of in. in and at belong to the same polynomial ring. Horner's method used.
DegreeDelta: PROC [terms: LIST OF Term] RETURNS [CARDINAL];
Difference between the degrees of successive terms of terms. If terms of length one, returns the degree of the unique term. If terms = NIL, returns zero.
SylvesterMatrix: AlgebraClasses.BinaryOp;
Sylvester matrix
Resultant: AlgebraClasses.BinaryOp;
Resultant.
SignVars: AlgebraClasses.ElementRankOp;
Number of sign variations in the sequence of a (recursively, if actually multivariate) univariate polynomial's coefficients. Obviously coefficients must belong to an ordered structure.
Reverse: AlgebraClasses.UnaryOp;
Reverse the coefficients of a polynoimila.
Content: AlgebraClasses.UnaryOp;
PrimitivePart: AlgebraClasses.UnaryOp;
PseudoDivide: AlgebraClasses.BinaryToPairOp;
PROC [dividend, divisor: SignatureTable] RETURNS [quotient, remainder: SignatureTable];
This is a method for polys over a ring.
TrialDivide: AlgebraClasses.BinaryToPairOp;
PROC [dividend, divisor: SignatureTable] RETURNS [quotient, remainder: SignatureTable];
quotient ← remainder ← NIL if fails, i.e. if ~Exists Q, R, such that A = B*Q + R.
This is a method for polys over a ring.
Divide: AlgebraClasses.BinaryToPairOp;
PROC [dividend, divisor: SignatureTable] RETURNS [quotient, remainder: SignatureTable];
This is a method only for polys over a field, i.e. assumed that it won't fail, i.e. can divide in the coefficient domain without checking first.
Remainder: AlgebraClasses.BinaryOp;
This is a method only for polys over a field, i.e. assumed that it won't fail, i.e. can divide in the coefficient domain without checking first.
ExactQuotient: AlgebraClasses.BinaryOp;
Returns NIL if secondArg does not divide firstArg exactly, i.e. if Divide either fails, or returns nonzero remainder.
GCD: AlgebraClasses.BinaryOp;
GreatestSqFreeDivisor: AlgebraClasses.UnaryOp;
A simple-minded algorithm based on division algorithm, possibly on pseudo-division. If the former, fails if division algorithm does.
Intended mainly for univariate polynomials over a field.
Comparison
Equal: AlgebraClasses.EqualityOp;
IsZero: AlgebraClasses.UnaryPredicate;
Sign: AlgebraClasses.CompareToZeroOp;
Sign of the leading base coefficient.
Abs: AlgebraClasses.UnaryOp;
Compare: AlgebraClasses.BinaryCompareOp;
Utility
NewMainVariable: AlgebraClasses.BinaryOp;
firstArg is polynomial, secondArg is a Variable that may or may not occur in firstArg's allVariables. result is firstArg with reordered variables so that secondArg is new main variable. Order of other variables is preserved
END.