Computer Algebra Kit (c) 1993,00 by Comp.Alg.Objects. All Rights Reserved.

**Maturity Index:** Relatively mature

As an example, consider the recursive polynomial in two variables (2 *x*^2 + 1) *y*^3 + *x* *y*; it's a sum of two terms. The same polynomial in expanded representation is the sum of three monomials : 2 *x*^2 *y*^3 + *y*^3 + *x* *y*.

Not all representations are implemented. Some representations (notably the variable sparse ones) are implemented in Objective C, and can already be used, but may be slow. The following table summarizes the current state of implementation of Polynomial :

- variable sparse, recursive and degree sparse : temporary implementation
- variable sparse, recursive and degree dense : not implemented
- variable dense, recursive and degree sparse : implemented over objects, integers and integers modulo a small prime
- variable dense, recursive and degree dense : implemented over objects, integers and integers modulo a small prime
- variable sparse, expanded and degree sparse : temporary implementation
- variable sparse, expanded and degree dense : not implemented
- variable dense, expanded and degree sparse : implemented over objects, integers and integers modulo a small prime
- variable dense, expanded and degree dense : not implemented

For a variable dense polynomial, the collection of symbols is fixed when the monomial is created; you can't insert terms in a different symbol. In the variable sparse case, the collection of symbols is dynamically adapted as you insert terms, but is kept sorted alphabetically. Note that in the variable dense case, the collection of symbols contains the actual set of symbols (those that actually occur in the polynomial with nonzero exponent) as a *subset*. See the documentation on **symbols**. The variable ordering imposed by the collection of symbols is called *lexicographic* (currently the variable ordering is always lexicographic). Note that in the variable dense case, the lexicographic order need not be alphabetical.

If the polynomial is variable sparse, the coefficients of the terms are either scalar objects or again variable sparse polynomials and each symbol can be different. If the polynomial is variable dense, all symbols of all terms are equal, and the coefficients are either all scalar objects or again all variable dense polynomials. In a degree dense polynomial, the coefficients of the terms can be zero;while (aTerm = [aRecursivePolynomial removeTerm]) [aCollection add:aTerm];

The methods **eachMonomial**, **removeMonomial** and **insertMonomial:** apply to polynomials in expanded representation. For example, to obtain a collection of monomials from a polynomial :

The coefficients of the monomials are scalar objects. If the polynomial is variable sparse, the monomials are too. For degree dense polynomialsaSequence = [anExpandedPolynomial eachMonomial]; while (aMonomial = [aSequence next]) [aCollection add:aMonomial];

- scalarZero
- termZero
- monomialZero
- hash
- isEqual:
- isRecursive
- isExpanded
- isVariableSparse
- isVariableDense
- isDegreeDense
- isDegreeSparse
- isUnivariate
- inUnivariateDomain
- isMultivariate

- intValue
- intValue:
- floatValue
- floatValue:
- asScalar
- asSymbol
- asTerm
- asMonomial
- asCoefficient
- asNumerical
- asModp:

- makeDegreeDense
- makeDegreeSparse
- makeRecursive
- makeExpanded
- makeVariableSparse
- makeVariableDense
- collect:

- one
- isOne
- isMinusOne
- multiply:
- square
- inverse
- multiplyScalar:
- divideScalar:
- multiplyCoefficient:
- divideCoefficient:
- multiplyTerm:
- divideTerm:
- multiplyMonomial:
- divideMonomial:

+Creates and returns a polynomial in the recursive, variable sparse and degree sparse representation, containing the scalar objectscalar:aScalar

-Makes a copy of all the terms or monomials of the polynomial. The original polynomial and the copy don't share any terms or monomials.copy

-Makes a full independent copy of the polynomial by copying all terms or monomials and by sendingdeepCopy

-Returns a new empty polynomial i.e. a polynomial that is equal to zero and not a copy of another polynomial. The representation of the new polynomial is the same as the representation of the object that received the message.empty

-Returns the zero (base) scalar element.scalarZero

-Returns the zero term for a recursive polynomial. In the variable dense case, you may depend upon the fact that the symbol of this term is set to the main symbol of the polynomial (the exponent is set to one).termZero

-Returns the zero monomial for an expanded polynomial.monomialZero

- (BOOL)Returns YES if the polynomial is in recursive representation. Implies that the polynomial is not in expanded representation.isRecursive

- (BOOL)Returns YES if the polynomial is in expanded representation. Implies that the polynomial is not in recursive representation.isExpanded

- (BOOL)Returns YES if the polynomial is variable sparse. Implies that the polynomial is not variable dense.isVariableSparse

- (BOOL)Returns YES if the polynomial is variable dense. Implies that the polynomial is not variable sparse.isVariableDense

- (BOOL)Returns YES if the polynomial is degree dense. Implies that the polynomial is not degree sparse.isDegreeDense

- (BOOL)Returns YES if the polynomial is degree sparse. Implies that the polynomial is not degree dense.isDegreeSparse

- (BOOL)Whether the number of symbols equals one.isUnivariate

- (BOOL)Whether the polynomial is variable dense and the number of symbols equals one.inUnivariateDomain

- (BOOL)isMultivariate

- (int)Returns zero if the polynomial is zero. If the polynomial consists of a single term or monomial, returns the int value of that object. Otherwise generates an error.intValue

-Returns a polynomial (of the same representation as the polynomial that receives the message) with value equal tointValue:(int)aValue

- (float)Returns zero if the polynomial is zero. If the polynomial consists of a single term or monomial, returns the float value of that object. Otherwise generates an error.floatValue

-Returns a polynomial (of the same representation as the polynomial that receives the message) with value equal tofloatValue:(float)aValue

-If the polynomial consists of just one term or monomial that is a scalar, this method returns a copy of the scalar. Otherwise it returnsasScalar

-If the polynomial consists of a single symbol (with exponent one and coefficient one), this method returns a copy of the symbol. Otherwise it returnsasSymbol

-Returns, for a recursive polynomial that consists of a single term, a copy of that term. ReturnsasTerm

-Returns, for an expanded polynomial that consists of a single monomial, a copy of that monomial. ReturnsasMonomial

-This method applies only to recursive polynomials. If the polynomial is a term, this method returns a copy of its coefficient. Otherwise it returnsasCoefficient

-Returns a numerical polynomial, ie. a polynomial in the same representation as the original polynomial but with the scalars are replaced by their numerical value. For example, for a polynomial with integer coefficients, this method returns a polynomial with floating-point objects as coefficients.asNumerical

-Returns a new polynomial, of the same representation as the original polynomial, but with the scalars replaced by their value moduloasModp:(unsigned short)p

-Returns a collection of symbols. If the polynomial is variable dense, beware that some symbols may occur with a zero exponent in the polynomial. If the polynomial is variable sparse, this method returns an alphabetically sorted collection of all the symbols that occur in the polynomial with non-zero exponent. Don' modify the collection returned by this method; do not attempt to insert new symbols, or change their order.symbols

- (int)For a recursive polynomial, returns the maximum of the exponents of the terms. For an expanded polynomial, returns the maximum of the degrees of the monomials (the method first checks whether the variable order is degree or reverse degree compatible, because if it is, the maximum is not really computed). Returns minus one if the polynomial is equal to zero.degree

- (int)For a recursive polynomial, returns the minimum of the exponents of the terms. For an expanded polynomial, returns the minimum of the degrees of the monomials (the method first checks whether the variable order is degree or reverse degree compatible, because if it is, the minimum is not really computed). Returns minus one if the polynomial is equal to zero.order

**See also:** termContent, monomialContent

- (int)Returns the number of nonzero terms in the polynomial. Returns zero if the polynomial is equal to zero. In the case of a degree dense polynomial, the actual number of terms (including zero terms) can be obtained as the number of members of the associated sequence, or, for a univariate polynomial, as the degree of the polynomial plus one.numTerms

- (int)Returns the number of a non-zero monomials in the polynomial. Returns zero if the polynomial is equal to zero. In the case of a degree dense polynomial, the actual number of monomials (including zero monomials) can be obtained as the number of members of the associated sequence.numMonomials

-Removes (and returns) the leading non-zero term of the polynomial. ReturnsremoveTerm

If the polynomial is variable dense, the coefficient of the term is either a scalar, or a variable dense polynomial in a variable less. If the polynomial is variable sparse, the coefficient of the term is the same kind of variable sparse polynomial as the original ie., there is no difference between coefficient domain and polynomial domain in the variable sparse case.

If the polynomial is degree dense, this method cannot be used to obtain the zero terms in the polynomial (because the leading term is defined as the first non-zero term in the sequence of terms). The method **eachTerm** returns all terms, including zero terms.

-InsertsinsertTerm:aTerm

As always, if the exponent of the term is zero, the symbol of the term must be **nil**. If the polynomial is variable sparse, the coefficient of the term must be either a scalar object or a <<non-scalar>> variable sparse polynomial. In the variable dense case, the symbol of the term must be equal to the main symbol of the variable dense polynomial; the coefficient domain of the polynomial must match the coefficient of the term; it may be either a scalar object or a variable dense polynomial.

If the polynomial is degree sparse, insertion is fast at head or tail of the linked list of terms. If the polynomial is degree dense, the array of coefficients is automatically expanded to make room for new terms. Therefore, it's better to insert terms of higher degree before terms of smaller degree in the degree dense case.

-Removes the leading monomial of the polynomial. ReturnsremoveMonomial

-InsertsinsertMonomial:aMonomial

-Returns, for a recursive polynomial, a sequence of terms. You may not modify the terms in the sequence or alter the polynomial in any other way while sequencing over its contents. A zero polynomial is represented by an empty sequence. If the polynomial is variable dense, all the terms in the sequence have the same symbol; if it is variable sparse, the symbols may be different. The terms are ordered with decreasing exponents (and in the variable sparse case, with respect to the symbols). The first member of the sequence is the leading term of the polynomial; this term is never equal to zero. If the polynomial is degree sparse, the sequence doesn't contain any terms with zero coefficient. If the polynomial is degree dense, the sequence also contains the terms with zero coefficient (unlikeeachTerm

**See also:** CASequence

-LikeeachMonomial

**See also:** CASequence

-eachSequence

Returns, for recursive or expanded polynomials, a sequence whose members are either monomials or again sequences. At the deepest level of recursion the members of this sequence are *monomials*, even for recursive polynomials.

The following example shows how to access the leading monomial of a recursive, non-zero polynomial (such a polynomial is *not* a sum of monomials) :

aSequence = [aRecursivePolynomial eachSequence]; aMember = [aSequence firstElement]; while ([aMember isKindOfSequence]) aMember = [aMember firstElement]; printf("leading monomial is %s",[aMember str]);

-Returns a sequence of the scalar objects in the polynomial. If the polynomial is in expanded representation, this sequence contains the scalars of the monomials in the polynomial. If it is recursive, then the sequence contains the (base) scalars in the polynomial.eachScalar

**Note:** The sequence returned by this method doesn't respond to **at:** messages.

-Returns, for a recursive and variable dense polynomial, a sequence of the coefficients of the terms in the polynomial.eachCoefficient

-If the polynomial is degree dense, this method merely returns a copy ofmakeDegreeDense

-If the polynomial is degree sparse, this method merely returns a copy ofmakeDegreeSparse

-Returns, for an expanded polynomial, a new polynomial over the same domain of scalars and with the same value, but in the recursive representation. The polynomial may be degree dense or degree sparse, variable sparse or variable dense.makeRecursive

-Returns, for a recursive polynomial, a new polynomial over the same domain of scalars and with the same value, but in the expanded representation. The polynomial may be degree dense or degree sparse, variable sparse or variable dense.makeExpanded

-Returns, for a variable dense polynomial, a new polynomial over the same domain of scalars and with the same value, but in the variable sparse representation. The polynomial may be degree dense or degree sparse, recursive or expanded.makeVariableSparse

-Returns, for a variable sparse or variable dense polynomial, a new polynomial over the same domain of scalars and with the same value, but in the variable dense representation. The polynomial may be degree dense or degree sparse, recursive or expanded. This method invokesmakeVariableDense

**See also:** collect

-collect:symbols

Returns, for a variable sparse or variable dense polynomial, a new variable dense polynomial in the symbols indicated by the collection *symbols*. The collection must contain at least one symbol. The original polynomial may be degree dense or degree sparse, recursive or expanded, and the resulting polynomial will be of the same representation.

The following examples show how to convert a variable sparse polynomial into variable dense representation, how to convert two variable sparse polynomials into the *same* variable dense representation, and finally how to change the variable order of a variable dense polynomial :

{ dense = [sparse collect:[sparse symbols]]; }

{ symbols = [[a symbols] union:[b symbols]]; c = [a collect:symbols]; d = [b collect:symbols]; }

{ symbols = [[b symbols] copy]; /* ... do something with "symbols" here... */ d = [b collect:symbols]; }

-Returns the leading term of the (recursive) polynomial. ReturnsleadingTerm

-Returns the leading coefficient of the (recursive) polynomial. ReturnsleadingCoefficient

- (int)For a recursive polynomial, returns the sign of the leading coefficient. For a polynomial in expanded representation, returns the sign of the leading scalar. Returns zero if the polynomial is equal to zero.leadingSign

-Returns the leading monomial of the polynomial (in expanded representation). ReturnsleadingMonomial

-Returns the scalar of the leading monomial of the polynomial. ReturnsleadingScalar

- (BOOL)For a recursive polynomial, returns YES if the leading coefficient of the polynomial is equal to one. For an expanded polynomial, tests whether the leading scalar is equal to one. It follows that the same polynomialisMonic

- (BOOL)WhethernotMonic

-makeMonic

-Returns a copy of the zero polynomial (same representation as polynomial that receives the message). The only difference withzero

**See also:** empty

-Returns a new polynomial; adds the (base) scalaraddScalar:s

-Returns a new polynomial; subtracts the (base) scalarsubtractScalar:s

-Returns a copy of the unity polynomial (same representation as polynomial that receives the message).one

- (BOOL)Whether the polynomial is equal to one.isOne

- (BOOL)Whether the polynomial is equal to minus one.isMinusOne

-Returns a new polynomial. Computes the product of the polynomials by the classical polynomial multiplication algorithm, except if the polynomials are equal in which case the method invokesmultiply:b

-Returns a new polynomial. Computes the square of the polynomial by the classical polynomial multiplication algorithm using symmetry.square

-Returns a new polynomial that is the inverse of the polynomial, orinverse

-Returns new polynomialsremainder:bquotient:(id *)q

If the polynomials are variable sparse, they are converted into variable dense representation. The division algorithm itself, works for univariate and multivariate variable dense polynomials, in recursive or expanded representation, over fields or integral domains. However, in the multivariate case, a non-zero remainder need not be unique. In the case of division of polynomials with coefficients in an integral domain (such as the integers), the division possibly fails when a coefficient division fails; it is still possible to do a pseudo-division. Seeid q,r; r = [self remainder:b quotient:&q]; /* do something with r and q */

-Returns the exact quotient (a new polynomial) of the polynomial division. Returnsdivide:b

-If the polynomials are variable sparse or expanded, they are temporarily converted into variable dense and recursive representation for this operation. IfpseudoRemainder:bquotient:(id *)q

-Computes the pseudo-remainder of the polynomials by invokingpseudoRemainder:b

-Returns the content of the sequence of scalars of the polynomial (the greatest common divisor of the scalars in the polynomial); the result is a new scalar object. If the polynomial is zero, this method returnscontent

-If the polynomial is zero, this method returns a copy of itself. Otherwise, this method returns the quotient (a new polynomial) on division by the scalar returned bydivideContent

-Returns for a variable dense and recursive polynomial, the greatest common divisor of the coefficients (not scalars) of the polynomial. If the polynomial is equal to zero, this method returnscoefficientContent

-If the polynomial is zero, this method returns a copy of itself. Otherwise, this method returns the quotient (a new polynomial) on division by the coefficient returned bydivideCoefficientContent

-Returns for a variable dense and recursive polynomial, thetermContent

**See also:** order

-Returns the greatest common divisor (a monic monomial) of the monomials in an expanded polynomial. If the polynomial is equal to zero, this method returnsmonomialContent

-Drops terms or monomials of degree greater thantruncateAtDegree:(int)d

-Returns a new polynomial that is the image of the polynomial under the frobenius map by sendingfrobenius

-Returns a new polynomial that is the image of the polynomial under the inverse of the frobenius map by sendingfrobeniusInverse

-evaluate:aScalar

Replaces the main variable of the polynomial by *aScalar*, and if the polynomial is univariate, returns a scalar object. If the polynomial is not univariate, it must be recursive and variable dense and the method returns again a recursive and variable dense polynomial in a variable less (ie. a coefficient object), obtained by replacing the main variable by *aScalar*.

-evaluate:(STR)aSymbolat:aScalar

Returns a new polynomial object, obtained by replacing the variable named *aSymbol* by *aScalar*.

-Returns a new scalar object, obtained by replacing all variables of the polynomial by the scalar objects in the collectionevaluateAll:cltnOfScalars

-Returns a new (variable dense) polynomial, obtained by replacing the main variable of a variable dense polynomial bysubstitute:aPolynomial

-Returns a new polynomial, obtained by replacing the variable namedsubstitute:(STR)aSymbolby:aPolynomial

-substituteAll:cltnOfPolynomials

Returns a new polynomial, obtained by replacing all variables simultaneously by the polynomials in the collection*cltnOfPolynomials*.

Change of Variables - Permuting (Swapping) Variables = substituteAll

-Returns the derivative of a variable dense polynomial with respect to the main variable (the last member in the collection returned byderive

-deriveWrt:(STR)aSymbol

Returns the derivative of the polynomial with respect to the variable named *aSymbol*. For example, to integrate a polynomial with respect to *x* :

pdx = [p deriveWrt:"x"];

-Integrates a variable dense polynomial with respect to the main variable (the last member in the collection returned byintegrate

-integrateWrt:(STR)aSymbol

Integrates the polynomial with respect to the variable named *aSymbol*.

- (BOOL)Whether the polynomial prints a leading minus sign.printsLeadingSign

- (BOOL)Whether the polynomial prints multiple terms or monomials separated by a plus or minus signs.printsSum

- (BOOL)Whether the polynomial prints a single product.printsProduct

-Prints the polynomial, by sendingprintOn:(IOD)aFile