DIRECTORY Rope USING [ROPE], Basics, IO USING [STREAM], AlgebraClasses, Points, Variables, DistribPolys, MathExpr; Polynomials: CEDAR DEFINITIONS ~ BEGIN OPEN AC: AlgebraClasses, VARS: Variables, DP: DistribPolys; Polynomial: TYPE = AC.Object; PolynomialData: TYPE = LIST OF Term; Term: TYPE = REF TermRec; TermRec: TYPE = RECORD [ exponent: CARDINAL, coefficient: AC.Object ]; PolynomialSeq: TYPE = REF PolynomialSeqRec; PolynomialSeqRec: TYPE = RECORD [SEQUENCE lengthPlus1:[1..4096] OF Polynomial]; polynomialsOverCommutativeOrderedRingClass: AC.StructureClass; polynomialsOverCommutativeUnOrderedRingClass: AC.StructureClass; polynomialsOverNonCommutativeOrderedRingClass: AC.StructureClass; polynomialsOverNonCommutativeUnOrderedRingClass: AC.StructureClass; polynomialsOverCommutativeOrderedFieldClass: AC.StructureClass; polynomialsOverCommutativeUnOrderedFieldClass: AC.StructureClass; polynomialsOverNonCommutativeOrderedFieldClass: AC.StructureClass; polynomialsOverNonCommutativeUnOrderedFieldClass: AC.StructureClass; PolynomialRingData: TYPE = REF PolynomialRingDataRec; PolynomialRingDataRec: TYPE = RECORD [ coeffRing: AC.Structure, variable: VARS.VariableSeq, -- a single variable baseCoeffRing: AC.Structure, -- this and next field used by distributed poly IO allVariables: VARS.VariableSeq -- cumulative variables over baseCoeffRing ]; PolynomialOps: TYPE = REF PolynomialOpsRec; -- prop key is $PolynomialRing. Skew, i.e. noncommutative, fields ok PolynomialOpsRec: TYPE = RECORD [ monomial: AC.BinaryImbedOp, differentiate: AC.UnaryOp, leadingCoefficient: AC.UnaryOp, degree: AC.ElementRankOp, mainVarEval: AC.BinaryOp, allVarEval: AC.BinaryOp, subst: AC.BinaryOp, sylvesterMatrix: AC.BinaryOp, resultant: AC.BinaryOp ]; MakePolynomialStructure: PROC [coeffRing: AC.Structure, V: VARS.VariableSeq] RETURNS [polynomialRing: AC.Structure]; IsPolynomialRing: PROC [ring: AC.Structure] RETURNS [BOOL]; Monomial: PROC [polynomialRing: AC.Structure] RETURNS [AC.BinaryImbedOp]; Differentiate: PROC [polynomialRing: AC.Structure] RETURNS [AC.UnaryOp]; LeadingCoefficient: PROC [polynomialRing: AC.Structure] RETURNS [AC.UnaryOp]; Degree: PROC [polynomialRing: AC.Structure] RETURNS [AC.ElementRankOp]; MainVarEval: PROC [polynomialRing: AC.Structure] RETURNS [AC.BinaryOp]; AllVarEval: PROC [polynomialRing: AC.Structure] RETURNS [AC.BinaryOp]; Subst: PROC [polynomialRing: AC.Structure] RETURNS [AC.BinaryOp]; SylvesterMatrix: PROC [polynomialRing: AC.Structure] RETURNS [AC.BinaryOp]; Resultant: PROC [polynomialRing: AC.Structure] RETURNS [AC.BinaryOp]; Monom: AC.BinaryImbedOp; Read: AC.ReadOp; FromRope: AC.FromRopeOp; ToRope: AC.ToRopeOp; Write: AC.WriteOp; MakePolyExpr: AC.ToExprOp; PolyToRope: PROC [in: Polynomial, termRope: Rope.ROPE _ NIL] RETURNS [out: Rope.ROPE]; WritePoly: PROC [in: Polynomial, out: IO.STREAM, termRope: Rope.ROPE _ NIL]; ReadPolySeq: PROC [in: IO.STREAM, polynomialRing: AC.Structure] RETURNS [seq: PolynomialSeq]; PolySeqFromRope: PROC [in: Rope.ROPE, polynomialRing: AC.Structure] RETURNS [out: PolynomialSeq]; PolySeqToRope: PROC [in: PolynomialSeq] RETURNS [out: Rope.ROPE]; WritePolySeq: PROC [in: PolynomialSeq, out: IO.STREAM]; PolyFromDPoly: PROC [in: DP.DPolynomial, polynomialRing: AC.Structure] RETURNS [out: Polynomial]; DPolyFromPoly: PROC [in: Polynomial] RETURNS [out: DP.DPolynomial]; Add: AC.BinaryOp; Negate: AC.UnaryOp; Subtract: AC.BinaryOp; Multiply: AC.BinaryOp; Remainder: AC.BinaryOp; Diff: AC.UnaryOp; MainVarEv: AC.BinaryOp; AllVarEv: AC.BinaryOp; Sub: AC.BinaryOp; DegreeDelta: PROC [terms: LIST OF Term] RETURNS [CARDINAL]; SylvMatrix: AC.BinaryOp; Res: AC.BinaryOp; SignVars: PROC [in: Polynomial] RETURNS [CARDINAL]; Reverse: PROC [in: Polynomial] RETURNS [out: Polynomial]; ZeroPoly: PROC [in: Polynomial] RETURNS [BOOL]; Equal: AC.EqualityOp; Sign: AC.CompareToZeroOp; Abs: AC.UnaryOp; Compare: AC.BinaryCompareOp; LeadingCoeff: AC.UnaryOp; Deg: AC.ElementRankOp; Reductum: AC.UnaryOp; END. bPolynomials.mesa Last Edited by: Arnon, March 5, 1986 10:49:31 am PST Generic polynomials in one variable over a ring. Polynomial 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 PolynomialData = NIL. Classes for Polynomial Rings Instance Data for Polynomial Rings Operations unique to Polynomial Rings Polynomial Ring Constructors A particular polynomial structure is defined by its coeffRing and its variables. coeffRing can be a ring, field, algebra, or divisionAlgebra. V can be of any length and the right thing happens. Extract Polynomial Operations from Class Property Lists Error if not a PolynomialRing Error if not a PolynomialRing. Leading coeff of the recursive form of this poly. Constructors data1 = coeff, data2 = REF exp. Returns coeff * var ^ exp. Conversion and IO Provides for specification of a termRope. Provides for a termRope, and encloses poly in newlines. Arithmetic 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 in's coefficients, which are assumed to belong to an ordered structure. Reverse the coefficients of in. Content: PROC [in: POL.Polynomial, ring: AC.Structure] RETURNS [out: POL.Polynomial]; PrimitivePart: PROC [in: POL.Polynomial, ring: AC.Structure] RETURNS [out: POL.Polynomial]; PseudoDivide: PROC [dividend, divisor: POL.Polynomial, coeffRing: AC.Structure] RETURNS [quotient, remainder: POL.Polynomial]; DivisionAlgorithm: PROC [dividend, divisor: POL.Polynomial, coeffRing: AC.Structure] RETURNS [quotient, remainder: POL.Polynomial]; quotient _ remainder _ NIL if fails. ExactDivide: PROC [in1, in2: POL.Polynomial, coeffRing: AC.Structure] RETURNS [out: POL.Polynomial]; Returns NIL = ZeroPoly if in2 does not divide in1 exactly, i.e. if DivisionAlgorithm either fails, or returns nonzero remainder. GreatestCommonDivisor: PROC [dividend, divisor: POL.Polynomial, coeffRing: AC.Structure] RETURNS [quotient, remainder: POL.Polynomial]; GreatestSqFreeDivisor: PROC [in: POL.Polynomial, ring: AC.Structure] RETURNS [out: POL.Polynomial]; 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. Selection Leading coeff of the recursive form of this poly. Returns zero[coeffRing] for zero poly. Degree in main variable. Deg[ZeroPoly] = 0. Reductum of the recursive form of this poly. Reductum[ZeroPoly] = ZeroPoly. Κ¨˜Jšœ™J™4J˜J™0J˜šΟk ˜ Jšœœœ˜J˜Jšœœœ˜Jšœ˜J˜Jšœ ˜ Jšœ ˜ Jšœ ˜ —J˜head2šœ œ ˜J˜—Jš œœœœœ œ ˜Dheadšœ Οn™šœ œœ˜J˜—Jšœœœœ˜$J˜šœ œ™€J˜—Jšœœœ ˜šœ œœ˜Jšœ œ˜Jšœ  ˜Jšœ˜J˜—Jšœœœ˜+šœœ˜Jšœœœ ˜/——šœ™codešœ,œ˜>M˜—šœ.œ˜@M˜—šœ/œ˜AM˜—šœ1œ˜CM˜—šœ-œ˜?M˜—šœ/œ˜AM˜—šœ0œ˜BM˜—Mšœ2œ˜D—šœ"™"Mšœœœ˜5šœœœ˜&Mšœ œ ˜Mšœ œΟc˜0Mšœœ Ÿ2˜OMšœœ Ÿ*˜IM˜——šœ%™%MšœœœŸD˜pšœœœ˜!Mšœ œ˜Mšœœ ˜Mšœœ ˜Mšœœ˜Mšœ œ ˜Mšœ œ ˜Mšœœ ˜Mšœœ ˜Mšœ œ ˜M˜——šœ™š žœœ œœœœ ˜tJšœ™J™3——šœ7™7š žœœœ œœ˜;J™—š žœœœ œœ˜IMšœŸ™M™—š ž œœœ œœ ˜HMšœŸœ™M™—š žœœœ œœ ˜MJ™1J™—š žœœœ œœ˜GJ˜—š ž œœœ œœ ˜GJ˜—š ž œœœ œœ ˜FJ˜—š žœœœ œœ ˜AJ˜—š žœœœ œœ ˜KJ˜—Jš ž œœœ œœ ˜E—šœ ™ šžœœ˜Jšœ:™:——šœ™šžœœ˜J˜—šžœœ ˜J™—šžœœ ˜J˜—šžœœ ˜J˜—šž œœ ˜J˜—š ž œœ!œœœ œ˜VJšœ)™)J˜—š ž œœœœœœ˜LJšœ7™7J™—š ž œœœœœ œ˜]J˜—š žœœ œœ œ˜aJ˜—šž œœœ œ˜AJ˜—šž œœœœ˜7J˜—š ž œœœœ œ˜aM˜—Mšž œœœœ˜C—šœ ™ šžœœ ˜J˜—šžœœ ˜J˜—šžœœ ˜J˜—šžœœ ˜J˜—Jšž œœ ˜J˜šžœœ ˜J˜—šž œœ ˜Jšœb™bJ˜—šžœœ ˜JšœE™EJ˜—šžœœ ˜Jšœr™rJ˜—š ž œœ œœœœ˜;Jšœ›™›J˜—šž œœ ˜M™M˜—šžœœ ˜J™ J˜—šžœœœœ˜3Jšœu™uJ˜—šžœœœ˜9Jšœ™—J™š žœœœœ œœ ™UM™—š ž œœœœ œœ ™[M™—š ž œœœœ œœ ™~J™—š žœœœœ œœ ™ƒJšœ%™%J™—š ž œœ œœ œœ ™dJšœœu™€—M™š žœœœœ œœ ™‡M™—š žœœœœ œœ ™cMšœΏ™Ώ—J™—šœ ™ šžœœœœ˜/J˜—šžœœ ˜J˜—šžœœ˜Jšœ%™%J˜—šžœœ ˜J˜—Mšžœœ˜—™ šž œœ ˜J™XJ™—šžœœ˜Jšœ+™+J˜—šžœœ ˜JšœK™K——J˜Jšœ˜—…—Ά$ΐ