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

Polynomial

Inherits from: CAObject

Maturity Index: Relatively mature

Class Description

Polynomials are sums of products of scalar objects and symbols raised to small, non-negative integer exponents.  The scalars and symbols can be arbitrary Computer Algebra Kit objects.  Polynomial supports arithmetic over floating-point scalars, or elements of a field (see inField), or scalars that are elements of an integral domain (see inIntegralDomain).

Representations

All together, the Polynomial object presents eight different representations for polynomial arithmetic.  A recursive polynomial is a sum of terms, where each term consists of a coefficient, that is either a scalar object or again a polynomial, multiplied by a symbol raised to an exponent (see Term).  An expanded polynomial is a sum of monomials, each monomial consists of a scalar multiplied by a product of terms (see Monomial).  If the polynomial is variable dense, the collection of possible symbols is fixed and symbols raised to the exponent zero are internally stored; if the polynomial is variable sparse, it's not defined a priori what symbols are allowed to occur in the polynomial.   A polynomial can be either degree dense or degree sparse.  If the polynomial is degree dense, terms or monomials can have a zero coefficient, otherwise the polynomial is internally stored as a linked list of non-zero terms or monomials.

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

Depending on the type of algorithm you're implementing or using, a different representation is preferred.  The variable dense representation for polynomials of 'high' degree in 'few' variables.  The variable sparse representation for polynomials of 'small' degree in 'many' variables.  Degree dense polynomials over finite fields perform well in factorization problems.  Degree sparse polynomials are preferred when there are many zero coefficients in the polynomial.  The expanded representation is used in the computation of Groebner bases, recursive polynomials are preferred for greatest common divisors, resultants etc.

Symbols and Variable Ordering

Note: Symbols can be arbitrary objects.  Any object that implements isEqual:, and for variable sparse polynomials, compare:, will serve (in the variable dense case it's not necessary to compare symbols because the ordering is fixed by the collection of symbols).  We always refer to the objects in question as symbols, even when they are not instances of the Symbol class.  

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. 

Accessing Terms and Monomials in a Polynomial

The methods eachTerm, removeTerm and insertTerm: apply to recursive polynomials.  For example, to obtain a collection of non-zero terms from a polynomial : 

while (aTerm = [aRecursivePolynomial removeTerm]) [aCollection add:aTerm];

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; eachTerm might in effect return a zero term.  It never does so for a degree sparse polynomial.

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

aSequence = [anExpandedPolynomial eachMonomial];
while (aMonomial = [aSequence next]) [aCollection add:aMonomial];

The coefficients of the monomials are scalar objects.  If the polynomial is variable sparse, the monomials are too.  For degree dense polynomials eachMonomial also returns monomials with a zero coefficient.  The leading monomial, returned by removeMonomial is never zero.

Greatest Common Divisors

There is an implementation of an algorithm to compute the GCD of (multivariate) polynomials.  For univariate polynomials over a field, the Euclidean algorithm is being used.  See gcd: for more details.

Counting Real Roots

Polynomial implements for univariate polynomials with coefficients taken from an ordered domain (such as the integers) an algorithm to count the (total) number of real roots of the polynomial.  See the documentation on numRealRoots.

Factorization

Polynomial implements a method to factor a polynomial into its squarefree parts, over fields or integral domains (zero or non-zero characteristic).  See factorSquareFree for more details.  There is also an implementation of an algorithm to factor a polynomial over a finite field into its irreducible factors.  See the documentation on factor.

Method types

Creation	- scalar:
	- copy
	- deepCopy
	- empty

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

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

Symbols and Variables	- symbols

Degree and Order	- degree
	- order

Number of Terms and Monomials	- numTerms
	- numMonomials

Removing and Inserting	- removeTerm
	- insertTerm:
	- removeMonomial
	- insertMonomial:

Sequences	- eachTerm
	- eachMonomial
	- eachSequence
	- eachScalar
	- eachCoefficient

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

Leading Term or Monomial	- leadingTerm
	- leadingCoefficient
	- leadingSign
	- leadingMonomial
	- leadingScalar

Monic Polynomials	- isMonic
	- notMonic
	- makeMonic

Addition	- zero
	- isZero
	- isOpposite:
	- negate
	- double
	- add:
	- subtract:
	- addScalar:
	- subtractScalar:

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

Polynomial Division	- remainder:quotient:
	- divide:

Pseudo Division	- pseudoRemainder:quotient:
	- pseudoRemainder:

Contents and Primitive Parts	- content
	- divideContent
	- coefficientContent
	- divideCoefficientContent
	- termContent
	- monomialContent

Resultant and Greatest Common Divisor	- gcd:
	- resultant:
	- resultant:wrt:
	- discriminant

Counting Real Roots	- numRealRoots
	- varRealRoots:

Factoring	- isSquareFree
	- factorSquareFree

Truncation	- truncateAtDegree:

Characteristic	- frobenius
	- frobeniusInverse

Evaluation and Substitution	- evaluate:
	- evaluate:at:
	- evaluateAll:
	- substitute:
	- substitute:by:
	- substituteAll:

Derivation and Integration	- derive
	- deriveWrt:
	- integrate
	- integrateWrt:

Printing	- printsLeadingSign
	- printsSum
	- printsProduct
	- printOn:

Methods

scalar:
+scalar:aScalar

Creates and returns a polynomial in the recursive, variable sparse and degree sparse representation, containing the scalar object aScalar.

copy
-copy

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.

deepCopy
-deepCopy

Makes a full independent copy of the polynomial by copying all terms or monomials and by sending deepCopy messages to the scalar objects.  The original polynomial and the copy don't share any scalars, terms or monomials.

empty
-empty

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.

scalarZero
-scalarZero

Returns the zero (base) scalar element.

termZero
-termZero

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).

monomialZero
-monomialZero

Returns the zero monomial for an expanded polynomial.

hash
- (unsigned)hash

Returns a small integer that is the same for objects that are equal (in the sense of isEqual:).

isEqual:
- (BOOL)isEqual:b

Whether the two objects are equal.  Returns YES if the objects are pointer equal.

isRecursive
- (BOOL)isRecursive

Returns YES if the polynomial is in recursive representation.  Implies that the polynomial is not in expanded representation.

isExpanded
- (BOOL)isExpanded

Returns YES if the polynomial is in expanded representation.  Implies that the polynomial is not in recursive representation.

isVariableSparse
- (BOOL)isVariableSparse

Returns YES if the polynomial is variable sparse.  Implies that the polynomial is not variable dense.

isVariableDense
- (BOOL)isVariableDense

Returns YES if the polynomial is variable dense.  Implies that the polynomial is not variable sparse.

isDegreeDense
- (BOOL)isDegreeDense

Returns YES if the polynomial is degree dense.  Implies that the polynomial is not degree sparse.

isDegreeSparse
- (BOOL)isDegreeSparse

Returns YES if the polynomial is degree sparse.  Implies that the polynomial is not degree dense.

isUnivariate
- (BOOL)isUnivariate

Whether the number of symbols equals one.

inUnivariateDomain
- (BOOL)inUnivariateDomain

Whether the polynomial is variable dense and the number of symbols equals one.

isMultivariate
- (BOOL)isMultivariate

intValue
- (int)intValue

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:
-intValue:(int)aValue

Returns a polynomial (of the same representation as the polynomial that receives the message) with value equal to aValue.

floatValue
- (float)floatValue

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:
-floatValue:(float)aValue

Returns a polynomial (of the same representation as the polynomial that receives the message) with value equal to aValue.

asScalar
-asScalar

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

asSymbol
-asSymbol

If the polynomial consists of a single symbol (with exponent one and coefficient one), this method returns a copy of the symbol.  Otherwise it returns nil.  The method returns nil if the polynomial is a scalar that is a symbol...

asTerm
-asTerm

Returns, for a recursive polynomial that consists of a single term, a copy of that term.  Returns nil if the polynomial is zero (not considered to be a term) or a polynomial that consists of two or more terms.

asMonomial
-asMonomial

Returns, for an expanded polynomial that consists of a single monomial, a copy of that monomial.  Returns nil if the polynomial is zero (not considered to be a monomial) or a polynomial that consists of two or more monomials.

asCoefficient
-asCoefficient

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

asNumerical
-asNumerical

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.

asModp:
-asModp:(unsigned short)p

Returns a new polynomial, of the same representation as the original polynomial, but with the scalars replaced by their value modulo p, a small prime number.

symbols
-symbols

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.

degree
- (int)degree

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.

order
- (int)order

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.

See also: termContent, monomialContent

numTerms
- (int)numTerms

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.

numMonomials
- (int)numMonomials

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.

removeTerm
-removeTerm

Removes (and returns) the leading non-zero term of the polynomial.  Returns nil if the polynomial is equal to zero.  The polynomial must be in recursive representation, but may be either degree sparse or degree dense, variable sparse or variable dense.  To remove a term, the polynomial may not be a copy of another polynomial.

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.

insertTerm:
-insertTerm:aTerm

Inserts aTerm into the recursive polynomial and returns self.  If the polynomial already contains a term with the same exponent, then the coefficients of the terms are added together.  Otherwise, aTerm is inserted in the collection of terms.  In any case, after insertion, aTerm belongs to the polynomial.  To insert a term, the polynomial may not be a copy of another polynomial.

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.

removeMonomial
-removeMonomial

Removes the leading monomial of the polynomial.  Returns nil if the polynomial is equal to zero.  The polynomial may be variable sparse or variable dense, degree sparse or degree dense, but must be in expanded representation.  To remove a monomial, the polynomial may not be a copy of another polynomial.

insertMonomial:
-insertMonomial:aMonomial

Inserts aMonomial into the expanded polynomial and returns self.  If the polynomial already contains a monomial with the same terms, then the scalars of the monomials are added together.  Otherwise, aMonomial is inserted in the collection of monomials.  In any case, after insertion, aMonomial belongs to the polynomial.  The polynomial may not be a copy of another polynomial.

eachTerm
-eachTerm

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 (unlike removeTerm).

See also: CASequence

eachMonomial
-eachMonomial

Like eachTerm but for expanded polynomial; returns a sequence of monomials.  A zero polynomial is represented by an empty sequence.  If the polynomial is variable dense, all the monomials in the sequence are variable dense; they are variable sparse if the polynomial is variable sparse.  The monomials are ordered with respect to Monomials compareTerms: method.  The first member of the sequence is the leading monomial of the polynomial; it's never equal to zero.  If the polynomial is degree sparse, the sequence doesn't contain any monomials with zero coefficient.  If the polynomial is degree dense, the sequence also contains the monomials with zero coefficient (unlike removeMonomial).

See also: CASequence

eachSequence
-eachSequence

Note: Not implemented.

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]);

eachScalar
-eachScalar

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.

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

eachCoefficient
-eachCoefficient

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

makeDegreeDense
-makeDegreeDense

If the polynomial is degree dense, this method merely returns a copy of self.  Otherwise, it creates a new degree dense polynomial and converts the polynomial into this new representation (making copies of the terms or monomials of the polynomial).   The resulting polynomial may be recursive, expanded, variable sparse or variable dense, depending on the representation of the original polynomial.

makeDegreeSparse
-makeDegreeSparse

If the polynomial is degree sparse, this method merely returns a copy of self.  Otherwise, it creates a new degree sparse polynomial and converts the polynomial into this new representation (making copies of the terms or monomials of the polynomial).   The resulting polynomial may be recursive, expanded, variable sparse or variable dense, depending on the representation of the original polynomial.

makeRecursive
-makeRecursive

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.

makeExpanded
-makeExpanded

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.

makeVariableSparse
-makeVariableSparse

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.

makeVariableDense
-makeVariableDense

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 invokes collect:.

See also: collect

collect:
-collect:symbols

Note: <<The case of symbols a collection with less members than the number of variables of the polynomial is not yet implemented.  Currenlty symbols must contain the same number, or more symbols than the original polynomial>>

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];
}

leadingTerm
-leadingTerm

Returns the leading term of the (recursive) polynomial.  Returns nil if the polynomial is equal to zero. 

leadingCoefficient
-leadingCoefficient

Returns the leading coefficient of the (recursive) polynomial.  Returns nil if the polynomial is equal to zero.  

leadingSign
- (int)leadingSign

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.

leadingMonomial
-leadingMonomial

Returns the leading monomial of the polynomial (in expanded representation).  Returns nil if the polynomial is equal to zero.  

leadingScalar
-leadingScalar

Returns the scalar of the leading monomial of the polynomial.  Returns nil if the polynomial is equal to zero.

isMonic
- (BOOL)isMonic

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 polynomial x y + 1 is monic in expanded representation, but is not monic in recursive representation (because the leading coefficient is x).  The method returns NO if the polynomial is equal to zero.  

notMonic
- (BOOL)notMonic

Whether isMonic returns NO.

makeMonic
-makeMonic

zero
-zero

Returns a copy of the zero polynomial (same representation as polynomial that receives the message).  The only difference with empty is that the latter method creates a new object, while this method just returns a copy of an already existing object.  For example, it's not possible to insert terms in the polynomial returned by zero.

See also: empty

isZero
- (BOOL)isZero

Whether the object is equal to zero.

isOpposite:
- (BOOL)isOpposite:b

Whether the object is the opposite of b.

negate
-negate

Returns the opposite of the object.

double
-double

Returns a new object, equal to the object multiplied by two i.e., added to itself.

add:
-add:b

Adds b to the object.  Returns a new object.

subtract:
-subtract:b

Subtracts b from the object.  Returns a new object.

addScalar:
-addScalar:s

Returns a new polynomial; adds the (base) scalar s to the original polynomial.

subtractScalar:
-subtractScalar:s

Returns a new polynomial; subtracts the (base) scalar s to the original polynomial.

one
-one

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

isOne
- (BOOL)isOne

Whether the polynomial is equal to one.

isMinusOne
- (BOOL)isMinusOne

Whether the polynomial is equal to minus one.

multiply:
-multiply:b

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 invokes square.

square
-square

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

inverse
-inverse

Returns a new polynomial that is the inverse of the polynomial, or nil if the polynomial cannot be inverted.  A polynomial over a field or integral domain can be inverted if and only if it consists of a single term that is invertible.

multiplyScalar:
-multiplyScalar:s

Multiplies by the scalar s.  Returns a new object.

divideScalar:
-divideScalar:s

Exact division by the scalar s.  Returns a new object, or nil if the division is not exact.

multiplyCoefficient:
-multiplyCoefficient:aCoefficient

Multiplies the (recursive and variable dense) polynomial by aCoefficient and returns a new object.  What aCoefficient means, depends on the representation of the polynomial.  If it is variable dense and univariate, then aCoefficient must be a scalar object.  If it is variable dense and multivariate, then aCoefficient must be again a variable dense polynomial in a variable less.   The method is not implemented in the variable sparse case; you can use multiplyScalar: or multiply: for these polynomials.

divideCoefficient:
-divideCoefficient:aCoefficient

Exact division of the (recursive and variable dense) polynomial by aCoefficient; returns a new object or nil if the division is not exact or if it fails.  If the polynomial is univariate, then aCoefficient must be a scalar object.  If it is multivariate, then aCoefficient must be again a variable dense polynomial in a variable less.   The method is not implemented in the variable sparse case; there you can use divideScalar: or divide:.

multiplyTerm:
-multiplyTerm:aTerm

Multiplies the (recursive) polynomial by the term aTerm; returns a new object.  This method is implemented for both variable sparse and variable dense recursive polynomials.  In the variable dense case, the symbol of the term must be equal to the main symbol of the polynomial and the coefficient classes must match.  In the variable sparse case, the only requirement is that the domain of scalars of the term and the polynomial are equal.

divideTerm:
-divideTerm:aTerm

(Exact) Division of the polynomial by aTerm; returns a new polynomial.  The division fails (and this method returns nil) if one of the terms of the polynomial is not divisible by aTerm.  This method is implemented for both variable sparse and variable dense recursive polynomials.  In the variable dense case, the symbol of the term must be equal to the main symbol of the polynomial and the coefficient classes must match.  In the variable sparse case, the only requirement is that the domain of scalars of the term and the polynomial are equal (and for the division not to fail, that the symbol of the term is less than or equal to the symbols of each term of the polynomial).

multiplyMonomial:
-multiplyMonomial:s

Multiplies by the monomial s.  Returns a new object.

divideMonomial:
-divideMonomial:s

Exact division by the monomial s.  Returns a new object, or nil if the division is not exact.

remainder:quotient:
-remainder:bquotient:(id *)q

Returns new polynomials R and, by reference, Q such that self = Q b + R.  If q is a NULL pointer, the quotient Q is not computed.  Returns nil (and sets the value pointed to by q to nil) if the polynomial division fails.

id q,r;

r = [self remainder:b quotient:&q];
	
/* do something with r and 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.  See pseudoRemainder:quotient: for more details.

divide:
-divide:b

Returns the exact quotient (a new polynomial) of the polynomial division.  Returns nil if the polynomial division fails or if the division was not exact (if there was a non-zero remainder).  The polynomial may be expanded or recursive.

pseudoRemainder:quotient:
-pseudoRemainder:bquotient:(id *)q

If the polynomials are variable sparse or expanded, they are temporarily converted into variable dense and recursive representation for this operation.  If n and m are the degrees of self and b respectively, and if c is the leading coefficient of b, than this method computes the pseudo-remainder R and, if q is not a NULL pointer, the pseudo-quotient Q such that c^(n-m+1) self = Q b + R.  Returns nil if the pseudo-division fails.

pseudoRemainder:
-pseudoRemainder:b

Computes the pseudo-remainder of the polynomials by invoking pseudoRemainder:quotient: with a NULL argument.

content
-content

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 returns nil.

divideContent
-divideContent

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 by content.

coefficientContent
-coefficientContent

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 returns nil.

divideCoefficientContent
-divideCoefficientContent

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 by coefficientContent.

termContent
-termContent

Returns for a variable dense and recursive polynomial, the monic greatest common divisor of the terms of the polynomial.  In other words, this method returns the main symbol of the polynomial raised to the order of the polynomial. 

See also: order

monomialContent
-monomialContent

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

gcd:
-gcd:b

Returns a new polynomial that is the gcd of the polynomials.  For recursive and variable dense polynomials over a field, the method computes the monic gcd of the polynomials by the euclidean algorithm.  Over an integral domain, the method computes the primitive gcd by the improved subresultant algorithm.  Expanded or variable dense polynomials are temporarily converted into recursive and variable dense representation (and the resulting gcd is converted back into the original representation).

resultant:
-resultant:b

Returns the resultant of the pair of two recursive and variable dense polynomials.  The result is a new object that is taken from the coefficient domain i.e., it is either a polynomial in a variable less than the argument polynomials, or it is a scalar.

resultant:wrt:
-resultant:bwrt:(STR)aSymbol

Returns the resultant of the pair of polynomials with respect to the variable named aSymbol.

discriminant
-discriminant

Returns the discriminant of the polynomial i.e. the resultant of the polynomial and its derivative.

Note: This is actually the discriminant up to a scalar.  Scalar factor will change in future.

numRealRoots
- (int)numRealRoots

Returns the number of real roots of a univariate and variable dense polynomial, using Sturm's algorithm over any ordered integral domain or field.  A univariate variable sparse polynomial is temporarily converted into variable dense representation.

varRealRoots:
- (int)varRealRoots:g

Returns the variation of real roots over the polynomial g.

isSquareFree
- (BOOL)isSquareFree

Returns YES if the polynomial is squarefree i.e., if the polynomial and its derivative are coprime.

factorSquareFree
-factorSquareFree

Factors a recursive and variable dense polynomial into a product of squarefree factors.  Returns a new collection of term objects; each term consists of a (base) scalar object, the squarefree factor and a positive integral exponent.  If the scalars are taken from a field, the factors are made monic; for an integral domain, the factors are made primitive.  The algorithm works in the case of zero and non-zero characteristic.  If the polynomial is expanded or variable sparse, the method temporarily converts it into recursive and variable dense representation.  The factors of the polynomial are made expanded or variable sparse again.

truncateAtDegree:
-truncateAtDegree:(int)d

Drops terms or monomials of degree greater than d.  Returns a new polynomial.

frobenius
-frobenius

Returns a new polynomial that is the image of the polynomial under the frobenius map by sending frobenius messages to each term or monomial.

frobeniusInverse
-frobeniusInverse

Returns a new polynomial that is the image of the polynomial under the inverse of the frobenius map by sending frobeniusInverse messages to each term or monomial.  Returns nil if the polynomial is not the image of a polynomial under the frobenius map.

evaluate:
-evaluate:aScalar

Note: Not implemented.

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:at:
-evaluate:(STR)aSymbolat:aScalar

Note: Not implemented.

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

evaluateAll:
-evaluateAll:cltnOfScalars

Returns a new scalar object, obtained by replacing all variables of the polynomial by the scalar objects in the collection cltnOfScalars i.e., the first member in the collection returned by variables is replaced by the first member in cltnOfScalars and so on.  Variable sparse or expanded polynomials are temporarily converted into recursive and variable dense representation by this method.

substitute:
-substitute:aPolynomial

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

substitute:by:
-substitute:(STR)aSymbolby:aPolynomial

Returns a new polynomial, obtained by replacing the variable named aSymbol by aPolynomial.  Implemented for recursive and variable sparse polynomials only.

substituteAll:
-substituteAll:cltnOfPolynomials

Note: Not implemented.

Returns a new polynomial, obtained by replacing all variables simultaneously by the polynomials in the collectioncltnOfPolynomials.

Change of Variables - Permuting (Swapping) Variables = substituteAll 

derive
-derive

Returns the derivative of a variable dense polynomial with respect to the main variable (the last member in the collection returned by variables).

deriveWrt:
-deriveWrt:(STR)aSymbol

Note: Not implemented.

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"];

integrate
-integrate

Integrates a variable dense polynomial with respect to the main variable (the last member in the collection returned by variables).  Because the resulting polynomial is a polynomial over the same domain of scalars as the integrandum, this operation might fail and returns nil if the scalars are not taken from a field.

integrateWrt:
-integrateWrt:(STR)aSymbol

Note: Not implemented.

Integrates the polynomial with respect to the variable named aSymbol. 

printsLeadingSign
- (BOOL)printsLeadingSign

Whether the polynomial prints a leading minus sign.

printsSum
- (BOOL)printsSum

Whether the polynomial prints multiple terms or monomials separated by a plus or minus signs.

printsProduct
- (BOOL)printsProduct

Whether the polynomial prints a single product.

printOn:
-printOn:(IOD)aFile

Prints the polynomial, by sending printOn: messages to the terms or monomials.