.TH "polynom" 3 "Mar 12, 2023"
.SH Polynomial
.PP
.B
Inherits from:
CAObject
.PP
.B
Maturity Index:
Relatively mature
.SH Class Description
.PP
Polynomials are sums of products of
.I
scalar
objects and
.I
symbols
raised to small, non-negative integer
.I
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
.B
inField
), or scalars that are elements of an integral domain (see
.B
inIntegralDomain
)\&.
.SH Representations
.PP
All together, the Polynomial object presents eight different representations for polynomial arithmetic\&. A
.I
recursive
polynomial is a sum of
.I
terms
, where each term consists of a
.I
coefficient
, that is either a scalar object or again a polynomial, multiplied by a symbol raised to an exponent (see
.B
Term
)\&. An
.I
expanded
polynomial is a sum of
.I
monomials
, each monomial consists of a
.I
scalar
multiplied by a product of terms (see
.B
Monomial
)\&. If the polynomial is
.I
variable dense
, the collection of possible symbols is fixed and symbols raised to the exponent zero are internally stored; if the polynomial is
.I
variable sparse
, it\&'s not defined a priori what symbols are allowed to occur in the polynomial\&. A polynomial can be either
.I
degree dense
or
.I
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\&.
.PP
As an example, consider the recursive polynomial in two variables (2
.I
x
^2 + 1)
.I
y
^3 +
.I
x
.I
y
; it\&'s a sum of two terms\&. The same polynomial in expanded representation is the sum of three monomials : 2
.I
x
^2
.I
y
^3 +
.I
y
^3 +
.I
x
.I
y
\&.
.PP
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 :
.RS 3
.br
* variable sparse, recursive and degree sparse : temporary implementation
.br
* variable sparse, recursive and degree dense : not implemented
.br
* variable dense, recursive and degree sparse : implemented over objects, integers and integers modulo a small prime
.br
* variable dense, recursive and degree dense : implemented over objects, integers and integers modulo a small prime
.br
* variable sparse, expanded and degree sparse : temporary implementation
.br
* variable sparse, expanded and degree dense : not implemented
.br
* variable dense, expanded and degree sparse : implemented over objects, integers and integers modulo a small prime
.br
* variable dense, expanded and degree dense : not implemented
.RE
.PP
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\&.
.SH Symbols and Variable Ordering
.PP
.B
Note:
Symbols can be arbitrary objects\&. Any object that implements
.B
isEqual:
, and for variable sparse polynomials,
.B
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
.I
symbols
, even when they are not instances of the
.B
Symbol
class\&.
.PP
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
.I
subset
\&. See the documentation on
.B
symbols
\&. The variable ordering imposed by the collection of symbols is called
.I
lexicographic
(currently the variable ordering is always lexicographic)\&. Note that in the variable dense case, the lexicographic order need not be alphabetical\&.
.SH Accessing Terms and Monomials in a Polynomial
.PP
The methods
.B
eachTerm
,
.B
removeTerm
and
.B
insertTerm:
apply to recursive polynomials\&. For example, to obtain a collection of
.I
non-zero
terms from a polynomial :
.RS 3
while (aTerm = [aRecursivePolynomial removeTerm]) [aCollection add:aTerm];
.br
.RE
.PP
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;
.B
eachTerm
might in effect return a zero term\&. It never does so for a degree sparse polynomial\&.
.PP
The methods
.B
eachMonomial
,
.B
removeMonomial
and
.B
insertMonomial:
apply to polynomials in expanded representation\&. For example, to obtain a collection of monomials from a polynomial :
.RS 3
aSequence = [anExpandedPolynomial eachMonomial];
.br
while (aMonomial = [aSequence next]) [aCollection add:aMonomial];
.br
.RE
.PP
The coefficients of the monomials are scalar objects\&. If the polynomial is variable sparse, the monomials are too\&. For degree dense polynomials
.B
eachMonomial
also returns monomials with a zero coefficient\&. The leading monomial, returned by
.B
removeMonomial
is never zero\&.
.SH Greatest Common Divisors
.PP
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
.B
gcd:
for more details\&.
.SH Counting Real Roots
.PP
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
.B
numRealRoots
\&.
.SH Factorization
.PP
Polynomial implements a method to factor a polynomial into its squarefree parts, over fields or integral domains (zero or non-zero characteristic)\&. See
.B
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
.B
factor
\&.
.SH Method types
.PP
.B
Creation
.RS 3
.br
* scalar:
.br
* copy
.br
* deepCopy
.br
* empty
.RE
.PP
.B
Identity
.RS 3
.br
* scalarZero
.br
* termZero
.br
* monomialZero
.br
* hash
.br
* isEqual:
.br
* isRecursive
.br
* isExpanded
.br
* isVariableSparse
.br
* isVariableDense
.br
* isDegreeDense
.br
* isDegreeSparse
.br
* isUnivariate
.br
* inUnivariateDomain
.br
* isMultivariate
.RE
.PP
.B
Coercion
.RS 3
.br
* intValue
.br
* intValue:
.br
* floatValue
.br
* floatValue:
.br
* asScalar
.br
* asSymbol
.br
* asTerm
.br
* asMonomial
.br
* asCoefficient
.br
* asNumerical
.br
* asModp:
.RE
.PP
.B
Symbols and Variables
.RS 3
.br
* symbols
.RE
.PP
.B
Degree and Order
.RS 3
.br
* degree
.br
* order
.RE
.PP
.B
Number of Terms and Monomials
.RS 3
.br
* numTerms
.br
* numMonomials
.RE
.PP
.B
Removing and Inserting
.RS 3
.br
* removeTerm
.br
* insertTerm:
.br
* removeMonomial
.br
* insertMonomial:
.RE
.PP
.B
Sequences
.RS 3
.br
* eachTerm
.br
* eachMonomial
.br
* eachSequence
.br
* eachScalar
.br
* eachCoefficient
.RE
.PP
.B
Representation
.RS 3
.br
* makeDegreeDense
.br
* makeDegreeSparse
.br
* makeRecursive
.br
* makeExpanded
.br
* makeVariableSparse
.br
* makeVariableDense
.br
* collect:
.RE
.PP
.B
Leading Term or Monomial
.RS 3
.br
* leadingTerm
.br
* leadingCoefficient
.br
* leadingSign
.br
* leadingMonomial
.br
* leadingScalar
.RE
.PP
.B
Monic Polynomials
.RS 3
.br
* isMonic
.br
* notMonic
.br
* makeMonic
.RE
.PP
.B
Addition
.RS 3
.br
* zero
.br
* isZero
.br
* isOpposite:
.br
* negate
.br
* double
.br
* add:
.br
* subtract:
.br
* addScalar:
.br
* subtractScalar:
.RE
.PP
.B
Multiplication
.RS 3
.br
* one
.br
* isOne
.br
* isMinusOne
.br
* multiply:
.br
* square
.br
* inverse
.br
* multiplyScalar:
.br
* divideScalar:
.br
* multiplyCoefficient:
.br
* divideCoefficient:
.br
* multiplyTerm:
.br
* divideTerm:
.br
* multiplyMonomial:
.br
* divideMonomial:
.RE
.PP
.B
Polynomial Division
.RS 3
.br
* remainder:quotient:
.br
* divide:
.RE
.PP
.B
Pseudo Division
.RS 3
.br
* pseudoRemainder:quotient:
.br
* pseudoRemainder:
.RE
.PP
.B
Contents and Primitive Parts
.RS 3
.br
* content
.br
* divideContent
.br
* coefficientContent
.br
* divideCoefficientContent
.br
* termContent
.br
* monomialContent
.RE
.PP
.B
Resultant and Greatest Common Divisor
.RS 3
.br
* gcd:
.br
* resultant:
.br
* resultant:wrt:
.br
* discriminant
.RE
.PP
.B
Counting Real Roots
.RS 3
.br
* numRealRoots
.br
* varRealRoots:
.RE
.PP
.B
Factoring
.RS 3
.br
* isSquareFree
.br
* factorSquareFree
.RE
.PP
.B
Truncation
.RS 3
.br
* truncateAtDegree:
.RE
.PP
.B
Characteristic
.RS 3
.br
* frobenius
.br
* frobeniusInverse
.RE
.PP
.B
Evaluation and Substitution
.RS 3
.br
* evaluate:
.br
* evaluate:at:
.br
* evaluateAll:
.br
* substitute:
.br
* substitute:by:
.br
* substituteAll:
.RE
.PP
.B
Derivation and Integration
.RS 3
.br
* derive
.br
* deriveWrt:
.br
* integrate
.br
* integrateWrt:
.RE
.PP
.B
Printing
.RS 3
.br
* printsLeadingSign
.br
* printsSum
.br
* printsProduct
.br
* printOn:
.RE
.SH Methods
.PP
scalar:
.RS 1
+
.B
scalar
:
.I
aScalar
.RE
.PP
Creates and returns a polynomial in the recursive, variable sparse and degree sparse representation, containing the scalar object
.I
aScalar
\&.
.PP
copy
.RS 1
-
.B
copy
.RE
.PP
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\&.
.PP
deepCopy
.RS 1
-
.B
deepCopy
.RE
.PP
Makes a full independent copy of the polynomial by copying all terms or monomials and by sending
.B
deepCopy
messages to the scalar objects\&. The original polynomial and the copy don\&'t share any scalars, terms or monomials\&.
.PP
empty
.RS 1
-
.B
empty
.RE
.PP
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\&.
.PP
scalarZero
.RS 1
-
.B
scalarZero
.RE
.PP
Returns the zero (base) scalar element\&.
.PP
termZero
.RS 1
-
.B
termZero
.RE
.PP
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)\&.
.PP
monomialZero
.RS 1
-
.B
monomialZero
.RE
.PP
Returns the zero monomial for an expanded polynomial\&.
.PP
hash
.RS 1
- (
unsigned
)
.B
hash
.RE
.PP
Returns a small integer that is the same for objects that are equal (in the sense of
.B
isEqual:
)\&.
.PP
isEqual:
.RS 1
- (
BOOL
)
.B
isEqual
:
.I
b
.RE
.PP
Whether the two objects are equal\&. Returns YES if the objects are pointer equal\&.
.PP
isRecursive
.RS 1
- (
BOOL
)
.B
isRecursive
.RE
.PP
Returns YES if the polynomial is in recursive representation\&. Implies that the polynomial is not in expanded representation\&.
.PP
isExpanded
.RS 1
- (
BOOL
)
.B
isExpanded
.RE
.PP
Returns YES if the polynomial is in expanded representation\&. Implies that the polynomial is not in recursive representation\&.
.PP
isVariableSparse
.RS 1
- (
BOOL
)
.B
isVariableSparse
.RE
.PP
Returns YES if the polynomial is variable sparse\&. Implies that the polynomial is not variable dense\&.
.PP
isVariableDense
.RS 1
- (
BOOL
)
.B
isVariableDense
.RE
.PP
Returns YES if the polynomial is variable dense\&. Implies that the polynomial is not variable sparse\&.
.PP
isDegreeDense
.RS 1
- (
BOOL
)
.B
isDegreeDense
.RE
.PP
Returns YES if the polynomial is degree dense\&. Implies that the polynomial is not degree sparse\&.
.PP
isDegreeSparse
.RS 1
- (
BOOL
)
.B
isDegreeSparse
.RE
.PP
Returns YES if the polynomial is degree sparse\&. Implies that the polynomial is not degree dense\&.
.PP
isUnivariate
.RS 1
- (
BOOL
)
.B
isUnivariate
.RE
.PP
Whether the number of symbols equals one\&.
.PP
inUnivariateDomain
.RS 1
- (
BOOL
)
.B
inUnivariateDomain
.RE
.PP
Whether the polynomial is variable dense and the number of symbols equals one\&.
.PP
isMultivariate
.RS 1
- (
BOOL
)
.B
isMultivariate
.RE
.PP
intValue
.RS 1
- (
int
)
.B
intValue
.RE
.PP
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\&.
.PP
intValue:
.RS 1
-
.B
intValue
:(int)
.I
aValue
.RE
.PP
Returns a polynomial (of the same representation as the polynomial that receives the message) with value equal to
.I
aValue
\&.
.PP
floatValue
.RS 1
- (
float
)
.B
floatValue
.RE
.PP
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\&.
.PP
floatValue:
.RS 1
-
.B
floatValue
:(float)
.I
aValue
.RE
.PP
Returns a polynomial (of the same representation as the polynomial that receives the message) with value equal to
.I
aValue
\&.
.PP
asScalar
.RS 1
-
.B
asScalar
.RE
.PP
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
.B
nil
\&.
.PP
asSymbol
.RS 1
-
.B
asSymbol
.RE
.PP
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
.B
nil
\&. The method returns
.B
nil
if the polynomial is a scalar that is a symbol\&.\&.\&.
.PP
asTerm
.RS 1
-
.B
asTerm
.RE
.PP
Returns, for a recursive polynomial that consists of a single term, a copy of that term\&. Returns
.B
nil
if the polynomial is zero (not considered to be a term) or a polynomial that consists of two or more terms\&.
.PP
asMonomial
.RS 1
-
.B
asMonomial
.RE
.PP
Returns, for an expanded polynomial that consists of a single monomial, a copy of that monomial\&. Returns
.B
nil
if the polynomial is zero (not considered to be a monomial) or a polynomial that consists of two or more monomials\&.
.PP
asCoefficient
.RS 1
-
.B
asCoefficient
.RE
.PP
This method applies only to recursive polynomials\&. If the polynomial is a term, this method returns a copy of its coefficient\&. Otherwise it returns
.B
nil
\&.
.PP
asNumerical
.RS 1
-
.B
asNumerical
.RE
.PP
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\&.
.PP
asModp:
.RS 1
-
.B
asModp
:(unsigned short)
.I
p
.RE
.PP
Returns a new polynomial, of the same representation as the original polynomial, but with the scalars replaced by their value modulo
.I
p
, a small prime number\&.
.PP
symbols
.RS 1
-
.B
symbols
.RE
.PP
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\&.
.PP
degree
.RS 1
- (
int
)
.B
degree
.RE
.PP
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\&.
.PP
order
.RS 1
- (
int
)
.B
order
.RE
.PP
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\&.
.PP
.B
See also:
termContent, monomialContent
.PP
numTerms
.RS 1
- (
int
)
.B
numTerms
.RE
.PP
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\&.
.PP
numMonomials
.RS 1
- (
int
)
.B
numMonomials
.RE
.PP
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\&.
.PP
removeTerm
.RS 1
-
.B
removeTerm
.RE
.PP
Removes (and returns) the leading non-zero term of the polynomial\&. Returns
.B
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\&.
.PP
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\&.
.PP
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
.B
eachTerm
returns all terms, including zero terms\&.
.PP
insertTerm:
.RS 1
-
.B
insertTerm
:
.I
aTerm
.RE
.PP
Inserts
.I
aTerm
into the recursive polynomial and returns
.B
self
\&. If the polynomial already contains a term with the same exponent, then the coefficients of the terms are added together\&. Otherwise,
.I
aTerm
is inserted in the collection of terms\&. In any case, after insertion,
.I
aTerm
belongs to the polynomial\&. To insert a term, the polynomial may not be a copy of another polynomial\&.
.PP
As always, if the exponent of the term is zero, the symbol of the term must be
.B
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\&.
.PP
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\&.
.PP
removeMonomial
.RS 1
-
.B
removeMonomial
.RE
.PP
Removes the leading monomial of the polynomial\&. Returns
.B
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\&.
.PP
insertMonomial:
.RS 1
-
.B
insertMonomial
:
.I
aMonomial
.RE
.PP
Inserts
.I
aMonomial
into the expanded polynomial and returns
.B
self
\&. If the polynomial already contains a monomial with the same terms, then the scalars of the monomials are added together\&. Otherwise,
.I
aMonomial
is inserted in the collection of monomials\&. In any case, after insertion,
.I
aMonomial
belongs to the polynomial\&. The polynomial may not be a copy of another polynomial\&.
.PP
eachTerm
.RS 1
-
.B
eachTerm
.RE
.PP
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
.B
removeTerm
)\&.
.PP
.B
See also:
CASequence
.PP
eachMonomial
.RS 1
-
.B
eachMonomial
.RE
.PP
Like
.B
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
.B
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
.B
removeMonomial
)\&.
.PP
.B
See also:
CASequence
.PP
eachSequence
.RS 1
-
.B
eachSequence
.RE
.PP
.B
Note:
Not implemented\&.
.PP
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
.I
monomials
, even for recursive polynomials\&.
.PP
The following example shows how to access the leading monomial of a recursive, non-zero polynomial (such a polynomial is
.I
not
a sum of monomials) :
.RS 3
aSequence = [aRecursivePolynomial eachSequence];
.br
aMember = [aSequence firstElement];
.br
while ([aMember isKindOfSequence]) aMember = [aMember firstElement];
.br
printf(\&"leading monomial is %s\&",[aMember str]);
.br
.RE
.PP
eachScalar
.RS 1
-
.B
eachScalar
.RE
.PP
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\&.
.PP
.B
Note:
The sequence returned by this method doesn\&'t respond to
.B
at:
messages\&.
.PP
eachCoefficient
.RS 1
-
.B
eachCoefficient
.RE
.PP
Returns, for a recursive and variable dense polynomial, a sequence of the coefficients of the terms in the polynomial\&.
.PP
makeDegreeDense
.RS 1
-
.B
makeDegreeDense
.RE
.PP
If the polynomial is degree dense, this method merely returns a copy of
.B
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\&.
.PP
makeDegreeSparse
.RS 1
-
.B
makeDegreeSparse
.RE
.PP
If the polynomial is degree sparse, this method merely returns a copy of
.B
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\&.
.PP
makeRecursive
.RS 1
-
.B
makeRecursive
.RE
.PP
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\&.
.PP
makeExpanded
.RS 1
-
.B
makeExpanded
.RE
.PP
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\&.
.PP
makeVariableSparse
.RS 1
-
.B
makeVariableSparse
.RE
.PP
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\&.
.PP
makeVariableDense
.RS 1
-
.B
makeVariableDense
.RE
.PP
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
.B
collect:
\&.
.PP
.B
See also:
collect
.PP
collect:
.RS 1
-
.B
collect
:
.I
symbols
.RE
.PP
.B
Note:
<<The case of
.I
symbols
a collection with less members than the number of variables of the polynomial is not yet implemented\&. Currenlty
.I
symbols
must contain the same number, or more symbols than the original polynomial>>
.PP
Returns, for a variable sparse or variable dense polynomial, a new variable dense polynomial in the symbols indicated by the collection
.I
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\&.
.PP
The following examples show how to convert a variable sparse polynomial into variable dense representation, how to convert two variable sparse polynomials into the
.I
same
variable dense representation, and finally how to change the variable order of a variable dense polynomial :
.RS 3
{
.br
dense = [sparse collect:[sparse symbols]];
.br
}
.br
.br
.RE
.RS 3
{
.br
symbols = [[a symbols] union:[b symbols]];
.br
c = [a collect:symbols];
.br
d = [b collect:symbols];
.br
}
.br
.br
.RE
.RS 3
{
.br
symbols = [[b symbols] copy];
.br
/* \&.\&.\&. do something with \&"symbols\&" here\&.\&.\&. */
.br
d = [b collect:symbols];
.br
}
.br
.br
.RE
.PP
leadingTerm
.RS 1
-
.B
leadingTerm
.RE
.PP
Returns the leading term of the (recursive) polynomial\&. Returns
.B
nil
if the polynomial is equal to zero\&.
.PP
leadingCoefficient
.RS 1
-
.B
leadingCoefficient
.RE
.PP
Returns the leading coefficient of the (recursive) polynomial\&. Returns
.B
nil
if the polynomial is equal to zero\&.
.PP
leadingSign
.RS 1
- (
int
)
.B
leadingSign
.RE
.PP
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\&.
.PP
leadingMonomial
.RS 1
-
.B
leadingMonomial
.RE
.PP
Returns the leading monomial of the polynomial (in expanded representation)\&. Returns
.B
nil
if the polynomial is equal to zero\&.
.PP
leadingScalar
.RS 1
-
.B
leadingScalar
.RE
.PP
Returns the scalar of the leading monomial of the polynomial\&. Returns
.B
nil
if the polynomial is equal to zero\&.
.PP
isMonic
.RS 1
- (
BOOL
)
.B
isMonic
.RE
.PP
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
.I
x
.I
y
+ 1 is monic in expanded representation, but is
.I
not
monic in recursive representation (because the leading coefficient is
.I
x
)\&. The method returns NO if the polynomial is equal to zero\&.
.PP
notMonic
.RS 1
- (
BOOL
)
.B
notMonic
.RE
.PP
Whether
.B
isMonic
returns NO\&.
.PP
makeMonic
.RS 1
-
.B
makeMonic
.RE
.PP
zero
.RS 1
-
.B
zero
.RE
.PP
Returns a copy of the zero polynomial (same representation as polynomial that receives the message)\&. The only difference with
.B
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
.B
zero
\&.
.PP
.B
See also:
empty
.PP
isZero
.RS 1
- (
BOOL
)
.B
isZero
.RE
.PP
Whether the object is equal to zero\&.
.PP
isOpposite:
.RS 1
- (
BOOL
)
.B
isOpposite
:
.I
b
.RE
.PP
Whether the object is the opposite of
.I
b
\&.
.PP
negate
.RS 1
-
.B
negate
.RE
.PP
Returns the opposite of the object\&.
.PP
double
.RS 1
-
.B
double
.RE
.PP
Returns a new object, equal to the object multiplied by two i\&.e\&., added to itself\&.
.PP
add:
.RS 1
-
.B
add
:
.I
b
.RE
.PP
Adds
.I
b
to the object\&. Returns a new object\&.
.PP
subtract:
.RS 1
-
.B
subtract
:
.I
b
.RE
.PP
Subtracts
.I
b
from the object\&. Returns a new object\&.
.PP
addScalar:
.RS 1
-
.B
addScalar
:
.I
s
.RE
.PP
Returns a new polynomial; adds the (base) scalar
.I
s
to the original polynomial\&.
.PP
subtractScalar:
.RS 1
-
.B
subtractScalar
:
.I
s
.RE
.PP
Returns a new polynomial; subtracts the (base) scalar
.I
s
to the original polynomial\&.
.PP
one
.RS 1
-
.B
one
.RE
.PP
Returns a copy of the unity polynomial (same representation as polynomial that receives the message)\&.
.PP
isOne
.RS 1
- (
BOOL
)
.B
isOne
.RE
.PP
Whether the polynomial is equal to one\&.
.PP
isMinusOne
.RS 1
- (
BOOL
)
.B
isMinusOne
.RE
.PP
Whether the polynomial is equal to minus one\&.
.PP
multiply:
.RS 1
-
.B
multiply
:
.I
b
.RE
.PP
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
.B
square
\&.
.PP
square
.RS 1
-
.B
square
.RE
.PP
Returns a new polynomial\&. Computes the square of the polynomial by the classical polynomial multiplication algorithm using symmetry\&.
.PP
inverse
.RS 1
-
.B
inverse
.RE
.PP
Returns a new polynomial that is the inverse of the polynomial, or
.B
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\&.
.PP
multiplyScalar:
.RS 1
-
.B
multiplyScalar
:
.I
s
.RE
.PP
Multiplies by the scalar
.I
s
\&. Returns a new object\&.
.PP
divideScalar:
.RS 1
-
.B
divideScalar
:
.I
s
.RE
.PP
Exact division by the scalar
.I
s
\&. Returns a new object, or
.B
nil
if the division is not exact\&.
.PP
multiplyCoefficient:
.RS 1
-
.B
multiplyCoefficient
:
.I
aCoefficient
.RE
.PP
Multiplies the (recursive and variable dense) polynomial by
.I
aCoefficient
and returns a new object\&. What
.I
aCoefficient
means, depends on the representation of the polynomial\&. If it is variable dense and univariate, then
.I
aCoefficient
must be a scalar object\&. If it is variable dense and multivariate, then
.I
aCoefficient
must be again a variable dense polynomial in a variable less\&. The method is
.I
not
implemented in the variable sparse case; you can use
.B
multiplyScalar:
or
.B
multiply:
for these polynomials\&.
.PP
divideCoefficient:
.RS 1
-
.B
divideCoefficient
:
.I
aCoefficient
.RE
.PP
Exact division of the (recursive and variable dense) polynomial by
.I
aCoefficient
; returns a new object or
.B
nil
if the division is not exact or if it fails\&. If the polynomial is univariate, then
.I
aCoefficient
must be a scalar object\&. If it is multivariate, then
.I
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
.B
divideScalar:
or
.B
divide:
\&.
.PP
multiplyTerm:
.RS 1
-
.B
multiplyTerm
:
.I
aTerm
.RE
.PP
Multiplies the (recursive) polynomial by the term
.I
aTerm
; returns a new object\&. This method is implemented for both variable sparse and variable dense
.I
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\&.
.PP
divideTerm:
.RS 1
-
.B
divideTerm
:
.I
aTerm
.RE
.PP
(Exact) Division of the polynomial by
.I
aTerm
; returns a new polynomial\&. The division fails (and this method returns
.B
nil
) if one of the terms of the polynomial is not divisible by
.I
aTerm
\&. This method is implemented for both variable sparse and variable dense
.I
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)\&.
.PP
multiplyMonomial:
.RS 1
-
.B
multiplyMonomial
:
.I
s
.RE
.PP
Multiplies by the monomial
.I
s
\&. Returns a new object\&.
.PP
divideMonomial:
.RS 1
-
.B
divideMonomial
:
.I
s
.RE
.PP
Exact division by the monomial
.I
s
\&. Returns a new object, or
.B
nil
if the division is not exact\&.
.PP
remainder:quotient:
.RS 1
-
.B
remainder
:
.I
b
.B
quotient
:(id *)
.I
q
.RE
.PP
Returns new polynomials
.I
R
and, by reference,
.I
Q
such that
.I
self
=
.I
Q b
+
.I
R
\&. If
.I
q
is a NULL pointer, the quotient
.I
Q
is not computed\&. Returns
.B
nil
(and sets the value pointed to by
.I
q
to
.B
nil
) if the polynomial division fails\&.
.RS 3
id q,r;
.br
.br
r = [self remainder:b quotient:&q];
.br
.br
/* do something with r and q */
.br
.br
.RE
.PP
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
.B
pseudoRemainder:quotient:
for more details\&.
.PP
divide:
.RS 1
-
.B
divide
:
.I
b
.RE
.PP
Returns the exact quotient (a new polynomial) of the polynomial division\&. Returns
.B
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\&.
.PP
pseudoRemainder:quotient:
.RS 1
-
.B
pseudoRemainder
:
.I
b
.B
quotient
:(id *)
.I
q
.RE
.PP
If the polynomials are variable sparse or expanded, they are temporarily converted into variable dense and recursive representation for this operation\&. If
.I
n
and
.I
m
are the degrees of
.B
self
and
.I
b
respectively, and if
.I
c
is the leading coefficient of
.I
b
, than this method computes the pseudo-remainder
.I
R
and, if
.I
q
is not a NULL pointer, the pseudo-quotient
.I
Q
such that
.I
c
^(n-m+1)
.I
self
=
.I
Q b
+
.I
R
\&. Returns
.B
nil
if the pseudo-division fails\&.
.PP
pseudoRemainder:
.RS 1
-
.B
pseudoRemainder
:
.I
b
.RE
.PP
Computes the pseudo-remainder of the polynomials by invoking
.B
pseudoRemainder:quotient:
with a NULL argument\&.
.PP
content
.RS 1
-
.B
content
.RE
.PP
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
.B
nil
\&.
.PP
divideContent
.RS 1
-
.B
divideContent
.RE
.PP
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
.B
content
\&.
.PP
coefficientContent
.RS 1
-
.B
coefficientContent
.RE
.PP
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
.B
nil
\&.
.PP
divideCoefficientContent
.RS 1
-
.B
divideCoefficientContent
.RE
.PP
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
.B
coefficientContent
\&.
.PP
termContent
.RS 1
-
.B
termContent
.RE
.PP
Returns for a variable dense and recursive polynomial, the
.I
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
.B
order
of the polynomial\&.
.PP
.B
See also:
order
.PP
monomialContent
.RS 1
-
.B
monomialContent
.RE
.PP
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
.B
nil
\&.
.PP
gcd:
.RS 1
-
.B
gcd
:
.I
b
.RE
.PP
Returns a new polynomial that is the gcd of the polynomials\&. For recursive and variable dense polynomials over a field, the method computes the
.I
monic
gcd of the polynomials by the euclidean algorithm\&. Over an integral domain, the method computes the
.I
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)\&.
.PP
resultant:
.RS 1
-
.B
resultant
:
.I
b
.RE
.PP
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\&.
.PP
resultant:wrt:
.RS 1
-
.B
resultant
:
.I
b
.B
wrt
:(STR)
.I
aSymbol
.RE
.PP
Returns the resultant of the pair of polynomials with respect to the variable named
.I
aSymbol
\&.
.PP
discriminant
.RS 1
-
.B
discriminant
.RE
.PP
Returns the discriminant of the polynomial i\&.e\&. the resultant of the polynomial and its derivative\&.
.PP
.B
Note:
This is actually the discriminant up to a scalar\&. Scalar factor will change in future\&.
.PP
numRealRoots
.RS 1
- (
int
)
.B
numRealRoots
.RE
.PP
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\&.
.PP
varRealRoots:
.RS 1
- (
int
)
.B
varRealRoots
:
.I
g
.RE
.PP
Returns the variation of real roots over the polynomial
.I
g
\&.
.PP
isSquareFree
.RS 1
- (
BOOL
)
.B
isSquareFree
.RE
.PP
Returns YES if the polynomial is squarefree i\&.e\&., if the polynomial and its derivative are coprime\&.
.PP
factorSquareFree
.RS 1
-
.B
factorSquareFree
.RE
.PP
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\&.
.PP
truncateAtDegree:
.RS 1
-
.B
truncateAtDegree
:(int)
.I
d
.RE
.PP
Drops terms or monomials of degree greater than
.I
d
\&. Returns a new polynomial\&.
.PP
frobenius
.RS 1
-
.B
frobenius
.RE
.PP
Returns a new polynomial that is the image of the polynomial under the frobenius map by sending
.B
frobenius
messages to each term or monomial\&.
.PP
frobeniusInverse
.RS 1
-
.B
frobeniusInverse
.RE
.PP
Returns a new polynomial that is the image of the polynomial under the inverse of the frobenius map by sending
.B
frobeniusInverse
messages to each term or monomial\&. Returns
.B
nil
if the polynomial is not the image of a polynomial under the frobenius map\&.
.PP
evaluate:
.RS 1
-
.B
evaluate
:
.I
aScalar
.RE
.PP
.B
Note:
Not implemented\&.
.PP
Replaces the main variable of the polynomial by
.I
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
.I
aScalar
\&.
.PP
evaluate:at:
.RS 1
-
.B
evaluate
:(STR)
.I
aSymbol
.B
at
:
.I
aScalar
.RE
.PP
.B
Note:
Not implemented\&.
.PP
Returns a new polynomial object, obtained by replacing the variable named
.I
aSymbol
by
.I
aScalar
\&.
.PP
evaluateAll:
.RS 1
-
.B
evaluateAll
:
.I
cltnOfScalars
.RE
.PP
Returns a new scalar object, obtained by replacing all variables of the polynomial by the scalar objects in the collection
.I
cltnOfScalars
i\&.e\&., the first member in the collection returned by
.B
variables
is replaced by the first member in
.I
cltnOfScalars
and so on\&. Variable sparse or expanded polynomials are temporarily converted into recursive and variable dense representation by this method\&.
.PP
substitute:
.RS 1
-
.B
substitute
:
.I
aPolynomial
.RE
.PP
Returns a new (variable dense) polynomial, obtained by replacing the main variable of a variable dense polynomial by
.I
aPolynomial
\&.
.PP
substitute:by:
.RS 1
-
.B
substitute
:(STR)
.I
aSymbol
.B
by
:
.I
aPolynomial
.RE
.PP
Returns a new polynomial, obtained by replacing the variable named
.I
aSymbol
by
.I
aPolynomial
\&. Implemented for recursive and variable sparse polynomials only\&.
.PP
substituteAll:
.RS 1
-
.B
substituteAll
:
.I
cltnOfPolynomials
.RE
.PP
.B
Note:
Not implemented\&.
.PP
Returns a new polynomial, obtained by replacing all variables simultaneously by the polynomials in the collection
.I
cltnOfPolynomials
\&.
.PP
Change of Variables - Permuting (Swapping) Variables = substituteAll
.PP
derive
.RS 1
-
.B
derive
.RE
.PP
Returns the derivative of a variable dense polynomial with respect to the main variable (the last member in the collection returned by
.B
variables
)\&.
.PP
deriveWrt:
.RS 1
-
.B
deriveWrt
:(STR)
.I
aSymbol
.RE
.PP
.B
Note:
Not implemented\&.
.PP
Returns the derivative of the polynomial with respect to the variable named
.I
aSymbol
\&. For example, to integrate a polynomial with respect to
.I
x
:
.RS 3
pdx = [p deriveWrt:\&"x\&"];
.br
.RE
.PP
integrate
.RS 1
-
.B
integrate
.RE
.PP
Integrates a variable dense polynomial with respect to the main variable (the last member in the collection returned by
.B
variables
)\&. Because the resulting polynomial is a polynomial over the same domain of scalars as the integrandum, this operation might fail and returns
.B
nil
if the scalars are not taken from a field\&.
.PP
integrateWrt:
.RS 1
-
.B
integrateWrt
:(STR)
.I
aSymbol
.RE
.PP
.B
Note:
Not implemented\&.
.PP
Integrates the polynomial with respect to the variable named
.I
aSymbol
\&.
.PP
printsLeadingSign
.RS 1
- (
BOOL
)
.B
printsLeadingSign
.RE
.PP
Whether the polynomial prints a leading minus sign\&.
.PP
printsSum
.RS 1
- (
BOOL
)
.B
printsSum
.RE
.PP
Whether the polynomial prints multiple terms or monomials separated by a plus or minus signs\&.
.PP
printsProduct
.RS 1
- (
BOOL
)
.B
printsProduct
.RE
.PP
Whether the polynomial prints a single product\&.
.PP
printOn:
.RS 1
-
.B
printOn
:(IOD)
.I
aFile
.RE
.PP
Prints the polynomial, by sending
.B
printOn:
messages to the terms or monomials\&.