DIRECTORY Rope, Basics, IO, MathExpr, AlgebraClasses, Variables, VariableSequences, DistribPolys; SignatureTables: CEDAR DEFINITIONS ~ BEGIN SignatureTable: TYPE = AlgebraClasses.Object; SignatureTableData: TYPE = LIST OF Term; Term: TYPE = REF TermRec; TermRec: TYPE = RECORD [ exponent: CARDINAL, coefficient: AlgebraClasses.Object ]; 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 ]; MakeSignatureTableStructure: AlgebraClasses.SignatureTableStructureConstructor; PrintName: AlgebraClasses.PrintNameProc; ShortPrintName: AlgebraClasses.PrintNameProc; CoeffRing: AlgebraClasses.UnaryOp; Variable: AlgebraClasses.UnaryOp; BaseCoeffRing: AlgebraClasses.UnaryOp; AllVariables: AlgebraClasses.UnaryOp; Characteristic: AlgebraClasses.StructureRankOp; IsSignatureTableStructure: AlgebraClasses.UnaryPredicate; 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.ROPE _ NIL] RETURNS [out: Rope.ROPE]; WritePoly: PROC [in: SignatureTable, out: IO.STREAM, termRope: Rope.ROPE _ NIL]; PolyFromDPoly: PROC [in: DP.DSignatureTable, polynomialRing: AlgebraClasses.Object] RETURNS [out: SignatureTable]; DPolyFromPoly: PROC [in: SignatureTable] RETURNS [out: DP.DSignatureTable]; Monomial: AlgebraClasses.BinaryImbedOp; LeadingCoefficient: AlgebraClasses.UnaryOp; Degree: AlgebraClasses.ElementRankOp; Reductum: AlgebraClasses.UnaryOp; Zero: AlgebraClasses.NullaryOp; One: AlgebraClasses.NullaryOp; Add: AlgebraClasses.BinaryOp; Negate: AlgebraClasses.UnaryOp; Subtract: AlgebraClasses.BinaryOp; Multiply: AlgebraClasses.BinaryOp; Power: AlgebraClasses.BinaryOp; Differentiate: AlgebraClasses.BinaryOp; IndefIntegrate: AlgebraClasses.BinaryOp; MainVarEval: AlgebraClasses.BinaryOp; AllVarEval: AlgebraClasses.BinaryOp; Subst: AlgebraClasses.BinaryOp; DegreeDelta: PROC [terms: LIST OF Term] RETURNS [CARDINAL]; SylvesterMatrix: AlgebraClasses.BinaryOp; Resultant: AlgebraClasses.BinaryOp; SignVars: AlgebraClasses.ElementRankOp; Reverse: AlgebraClasses.UnaryOp; Content: AlgebraClasses.UnaryOp; PrimitivePart: AlgebraClasses.UnaryOp; PseudoDivide: AlgebraClasses.BinaryToPairOp; TrialDivide: AlgebraClasses.BinaryToPairOp; Divide: AlgebraClasses.BinaryToPairOp; Remainder: AlgebraClasses.BinaryOp; ExactQuotient: AlgebraClasses.BinaryOp; GCD: AlgebraClasses.BinaryOp; GreatestSqFreeDivisor: AlgebraClasses.UnaryOp; Equal: AlgebraClasses.EqualityOp; IsZero: AlgebraClasses.UnaryPredicate; Sign: AlgebraClasses.CompareToZeroOp; Abs: AlgebraClasses.UnaryOp; Compare: AlgebraClasses.BinaryCompareOp; NewMainVariable: AlgebraClasses.BinaryOp; END. *SignatureTables.mesa Last Edited by: Arnon, March 5, 1986 10:49:31 am PST Generic recursive polynomials in one variable over a ring. SignatureTable Representation Recursive representation. The terms of a nonconstant polynomial are sorted in order of decreasing exponent, thus the reductum of a polynomial (if nonzero) is expected to be a polynomial in the same number of variables, of lower degree. Zero polynomial is represented by SignatureTableData = NIL. Instance Data for SignatureTable Rings SignatureTable Structure Ops 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. Conversion and IO Provides for specification of a termRope. Provides for a termRope, and encloses poly in newlines. Constructors data1 = coeff, data2 = REF exp. Returns coeff * var ^ exp. Selectors Leading coeff of the recursive form of this poly. Returns zero[coeffRing] for zero poly. Degree in main variable. Degree[ZeroPoly] = 0. Reductum of the recursive form of this poly. Reductum[ZeroPoly] = ZeroPoly. Arithmetic 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. 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 the (main) variable of in at an element of the coeffRing of in. Horner's method used. Evaluate all variables of in at a point over the baseCoeffRing of in. Substitute at for the (main) variable of in. in and at belong to the same polynomial ring. Horner's method used. 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. Sylvester matrix Resultant. 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 the coefficients of a polynoimila. PROC [dividend, divisor: SignatureTable] RETURNS [quotient, remainder: SignatureTable]; This is a method for polys over a ring. 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. 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. 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. Returns NIL if secondArg does not divide firstArg exactly, i.e. if Divide either fails, or returns nonzero remainder. 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 Sign of the leading base coefficient. Utility 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 Ê¯˜Jšœ™J™4J˜J™:J˜šÏk ˜ Jšœ˜J˜Jšœ˜Jšœ ˜ Jšœ˜J˜ J˜Jšœ ˜ —J˜head2šœœ˜"J˜—Jšœ˜headšœÏn™šœœ˜-J˜—Jšœœœœ˜(J˜Jšœ¤œ™¨J˜Jšœœœ ˜šœ œœ˜Jšœ œ˜Jšœ"˜"Jšœ˜——šœ&™&Icodešœœœ˜=šœœœ˜*Mšœ!˜!MšœÏc˜.Mšœ&Ÿ˜BMšœ1Ÿ*˜[M˜——šœ™šžœ4˜OJšœP™PJšœ<™