Polynomial Representation
Polynomial:
TYPE =
AC.Object;
PolynomialData: TYPE = LIST OF Term;
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.
Term: TYPE = REF TermRec;
TermRec:
TYPE =
RECORD [
exponent: CARDINAL,
coefficient: AC.Object
];
Instance Data for Polynomial Rings
PolynomialRingData: TYPE = REF PolynomialRingDataRec;
PolynomialRingDataRec:
TYPE =
RECORD [
coeffRing: AC.Object,
variable: Variables.Variable, -- main variable
baseCoeffRing: AC.Object, -- not a polynomialStructure
allVariables: VariableSequences.VariableSequence -- cumulative variables over baseCoeffRing
];
Polynomial Structure Ops
MakePolynomialStructure:
AC.PolynomialStructureConstructor;
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:
AC.PrintNameProc;
ShortPrintName:
AC.PrintNameProc;
BaseCoeffRing:
AC.UnaryOp;
AllVariables:
AC.UnaryOp;
Characteristic:
AC.StructureRankOp;
IsPolynomialStructure: AC.UnaryPredicate;
Conversion and IO
CanRecast:
AC.BinaryPredicate;
LegalFirstChar:
AC.LegalFirstCharOp;
PolyToRope:
PROC [in: Polynomial, termRope: Rope.
ROPE ←
NIL]
RETURNS [out: Rope.
ROPE];
Provides for specification of a termRope.
WritePoly:
PROC [in: Polynomial, out:
IO.
STREAM, termRope: Rope.
ROPE ←
NIL];
Provides for a termRope, and encloses poly in newlines.
PolyFromDPoly:
PROC [in:
DP.DPolynomial, polynomialRing:
AC.Object]
RETURNS [out: Polynomial];
DPolyFromPoly:
PROC [in: Polynomial]
RETURNS [out:
DP.DPolynomial];
Arithmetic
Differentiate:
AC.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:
AC.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:
AC.BinaryOp;
MainVarEval the (main) variable of in at an element of the coeffRing of in. Horner's method used.
AllVarEval:
AC.BinaryOp;
Evaluate all variables of in at a point over the baseCoeffRing of in.
Subst:
AC.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:
AC.BinaryOp;
Sylvester matrix
Resultant:
AC.BinaryOp;
Resultant.
SignVars:
AC.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:
AC.UnaryOp;
Reverse the coefficients of a polynoimila.
PrimitivePart:
AC.UnaryOp;
PseudoDivide:
AC.BinaryToPairOp;
PROC [dividend, divisor: Polynomial] RETURNS [quotient, remainder: Polynomial];
This is a method for polys over a ring.
TrialDivide:
AC.BinaryToPairOp;
PROC [dividend, divisor: Polynomial] RETURNS [quotient, remainder: Polynomial];
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:
AC.BinaryToPairOp;
PROC [dividend, divisor: Polynomial] RETURNS [quotient, remainder: Polynomial];
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:
AC.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:
AC.BinaryOp;
Returns NIL if secondArg does not divide firstArg exactly, i.e. if Divide either fails, or returns nonzero remainder.
GreatestSqFreeDivisor:
AC.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.