All Classes Functions Friends
Public Member Functions | Public Attributes | Static Public Attributes | Friends | List of all members
SparseUnivariatePolynomial< Ring > Class Template Reference
The concrete class SparseUnivariatePolynomial< Ring > inherits from BPASUnivariatePolynomial and implements a univariate polynomial ring over an arbitrary BPAS ring with a sparse representation. In other words, this is a template class, while the coefficient ring satisfies the specifications of a BPASRing. It overrides all the public member functions of BPASRing, BPASPolynomial and BPASUnivariatePolynomial. One can construct a SparseUnivariatePolynomial< Ring > object either by initializing a zero polynomial or from another SparseUnivariatePolynomial< Ring > object. Other operations include resultant and sub-resultant chain computations.
Inheritance diagram for SparseUnivariatePolynomial< Ring >:
BPASUnivariatePolynomial BPASPolynomial BPASRing

Public Member Functions

 SparseUnivariatePolynomial ()
 
 SparseUnivariatePolynomial (const SparseUnivariatePolynomial< Ring > &b)
 
 SparseUnivariatePolynomial (Integer c)
 
 SparseUnivariatePolynomial (RationalNumber c)
 
 SparseUnivariatePolynomial (ComplexRationalNumber c)
 
 SparseUnivariatePolynomial (DenseUnivariateIntegerPolynomial b)
 
 SparseUnivariatePolynomial (DenseUnivariateRationalPolynomial b)
 
 ~SparseUnivariatePolynomial ()
 
int numberOfTerms ()
 
int degree ()
 
Ring leadingCoefficient ()
 
Ring coefficient (int k)
 
void setCoefficient (int e, Ring c)
 
std::string variable ()
 
void setVariableName (std::string c)
 
SparseUnivariatePolynomial
< Ring > & 
operator= (SparseUnivariatePolynomial< Ring > b)
 
bool operator!= (SparseUnivariatePolynomial< Ring > &b)
 
bool operator== (SparseUnivariatePolynomial< Ring > &b)
 
bool operator== (DenseUnivariateRationalPolynomial &b)
 
bool operator== (DenseUnivariateIntegerPolynomial &b)
 
bool isZero ()
 
void zero ()
 
bool isOne ()
 
void one ()
 
bool isNegativeOne ()
 
void negativeOne ()
 
int isConstant ()
 
Ring convertToConstant ()
 
Ring content ()
 
SparseUnivariatePolynomial< Ring > operator^ (int e)
 
SparseUnivariatePolynomial
< Ring > & 
operator^= (int e)
 
SparseUnivariatePolynomial< Ring > operator<< (int k)
 
SparseUnivariatePolynomial
< Ring > & 
operator<<= (int k)
 
SparseUnivariatePolynomial< Ring > operator>> (int k)
 
SparseUnivariatePolynomial
< Ring > & 
operator>>= (int k)
 
SparseUnivariatePolynomial< Ring > operator+ (SparseUnivariatePolynomial< Ring > &b)
 
SparseUnivariatePolynomial
< Ring > & 
operator+= (SparseUnivariatePolynomial< Ring > b)
 
SparseUnivariatePolynomial< Ring > operator+ (Ring e)
 
SparseUnivariatePolynomial
< Ring > & 
operator+= (Ring e)
 
SparseUnivariatePolynomial< Ring > operator- ()
 
SparseUnivariatePolynomial< Ring > operator- (SparseUnivariatePolynomial< Ring > &b)
 
SparseUnivariatePolynomial
< Ring > & 
operator-= (SparseUnivariatePolynomial< Ring > b)
 
SparseUnivariatePolynomial< Ring > operator- (Ring e)
 
SparseUnivariatePolynomial
< Ring > & 
operator-= (Ring e)
 
SparseUnivariatePolynomial< Ring > operator* (SparseUnivariatePolynomial< Ring > b)
 
SparseUnivariatePolynomial
< Ring > & 
operator*= (SparseUnivariatePolynomial< Ring > b)
 
SparseUnivariatePolynomial< Ring > operator* (Ring c)
 
SparseUnivariatePolynomial< Ring > operator* (sfixn e)
 
SparseUnivariatePolynomial
< Ring > & 
operator*= (Ring c)
 
SparseUnivariatePolynomial
< Ring > & 
operator*= (sfixn e)
 
SparseUnivariatePolynomial< Ring > operator/ (SparseUnivariatePolynomial< Ring > &b)
 
SparseUnivariatePolynomial
< Ring > & 
operator/= (SparseUnivariatePolynomial< Ring > b)
 
SparseUnivariatePolynomial< Ring > operator/ (Ring e)
 
SparseUnivariatePolynomial
< Ring > & 
operator/= (Ring e)
 
void negate ()
 
SparseUnivariatePolynomial< Ring > monicDivide (SparseUnivariatePolynomial< Ring > &b)
 
SparseUnivariatePolynomial< Ring > monicDivide (SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem)
 
SparseUnivariatePolynomial< Ring > lazyPseudoDivide (SparseUnivariatePolynomial< Ring > &b, Ring *c, Ring *d=NULL)
 
SparseUnivariatePolynomial< Ring > lazyPseudoDivide (SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem, Ring *c, Ring *d)
 
SparseUnivariatePolynomial< Ring > pseudoDivide (SparseUnivariatePolynomial< Ring > &b, Ring *d=NULL)
 
SparseUnivariatePolynomial< Ring > pseudoDivide (SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem, Ring *d)
 
void differentiate (int k)
 
SparseUnivariatePolynomial< Ring > integrate ()
 
bool isTrailingCoefficientZero ()
 
Ring evaluate (Ring x)
 
std::vector
< SparseUnivariatePolynomial
< Ring > > 
subresultantChain (SparseUnivariatePolynomial< Ring > &q)
 
SparseUnivariatePolynomial< Ring > resultant (SparseUnivariatePolynomial< Ring > &q)
 
SparseUnivariatePolynomial< Ring > gcd (SparseUnivariatePolynomial< Ring > &q)
 
std::vector
< SparseUnivariatePolynomial
< Ring > > 
squareFree ()
 
DenseUnivariateRationalPolynomial convertToDUQP ()
 
DenseUnivariateIntegerPolynomial convertToDUZP ()
 
- Public Member Functions inherited from BPASUnivariatePolynomial
BPASUnivariatePolynomialoperator+ (DataType)
 
BPASUnivariatePolynomialoperator+= (DataType)
 
BPASUnivariatePolynomialoperator- (DataType)
 
BPASUnivariatePolynomialoperator-= (DataType)
 
BPASUnivariatePolynomialoperator* (DataType)
 
BPASUnivariatePolynomialoperator*= (DataType)
 
BPASUnivariatePolynomialoperator/ (DataType)
 
BPASUnivariatePolynomialoperator/= (DataType)
 
BPASUnivariatePolynomialoperator<< (int)
 
BPASUnivariatePolynomialoperator<<= (int)
 
BPASUnivariatePolynomialoperator>> (int)
 
BPASUnivariatePolynomialoperator>>= (int)
 
BPASUnivariatePolynomialmonicDivide (BPASUnivariatePolynomial &)
 
BPASUnivariatePolynomialmonicDivide (BPASUnivariatePolynomial &, BPASUnivariatePolynomial *)
 
BPASUnivariatePolynomiallazyPseudoDivide (BPASUnivariatePolynomial &, DataType *, DataType *)
 
BPASUnivariatePolynomiallazyPseudoDivide (BPASUnivariatePolynomial &, BPASUnivariatePolynomial *, DataType *, DataType *)
 
BPASUnivariatePolynomialpseudoDivide (BPASUnivariatePolynomial &, DataType *)
 
BPASUnivariatePolynomialpseudoDivide (BPASUnivariatePolynomial &, BPASUnivariatePolynomial *, DataType *)
 
DataType content ()
 
BPASUnivariatePolynomialgcd (BPASUnivariatePolynomial &)
 
std::vector
< BPASUnivariatePolynomial & > 
squareFree ()
 
DataType leadingCoefficient ()
 
DataType coefficient (int)
 
void setCoefficient (int, DataType)
 
DataType evaluate (DataType)
 
- Public Member Functions inherited from BPASPolynomial
BPASPolynomialoperator= (BPASPolynomial &)
 
BPASPolynomialoperator+ (BPASPolynomial &)
 
BPASPolynomialoperator+= (BPASPolynomial &)
 
BPASPolynomialoperator- (BPASPolynomial &)
 
BPASPolynomialoperator- ()
 
BPASPolynomialoperator-= (BPASPolynomial &)
 
BPASPolynomialoperator* (BPASPolynomial &)
 
BPASPolynomialoperator*= (BPASPolynomial &)
 
BPASPolynomialoperator/ (BPASPolynomial &)
 
BPASPolynomialoperator/= (BPASPolynomial &)
 
BPASPolynomialoperator^ (int)
 
bool operator== (BPASPolynomial &)
 
bool operator!= (BPASPolynomial &)
 

Public Attributes

int characteristic
 

Static Public Attributes

static bool isPrimeField
 
static bool isComplexField
 
- Static Public Attributes inherited from BPASRing
static int characteristic
 
static bool isPrimeField
 
static bool isComplexField
 

Friends

SparseUnivariatePolynomial< Ring > operator+ (Ring c, SparseUnivariatePolynomial< Ring > p)
 
SparseUnivariatePolynomial< Ring > operator- (Ring c, SparseUnivariatePolynomial< Ring > p)
 
SparseUnivariatePolynomial< Ring > operator* (Ring e, SparseUnivariatePolynomial< Ring > p)
 
SparseUnivariatePolynomial< Ring > operator* (sfixn e, SparseUnivariatePolynomial< Ring > p)
 
SparseUnivariatePolynomial< Ring > operator/ (Ring e, SparseUnivariatePolynomial< Ring > p)
 
std::ostream & operator<< (std::ostream &out, SparseUnivariatePolynomial< Ring > b)
 

Constructor & Destructor Documentation

template<class Ring>
SparseUnivariatePolynomial< Ring >::SparseUnivariatePolynomial ( )
inline

Construct a polynomial

Parameters
template<class Ring>
SparseUnivariatePolynomial< Ring >::SparseUnivariatePolynomial ( const SparseUnivariatePolynomial< Ring > &  b)
inline

Copy constructor

Parameters
b,:A sparse univariate polynomial
template<class Ring>
SparseUnivariatePolynomial< Ring >::~SparseUnivariatePolynomial ( )
inline

Destroy the polynomial

Parameters

Member Function Documentation

template<class Ring>
Ring SparseUnivariatePolynomial< Ring >::coefficient ( int  k)
inline

Get a coefficient

Parameters
k,:The exponent
template<class Ring>
Ring SparseUnivariatePolynomial< Ring >::content ( )
inline

Content of the polynomial

Parameters
template<class Ring>
Ring SparseUnivariatePolynomial< Ring >::convertToConstant ( )
inline

Convert to a constant

Parameters
template<class Ring>
int SparseUnivariatePolynomial< Ring >::degree ( )
inlinevirtual

Get the degree of the polynomial

Parameters

Implements BPASUnivariatePolynomial.

template<class Ring>
void SparseUnivariatePolynomial< Ring >::differentiate ( int  k)
inlinevirtual

Compute k-th derivative

Parameters
k,:k-th derivative

Implements BPASUnivariatePolynomial.

template<class Ring>
Ring SparseUnivariatePolynomial< Ring >::evaluate ( Ring  x)
inline

Evaluate f(x)

Parameters
x,:Evaluation point
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::gcd ( SparseUnivariatePolynomial< Ring > &  q)
inline

GCD(p, q)

Parameters
q,:The other polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::integrate ( )
inline

Compute integral with constant of integration set to 0

Parameters
template<class Ring>
int SparseUnivariatePolynomial< Ring >::isConstant ( )
inlinevirtual

Is a constant

Parameters

Implements BPASRing.

template<class Ring>
bool SparseUnivariatePolynomial< Ring >::isNegativeOne ( )
inlinevirtual

Is polynomial a constant -1

Parameters

Implements BPASRing.

template<class Ring>
bool SparseUnivariatePolynomial< Ring >::isOne ( )
inlinevirtual

Is polynomial a constant 1

Parameters

Implements BPASRing.

template<class Ring>
bool SparseUnivariatePolynomial< Ring >::isTrailingCoefficientZero ( )
inlinevirtual

Is trailing coefficient zero

Parameters

Implements BPASUnivariatePolynomial.

template<class Ring>
bool SparseUnivariatePolynomial< Ring >::isZero ( )
inlinevirtual

Is zero polynomial

Parameters

Implements BPASRing.

template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::lazyPseudoDivide ( SparseUnivariatePolynomial< Ring > &  b,
Ring *  c,
Ring *  d = NULL 
)
inline

Lazy pseudo dividsion Return the quotient and itself becomes remainder e is the exact number of division steps

Parameters
b,:The dividend polynomial
c,:The leading coefficient of b to the power e
d,:That to the power deg(a) - deg(b) + 1 - e
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::lazyPseudoDivide ( SparseUnivariatePolynomial< Ring > &  b,
SparseUnivariatePolynomial< Ring > *  rem,
Ring *  c,
Ring *  d 
)
inline

Lazy pseudo dividsion Return the quotient e is the exact number of division steps

Parameters
b,:The divident polynomial
rem,:The remainder polynomial
c,:The leading coefficient of b to the power e
d,:That to the power deg(a) - deg(b) + 1 - e
template<class Ring>
Ring SparseUnivariatePolynomial< Ring >::leadingCoefficient ( )
inline

Get the leading coefficient

Parameters
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::monicDivide ( SparseUnivariatePolynomial< Ring > &  b)
inline

Monic division Assuming the leading coefficient of dividend is 1 Return quotient and itself becomes remainder

Parameters
b,:The dividend polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::monicDivide ( SparseUnivariatePolynomial< Ring > &  b,
SparseUnivariatePolynomial< Ring > *  rem 
)
inline

Monic division Assuming the leading coefficient of dividend is 1 Return quotient

Parameters
b,:The dividend polynomial
rem,:The remainder polynomial
template<class Ring>
void SparseUnivariatePolynomial< Ring >::negate ( )
inline

Negate the polynomial

Parameters
template<class Ring>
void SparseUnivariatePolynomial< Ring >::negativeOne ( )
inlinevirtual

Set polynomial to -1

Parameters

Implements BPASRing.

template<class Ring>
int SparseUnivariatePolynomial< Ring >::numberOfTerms ( )
inline

Get the number of terms

Parameters
template<class Ring>
void SparseUnivariatePolynomial< Ring >::one ( )
inlinevirtual

Set polynomial to 1

Parameters

Implements BPASRing.

template<class Ring>
bool SparseUnivariatePolynomial< Ring >::operator!= ( SparseUnivariatePolynomial< Ring > &  b)
inline

Overload operator !=

Parameters
b,:A sparse univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator* ( SparseUnivariatePolynomial< Ring >  b)
inline

Multiply another polynomial

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator* ( Ring  c)
inline

Overload operator *

Parameters
c,:A coefficient
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator*= ( SparseUnivariatePolynomial< Ring >  b)
inline

Overload operator *=

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator*= ( Ring  c)
inline

Overload operator *=

Parameters
c,:A coefficient
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator+ ( SparseUnivariatePolynomial< Ring > &  b)
inline

Overload operator +

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator+ ( Ring  e)
inline

Overload operator +

Parameters
e,:A coefficient constant
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator+= ( SparseUnivariatePolynomial< Ring >  b)
inline

Overload operator+=

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator+= ( Ring  e)
inline

Overload operator +=

Parameters
e,:A coefficient constant
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator- ( )
inline

Overload operator -, negate

Parameters
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator- ( SparseUnivariatePolynomial< Ring > &  b)
inline

Subtract another polynomial

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator- ( Ring  e)
inline

Overload operator -

Parameters
e,:A coefficient constant
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator-= ( SparseUnivariatePolynomial< Ring >  b)
inline

Overload operator -=

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator-= ( Ring  e)
inline

Overload operator -=

Parameters
e,:A coefficient constant
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator/ ( SparseUnivariatePolynomial< Ring > &  b)
inline

Overload operator / EdeDivision

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator/ ( Ring  e)
inline

Overload operator /

Parameters
e,:A coefficient constant
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator/= ( SparseUnivariatePolynomial< Ring >  b)
inline

Overload operator /= ExactDivision

Parameters
b,:A univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator/= ( Ring  e)
inline

Overload operator /=

Parameters
e,:A coefficient constant
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator<< ( int  k)
inline

Overload operator << replace by muplitying x^k

Parameters
k,:The exponent of variable, k > 0
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator<<= ( int  k)
inline

Overload operator <<= replace by muplitying x^k

Parameters
k,:The exponent of variable, k > 0
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator= ( SparseUnivariatePolynomial< Ring >  b)
inline

Overload operator =

Parameters
b,:A sparse univariate polynomial
template<class Ring>
bool SparseUnivariatePolynomial< Ring >::operator== ( SparseUnivariatePolynomial< Ring > &  b)
inline

Overload operator ==

Parameters
b,:A sparse univariate polynomial
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator>> ( int  k)
inline

Overload operator >> replace by dividing x^k, and return the quotient

Parameters
k,:The exponent of variable, k > 0
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator>>= ( int  k)
inline

Overload operator >>= replace by dividing x^k, and return the quotient

Parameters
k,:The exponent of variable, k > 0
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::operator^ ( int  e)
inline

Overload operator ^ replace xor operation by exponentiation

Parameters
e,:The exponentiation, e > 0
template<class Ring>
SparseUnivariatePolynomial<Ring>& SparseUnivariatePolynomial< Ring >::operator^= ( int  e)
inline

Overload operator ^= replace xor operation by exponentiation

Parameters
e,:The exponentiation, e > 0
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::pseudoDivide ( SparseUnivariatePolynomial< Ring > &  b,
Ring *  d = NULL 
)
inline

Pseudo dividsion Return the quotient and itself becomes remainder

Parameters
b,:The divident polynomial
d,:The leading coefficient of b to the power deg(a) - deg(b) + 1
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::pseudoDivide ( SparseUnivariatePolynomial< Ring > &  b,
SparseUnivariatePolynomial< Ring > *  rem,
Ring *  d 
)
inline

Pseudo dividsion Return the quotient

Parameters
b,:The divident polynomial
rem,:The remainder polynomial
d,:The leading coefficient of b to the power deg(a) - deg(b) + 1
template<class Ring>
SparseUnivariatePolynomial<Ring> SparseUnivariatePolynomial< Ring >::resultant ( SparseUnivariatePolynomial< Ring > &  q)
inline

Resultant

Parameters
q,:The other sparse univariate polynomial
template<class Ring>
void SparseUnivariatePolynomial< Ring >::setCoefficient ( int  e,
Ring  c 
)
inline

Set a coeffcient with its exponent

Parameters
e,:The exponent
c,:The coefficient
template<class Ring>
void SparseUnivariatePolynomial< Ring >::setVariableName ( std::string  c)
inlinevirtual

Set the variable name

Parameters
c,:Variable's name

Implements BPASUnivariatePolynomial.

template<class Ring>
std::vector< SparseUnivariatePolynomial<Ring> > SparseUnivariatePolynomial< Ring >::squareFree ( )
inline

Square free

Parameters
template<class Ring>
std::vector< SparseUnivariatePolynomial<Ring> > SparseUnivariatePolynomial< Ring >::subresultantChain ( SparseUnivariatePolynomial< Ring > &  q)
inline

Subresultant Chain Return the list of subresultants

Parameters
q,:The other sparse univariate polynomial
template<class Ring>
std::string SparseUnivariatePolynomial< Ring >::variable ( )
inlinevirtual

Get the variable name

Parameters

Implements BPASUnivariatePolynomial.

template<class Ring>
void SparseUnivariatePolynomial< Ring >::zero ( )
inlinevirtual

Zero polynomial

Parameters

Implements BPASRing.

Friends And Related Function Documentation

template<class Ring>
std::ostream& operator<< ( std::ostream &  out,
SparseUnivariatePolynomial< Ring >  b 
)
friend

Overload stream operator <<

Parameters
out,:Stream object
b,:The univariate polynomial

The documentation for this class was generated from the following file: