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

Monomial

Inherits from: CAObject

Maturity Index: Relatively mature

Class Description

A monomial consists of a scalar object scalar multiplied by a product of terms; each term consists of a scalar coefficient multiplied by a symbol raised to a nonnegative exponent (see the documentation on Term).  The degree of a monomial is the sum of the exponents of its terms.  A monomial can be either variable sparse or variable dense : the terms of a variable dense monomial are represented by a dense array of exponents, where the size of the array is equal to the number of symbols.  The exponent of a term can be equal to zero.  In a variable sparse monomial, terms with exponent equal to zero are not stored.

Scalar of a Monomial

When a term is inserted into a monomial (see insertTerm:), its coefficient is multiplied together with the scalar of the monomial; it follows that a monomial consists internally of a scalar multiplied by a product of monic terms (a 'power product').  The methods leadingTerm, removeTerm, eachTerm etc. return monic terms.  A monomial is said to be monic if its scalar is equal to one.

Symbols and Variable Ordering

For a variable dense monomial, 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.  Note that, in both cases - variable sparse or variable dense -, the collection of symbols contains the actual set of symbols (those that actually occur in the monomial with nonzero exponent) as a subset.   See the documentation on findSymbols.  The variable ordering imposed by the ordering of the collection of symbols is called lexicographic (currently the variable ordering is always lexicographic).  Monomials can be compared with respect to this ordering.

Conversion between Representations

It suffices to remove terms from a monomial in one representation and to insert them into another; abstractly, both kind of monomials, are collections of terms.

sparse = [Monomial scalar:[dense scalar]];
while (term = [dense removeTerm]) [sparse insertTerm:term];

The example shows how to, destructively, convert from the variable dense into the variable sparse representation (see also makeVariableSparse).  Note that when you create a variable sparse monomial, you don't have to specify the symbols in advance. 

dense = [Monomial scalar:[sparse scalar] symbols:[sparse findSymbols]];
while (term = [sparse removeTerm]) [dense insertTerm:term];

The above example shows how to, destructively, convert from the variable sparse into the variable dense representation  (see also makeVariableDense).  To create a variable dense monomial, you have to fix the symbols prior to inserting terms.

Polynomials

A polynomial in expanded (or 'distributed') representation is a sum of monomials.  Although a polynomial in recursive representation is not a sum of monomials (it's a sum of terms), recursive polynomials can to some extent be manipulated as sequences of monomials (see Polynomial's method eachSequence).  Note that in the recursive case, the scalars for monomials are taken from the (base) scalar ring.

The monomials in a variable sparse polynomial, are variable sparse.  Likewise, the monomials in a variable dense polynomial, are variable dense.  For a degree dense polynomial, the scalars of the monomials can be zero, while for a degree sparse polynomial they cannot.

Method types

Creation	- scalar:
	- scalar:symbols:
	- empty
	- copy
	- deepCopy

Coercion	- intValue
	- intValue:
	- floatValue
	- floatValue:
	- asScalar
	- asSymbol

Identity	- scalar
	- termOne
	- isMonic
	- isVariableSparse
	- isVariableDense
	- degree
	- numTerms
	- isTerm
	- isEqual:
	- hash

Variable Ordering	- symbols
	- isOrderDegreeCompatible
	- isOrderReverseDegreeCompatible
	- compareTerms:

Inserting and Removing	- removeTerm
	- insertTerm:

Accessing Terms	- eachTerm
	- leadingTerm

Addition	- zero
	- isZero
	- negate
	- double
	- add:
	- subtract:

Multiplication	- one
	- isOne
	- isMinusOne
	- square
	- multiply:
	- multiplyScalar:
	- divideScalar:
	- divide:
	- divideTerms:

Greatest Common Divisor	- gcd:
	- lcm:

Characteristic	- frobenius
	- frobeniusInverse

Printing	- printsLeadingSign
	- printsSum
	- printsProduct
	- printOn:

Methods

scalar:
+scalar:aScalar

Creates a new variable sparse monomial.  Sets the scalar equal to aScalar.

scalar:symbols:
+scalar:aScalarsymbols:aCltn

Creates a new variable dense monomial.  Sets the scalar equal to aScalar and fixes the symbols to aCltn.  The collection of symbols must not be empty.

empty
-empty

Creates a new monomial with scalar equal to one and empty sequence of terms.  The representation of the monomial is identical to that of the original monomial.

copy
-copy

Makes a copy of the terms of the monomial.

deepCopy
-deepCopy

Makes a deepCopy of the terms and the scalar of the monomial.

intValue
- (int)intValue

Returns the intValue of the scalar of the monomial, if all terms are trivial.  If not, generates an error message.

intValue:
-intValue:(int)aValue

Returns a new monomial with a scalar whose value as int is equal to aValue.  All terms in this monomial are trivial.

floatValue
- (float)floatValue

Returns the floatValue of the scalar of the monomial, if all terms are trivial.  If not, generates an error message.

floatValue:
-floatValue:(float)aValue

Returns a new monomial with a scalar whose value as float is equal to aValue.  All terms in this monomial are trivial.

asScalar
-asScalar

Returns, if all the terms in the monomial are trivial (have exponent equal to zero), a new reference to the scalar of the monomial.  Otherwise returns nil.

asSymbol
-asSymbol

Returns, if the scalar of the monomial is equal to one and if the monomial contains exactly one term whose exponent is equal to one, a new reference to the symbol of that term.  Otherwise returns nil.

scalar
-scalar

Returns the scalar of the monomial. 

termOne
-termOne

Returns the trivial term.  

isMonic
- (BOOL)isMonic

Returns YES if the scalar of the monomial is equal to one.

isVariableSparse
- (BOOL)isVariableSparse

Returns YES if the terms of the monomial are variable sparse i.e., whether symbols raised to exponent zero are ignored and whether the collection of allowed symbols is dynamically adjusted when terms are inserted.

isVariableDense
- (BOOL)isVariableDense

Returns YES if the terms of the monomial are variable dense i.e., whether symbols raised to exponent zero are stored and whether the collection of allowed symbols is fixed.

degree
- (int)degree

Returns the sum of the exponents of the terms in the monomial.  Returns minus one if the monomial is equal to zero.

numTerms
- (int)numTerms

Returns the number of terms with non-zero exponent in the monomial.  The total number of terms in a variable dense monomial is equal to the number of symbols.  Note that eachTerm returns a sequence of all terms, trivial or not. 

isTerm
- (BOOL)isTerm

Whether the monomial consists of a single term.

isEqual:
- (BOOL)isEqual:aMonomial

Returns YES if the scalars and the terms of the monomial are equal to each other.  The monomials must be in the same representation.

hash
- (unsigned)hash

Returns a hash value for the monomial.

symbols
-symbols

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

isOrderDegreeCompatible
- (BOOL)isOrderDegreeCompatible

Should return YES if, when the monomial a is less than the monomial b, the degree of a is less than the degree of b.  Currently, the order is degree compatible only for univariate, variable dense monomials. 

isOrderReverseDegreeCompatible
- (BOOL)isOrderReverseDegreeCompatible

Should return YES if, when the monomial a is less than the monomial b, the degree of a is greater than the degree of b.  Currently, there is no such order. 

compareTerms:
- (int)compareTerms:aMonomial

Compares the terms (symbols and exponents) of the monomials; the scalars of the monomials are not taken into account.  Returns zero if the symbols and exponents of the terms are equal; returns -1 if the monomial is less than aMonomial, and +1 if it is greater than aMonomial.

If the monomials are variable dense, the first symbol in the collection of symbols is taken to be smaller than symbols with higher index in the array of symbols.  This method compares with respect to the lexicographic order : it starts comparing the smallest symbols, and as long as exponents are equal, it works towards larger symbols (those at the end of the collection of symbols).

If the monomials are variable sparse, the method also compares lexicographically, but now the smallest symbol, is the one that is smallest with respect to Symbol's compare:.  If the collection of symbols for a variable dense monomial is ordered alphabetically, the variable sparse and variable dense orderings coincide.

removeTerm
-removeTerm

Removes the leading term (first term with non-zero exponent) of the monomial or returns nil if there is no such term.  The coefficient of this term is equal to one.  The reference count of the monomial must be equal to one.

See also: leadingTerm, eachTerm

insertTerm:
-insertTerm:aTerm

Inserts aTerm in the product of terms and returns self.  The reference count of the monomial must be equal to one.

If the coefficient of the term is zero, this method empties the sequence of terms and sets the scalar to zero, as if the monomial were multiplied by zero.  Otherwise, the methods multiplies the coefficient of the term and the scalar of the monomial together, and, if the monomial doesn't contain a term with symbol equal to that of aTerm, the method inserts a (monic) term in the ordered sequence of terms.  If there is a term in the same symbol, the method adds the exponent of aTerm to it.

eachTerm
-eachTerm

Returns a sequence of terms.  The coefficient of each term is equal to one.  The scalar of the monomial itself is obtained by sending scalar to the monomial.  If the monomial is variable dense, the sequence also contains the terms whose exponent is equal to zero.

leadingTerm
-leadingTerm

Returns the leading term of the monomial i.e., the first term with a non-zero exponent.  The coefficient of this term is equal to one.  Returns nil if there is no such term in the monomial.

zero
-zero

isZero
- (BOOL)isZero

Returns YES if the scalar object is zero.

negate
-negate

double
-double

add:
-add:b

subtract:
-subtract:b

one
-one

Returns a monomial with scalar equal to one and containing no (nontrivial) terms.

isOne
- (BOOL)isOne

Whether there are only trivial terms and the scalar is equal to one.

isMinusOne
- (BOOL)isMinusOne

square
-square

multiply:
-multiply:b

multiplyScalar:
-multiplyScalar:s

Multiplies the scalar of the monomial by s and copies the terms.

divideScalar:
-divideScalar:s

Divides scalar by s and copies terms.  Returns nil if the division fails or if it's not exact.

divide:
-divide:aMonomial

Divides the scalars and the terms of the monomials.  Returns nil if either of the scalar or term division is not exact.

divideTerms:
-divideTerms:aMonomial

Divides the terms of the monomials by the terms of aMonomial.  Returns a new monomial with scalar equal to the scalar of the dividend.  Returns nil if the division of terms is not exact.

gcd:
-gcd:aMonomial

Returns a new monomial that is the monic greatest common divisor of the monomials, ie. the greatest common divisor of the terms of the monomials.

lcm:
-lcm:aMonomial

Returns a new monomial that is the monic least common multiple of the monomials, ie. the least common multiple of the terms of the monomials.

frobenius
-frobenius

Returns a new monomial by sending a frobenius message to the scalar of the monomial and by raising the terms in the monomial to the p-th power (p is equal to the scalar's characteristic).

frobeniusInverse
-frobeniusInverse

Returns a new monomial by sending a frobeniusInverse message to the scalar of the monomial and by extracting the p-th root of the terms in the monomial to a power (where p is equal to the scalar's characteristic).  Returns nil if the monomial is not a p-th power.

printsLeadingSign
- (BOOL)printsLeadingSign

Whether the monomial prints a leading minus sign.

printsSum
- (BOOL)printsSum

Whether the monomial prints a sum.

printsProduct
- (BOOL)printsProduct

Whether the monomial prints a single product.

printOn:
-printOn:(IOD)aFile

Prints the monomial to aFile by sending printOn: to the scalar and terms.