GiNaCRA  0.6.4
GiNaCRA::UnivariatePolynomial Class Reference

A class for a univariate polynomial providing everything what a GiNaC expression of type polynomial is and in addition, stores the single main variable of the polynomial. More...

#include <UnivariatePolynomial.h>

Inheritance diagram for GiNaCRA::UnivariatePolynomial:
Collaboration diagram for GiNaCRA::UnivariatePolynomial:

Public Types

enum  subresultantStrategy { GENERIC_SUBRESULTANTSTRATEGY, LAZARDS_SUBRESULTANTSTRATEGY, DUCOS_SUBRESULTANTSTRATEGY }
 Predefined flags for different solving strategies in UnivariatePolynomial::subresultants. More...

Public Member Functions

 UnivariatePolynomial ()
 Constructs a univariate polynomial consisting of the standard variable defined in constants.h.
 UnivariatePolynomial (const numeric &n)
 Constructs a univariate polynomial with exactly the specified root.
 UnivariatePolynomial (const ex &p, const symbol &s, bool enableCheck=true) throw ( invalid_argument )
 Constructs a univariate polynomial.
 UnivariatePolynomial (const UnivariatePolynomial &p)
 Constructs a univariate polynomial as copy of another one.
const symbol variable () const
 Selects the main variable of the polynomial.
const bool enabledPolynomialCheck () const
 Selects the flag for the is_rational_polynomial check.
UnivariatePolynomial inVariable (const symbol &x) const
const UnivariatePolynomialoperator= (const UnivariatePolynomial &)
 This polynomial gets all values of the other.
const UnivariatePolynomialoperator= (const ex &)
 This polynomial gets all values of the other expression, using the current main variable.
ex coeff (int i) const
ex lcoeff () const
ex tcoeff () const
ex content () const
UnivariatePolynomial diff (unsigned nth=1) const
UnivariatePolynomial trunc () const
 Removes the leading term.
bool isZero () const
 Returns true if the univariate polynomial is the zero polynomial, otherwise false.
const bool hasZeroRoot () const
int degree () const
int ldegree () const
 The low-degree is the smallest exponent at the main variable occuring.
UnivariatePolynomial primpart () const
UnivariatePolynomial primpart (const ex &content) const
UnivariatePolynomial sepapart () const
 Computes a polynomial being decomposed into linear factors of multiplicity 1 with the same set of zeros as this polynomial.
UnivariatePolynomial nonzeropart () const
 Eliminates the root 0 from the polynomial by dividing the polynomial by a power of the main variable.
bool isCompatible (const UnivariatePolynomial &o) const
 Compares univariate polynomials for compatibility regarding common computations.
bool isConstant () const
 Returns true if the univariate polynomial is constant in the respective variable, otherwise false.
ex evaluateAt (const ex &a) const
 Evaluation of the univariate polynomial at the specified expression, yielding a term in the coefficients only.
const UnivariatePolynomial rem (const UnivariatePolynomial &o) const
 Compute the remainder of o modulo the given polynomial in this variable.
const UnivariatePolynomial quo (const UnivariatePolynomial &o) const
 Compute the quotient of division by o in this variable.
const UnivariatePolynomial add (const UnivariatePolynomial &o) const
 Compute the sum of this and o in this variable.
const UnivariatePolynomial mul (const UnivariatePolynomial &o) const
 Compute the product of this and o in this variable.
const UnivariatePolynomial sub (const UnivariatePolynomial &o) const
 Compute the subtraction of this by o in this variable.
UnivariatePolynomial square () const
 Calculates the square.
const UnivariatePolynomial gcd (const UnivariatePolynomial &o) const
 Computes the greatest common divisor of this polynomial and the given by Euclid's algorithm.
const UnivariatePolynomial resultant (const UnivariatePolynomial &o) const
 Compute the resultant of o and the given polynomial in this variable.
const bool isEqual (const UnivariatePolynomial &o) const
void do_print (const print_context &c, unsigned level=0) const

Static Public Member Functions

static list< UnivariatePolynomialstandardSturmSequence (const UnivariatePolynomial &a, const UnivariatePolynomial &b) throw ( invalid_argument )
 Generates a standard Sturm sequence by generating an additively inverted polynomial remainder sequence.
static bool univariatePolynomialIsLess (const UnivariatePolynomial &a, const UnivariatePolynomial &b)
 Compares two univariate polynomials.
static bool univariatePolynomialIsLessLowDeg (const UnivariatePolynomial &a, const UnivariatePolynomial &b)
 Compares two univariate polynomials.
static bool univariatePolynomialIsLessOddDeg (const UnivariatePolynomial &a, const UnivariatePolynomial &b)
 Compares two univariate polynomials.
static bool univariatePolynomialIsLessOddLowDeg (const UnivariatePolynomial &a, const UnivariatePolynomial &b)
 Compares two univariate polynomials.
static bool univariatePolynomialIsLessEvenDeg (const UnivariatePolynomial &a, const UnivariatePolynomial &b)
 Compares two univariate polynomials.
static bool univariatePolynomialIsLessEvenLowDeg (const UnivariatePolynomial &a, const UnivariatePolynomial &b)
 Compares two univariate polynomials.
static const list
< UnivariatePolynomial
subresultants (const UnivariatePolynomial &a, const UnivariatePolynomial &b, const subresultantStrategy strategy=GENERIC_SUBRESULTANTSTRATEGY)
 Computes the subresultant sequence according to the algorithm in [Lionel Ducos.
static const vector< ex > subresultantCoefficients (const UnivariatePolynomial &a, const UnivariatePolynomial &b, const subresultantStrategy strategy=GENERIC_SUBRESULTANTSTRATEGY)
 Returns the leading coefficients of the subresultants of a and b.
static const vector< ex > principalSubresultantCoefficients (const UnivariatePolynomial &a, const UnivariatePolynomial &b, const subresultantStrategy strategy=GENERIC_SUBRESULTANTSTRATEGY)
 Returns the i-th coefficients of the i-th subresultant of a and b at the i-th position of the result vector.

Protected Attributes

symbol mVariable
bool mEnabledPolynomialCheck

Detailed Description

A class for a univariate polynomial providing everything what a GiNaC expression of type polynomial is and in addition, stores the single main variable of the polynomial.

Author:
Ulrich Loup
Since:
2010-08-03
Version:
2012-05-19
See also:
ISBN 0-387-94090-1 and ISBN-13: 978-3642069642

Definition at line 51 of file UnivariatePolynomial.h.


Member Enumeration Documentation

Predefined flags for different solving strategies in UnivariatePolynomial::subresultants.

Enumerator:
GENERIC_SUBRESULTANTSTRATEGY 
LAZARDS_SUBRESULTANTSTRATEGY 
DUCOS_SUBRESULTANTSTRATEGY 

Definition at line 461 of file UnivariatePolynomial.h.


Constructor & Destructor Documentation

Constructs a univariate polynomial consisting of the standard variable defined in constants.h.

Definition at line 63 of file UnivariatePolynomial.h.

Referenced by add(), diff(), evaluateAt(), gcd(), inVariable(), mul(), nonzeropart(), primpart(), quo(), rem(), resultant(), sepapart(), square(), sub(), subresultants(), and trunc().

GiNaCRA::UnivariatePolynomial::UnivariatePolynomial ( const numeric &  n) [inline]

Constructs a univariate polynomial with exactly the specified root.

Parameters:
nroot to-be

Definition at line 73 of file UnivariatePolynomial.h.

GiNaCRA::UnivariatePolynomial::UnivariatePolynomial ( const ex &  p,
const symbol &  s,
bool  enableCheck = true 
) throw ( invalid_argument )

Constructs a univariate polynomial.

Parameters:
ppolynomial
smain variable of the univariate polynomial p
enableCheckif set to true (default), the polynomial is checked for being a proper polynomial by GiNaC::ex::is_polynomial. Otherwise no check will be performed.

Definition at line 49 of file UnivariatePolynomial.cpp.

Constructs a univariate polynomial as copy of another one.

Parameters:
punivariate polynomial

Definition at line 91 of file UnivariatePolynomial.h.


Member Function Documentation

Compute the sum of this and o in this variable.

Parameters:
oother polynomial
Returns:

Definition at line 311 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::operator+().

ex GiNaCRA::UnivariatePolynomial::coeff ( int  i) const [inline]
Parameters:
idegree of which the coefficient shall be returned
Returns:
the i-th coefficient of this polynomial

Reimplemented in GiNaCRA::RationalUnivariatePolynomial.

Definition at line 148 of file UnivariatePolynomial.h.

References mVariable.

Referenced by GiNaCRA::RationalUnivariatePolynomial::cauchyBound(), and nonzeropart().

Returns:
the content of this polynomial

Definition at line 172 of file UnivariatePolynomial.h.

References mVariable.

void GiNaCRA::UnivariatePolynomial::do_print ( const print_context &  c,
unsigned  level = 0 
) const

Definition at line 62 of file UnivariatePolynomial.cpp.

References mVariable.

Selects the flag for the is_rational_polynomial check.

Returns:
flag for the is_rational_polynomial check

Definition at line 114 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck.

Referenced by GiNaCRA::operator-().

ex GiNaCRA::UnivariatePolynomial::evaluateAt ( const ex &  a) const [inline]

Evaluation of the univariate polynomial at the specified expression, yielding a term in the coefficients only.

Parameters:
aan expression for evaluation
Returns:
value of the univariate polynomial at the specified numeric.

Definition at line 277 of file UnivariatePolynomial.h.

References mVariable, and UnivariatePolynomial().

Computes the greatest common divisor of this polynomial and the given by Euclid's algorithm.

Parameters:
o
Returns:
the greatest common divisor of this polynomial and the given

Definition at line 351 of file UnivariatePolynomial.h.

References GiNaC::gcd(), mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Referenced by sepapart().

const bool GiNaCRA::UnivariatePolynomial::hasZeroRoot ( ) const [inline]
Returns:
true in case the polynomial's lowest degree is not 0

Definition at line 204 of file UnivariatePolynomial.h.

References ldegree().

Referenced by GiNaCRA::RealAlgebraicNumberFactory::realRoots(), and GiNaCRA::RealAlgebraicNumberFactory::realRootsEval().

Definition at line 123 of file UnivariatePolynomial.h.

References mVariable, and UnivariatePolynomial().

Compares univariate polynomials for compatibility regarding common computations.

Returns:
true in case the other UnivariatePolynomial has the same symbol as this.

Definition at line 259 of file UnivariatePolynomial.h.

References mVariable.

Referenced by GiNaCRA::RealAlgebraicNumberIR::sgn(), and subresultants().

Returns true if the univariate polynomial is constant in the respective variable, otherwise false.

Returns:
true if the univariate polynomial is constant in the respective variable, otherwise false.

Definition at line 268 of file UnivariatePolynomial.h.

References degree(), and mVariable.

Referenced by GiNaCRA::RealAlgebraicNumberFactory::realRoots(), sepapart(), and GiNaCRA::CAD::truncation().

const bool GiNaCRA::UnivariatePolynomial::isEqual ( const UnivariatePolynomial o) const [inline]
Parameters:
o
Returns:
true in case the other univariate polynomial equals this

Definition at line 378 of file UnivariatePolynomial.h.

References mVariable.

Referenced by GiNaCRA::operator!=(), GiNaCRA::UnivariatePolynomialSetEquals::operator()(), GiNaCRA::operator==(), and univariatePolynomialIsLess().

bool GiNaCRA::UnivariatePolynomial::isZero ( ) const [inline]

Returns true if the univariate polynomial is the zero polynomial, otherwise false.

Returns:
true if the univariate polynomial is the zero polynomial, otherwise false.

Definition at line 196 of file UnivariatePolynomial.h.

Referenced by GiNaCRA::CAD::elimination(), and subresultants().

Returns:
the leading coefficient of this polynomial

Reimplemented in GiNaCRA::RationalUnivariatePolynomial.

Definition at line 156 of file UnivariatePolynomial.h.

References mVariable.

Referenced by GiNaCRA::RationalUnivariatePolynomial::cauchyBound(), and subresultants().

The low-degree is the smallest exponent at the main variable occuring.

Returns:
low-degree of the univariate polynomial in its respective symbol

Definition at line 220 of file UnivariatePolynomial.h.

References mVariable.

Referenced by GiNaCRA::RationalUnivariatePolynomial::cauchyBound(), hasZeroRoot(), GiNaCRA::RationalUnivariatePolynomial::maximumNorm(), nonzeropart(), GiNaCRA::RationalUnivariatePolynomial::oneNorm(), and GiNaCRA::RationalUnivariatePolynomial::twoNorm().

Compute the product of this and o in this variable.

Parameters:
oother polynomial
Returns:

Definition at line 321 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::operator*().

Eliminates the root 0 from the polynomial by dividing the polynomial by a power of the main variable.

Runtime complexity:
linear in degree()

Definition at line 111 of file UnivariatePolynomial.cpp.

References coeff(), degree(), ldegree(), mVariable, UnivariatePolynomial(), and variable().

Referenced by GiNaCRA::RealAlgebraicNumberFactory::realRoots(), and GiNaCRA::RealAlgebraicNumberFactory::realRootsEval().

const UnivariatePolynomial & GiNaCRA::UnivariatePolynomial::operator= ( const UnivariatePolynomial o)

This polynomial gets all values of the other.

Definition at line 73 of file UnivariatePolynomial.cpp.

References mEnabledPolynomialCheck, and mVariable.

Referenced by operator=().

const UnivariatePolynomial & GiNaCRA::UnivariatePolynomial::operator= ( const ex &  o)

This polynomial gets all values of the other expression, using the current main variable.

Definition at line 81 of file UnivariatePolynomial.cpp.

References operator=().

Returns:
primitive part of the univariate polynomial

Definition at line 228 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::RealAlgebraicNumberIR::add(), GiNaCRA::RealAlgebraicNumberIR::mul(), and sepapart().

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::primpart ( const ex &  content) const [inline]
Parameters:
contentprecomputed content of this polynomial
Returns:
primitive part of the univariate polynomial

Definition at line 237 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Returns the i-th coefficients of the i-th subresultant of a and b at the i-th position of the result vector.

Parameters:
athe first Polynomial
bthe second Polynomial
strategychoice of optimization. Standard is none, other possibilities are due to the sections 2 and 3 of the paper.
See also:
UnivariatePolynomial::subresultants
Returns:
vector containing at the i-th position the i-th subresultant coefficient

Definition at line 228 of file UnivariatePolynomial.cpp.

References subresultants().

Referenced by GiNaCRA::CAD::elimination().

Compute the quotient of division by o in this variable.

Parameters:
oother polynomial
Returns:

Definition at line 301 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::operator/(), and sepapart().

Compute the remainder of o modulo the given polynomial in this variable.

Parameters:
oother polynomial
Returns:

Definition at line 291 of file UnivariatePolynomial.h.

References mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::operator%().

Compute the resultant of o and the given polynomial in this variable.

The resultant ist the subresultant of lowest degree.

Parameters:
oother polynomial
Returns:
the resultant of this polynomial and o
See also:
subresultants, GiNaC::resultant

Definition at line 364 of file UnivariatePolynomial.h.

References mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::RealAlgebraicNumberFactory::evaluateIR().

Computes a polynomial being decomposed into linear factors of multiplicity 1 with the same set of zeros as this polynomial.

This is also referred to as the square-free part.

Returns:
separable part of the univariate polynomial, or zero in case the polynomial was constant

Definition at line 103 of file UnivariatePolynomial.cpp.

References diff(), gcd(), isConstant(), mEnabledPolynomialCheck, mVariable, primpart(), quo(), and UnivariatePolynomial().

Calculates the square.

Returns:
this polynomial squared

Definition at line 340 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

list< UnivariatePolynomial > GiNaCRA::UnivariatePolynomial::standardSturmSequence ( const UnivariatePolynomial a,
const UnivariatePolynomial b 
) throw ( invalid_argument ) [static]

Generates a standard Sturm sequence by generating an additively inverted polynomial remainder sequence.

Convention: If one polynomial is zero, the corresponding Sturm sequence is zero followed by the other polynomial.

Parameters:
a
b
Returns:
Vector of pointers to the elements of the standard Sturm sequence

Definition at line 254 of file UnivariatePolynomial.cpp.

Compute the subtraction of this by o in this variable.

Parameters:
oother polynomial
Returns:

Definition at line 331 of file UnivariatePolynomial.h.

References mEnabledPolynomialCheck, mVariable, and UnivariatePolynomial().

Referenced by GiNaCRA::operator-().

Returns the leading coefficients of the subresultants of a and b.

Parameters:
athe first Polynomial
bthe second Polynomial
strategychoice of optimization. Standard is none, other possibilities are due to the sections 2 and 3 of the paper.
See also:
UnivariatePolynomial::subresultants
Returns:
vector containing at the i-th position the i-th subresultant coefficient

Definition at line 217 of file UnivariatePolynomial.cpp.

References subresultants().

Computes the subresultant sequence according to the algorithm in [Lionel Ducos.

Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra 145 (2000) 149–163]

Marginal cases: Let the degree of a be smaller or equal than the degree of b. if deg(b) is less than 2, then only a, b are returned.

Parameters:
athe first Polynomial
bthe second Polynomial
strategychoice of optimization. Standard is none, other possibilities are due to the sections 2 and 3 of the paper.
Returns:
the subresultant sequence in descending order of degree.
Runtime complexity:
O( deg(a)*deg(b) )
Todo:
implement using page 151 of the above mentioned article
Todo:
implement using page 154 of the above mentioned article
Todo:
implement using page 151 of the above mentioned article
Todo:
implement using page 154 of the above mentioned article

Definition at line 125 of file UnivariatePolynomial.cpp.

References degree(), DUCOS_SUBRESULTANTSTRATEGY, GENERIC_SUBRESULTANTSTRATEGY, isCompatible(), isZero(), LAZARDS_SUBRESULTANTSTRATEGY, lcoeff(), mVariable, UnivariatePolynomial(), and variable().

Referenced by principalSubresultantCoefficients(), and subresultantCoefficients().

Returns:
the trailing coefficient of this polynomial

Reimplemented in GiNaCRA::RationalUnivariatePolynomial.

Definition at line 164 of file UnivariatePolynomial.h.

References mVariable.

Removes the leading term.

Returns:
the polynomial without leading term

Definition at line 93 of file UnivariatePolynomial.cpp.

References mEnabledPolynomialCheck, UnivariatePolynomial(), and variable().

Referenced by GiNaCRA::CAD::truncation().

Compares two univariate polynomials.

The behavior of this function is equivalent to GiNaC::ex_is_less( a, b ).

Parameters:
a
b
Returns:
true if a < b, false otherwise

Definition at line 273 of file UnivariatePolynomial.cpp.

References isEqual().

Referenced by univariatePolynomialIsLessEvenDeg(), univariatePolynomialIsLessEvenLowDeg(), univariatePolynomialIsLessLowDeg(), univariatePolynomialIsLessOddDeg(), and univariatePolynomialIsLessOddLowDeg().

Compares two univariate polynomials.

The behavior of this function is equivalent to a.degree() even or a.degree() >= b.degree() and GiNaC::ex_is_less( a, b ).

Parameters:
a
b
Returns:
true if a < b, false otherwise

Definition at line 295 of file UnivariatePolynomial.cpp.

References degree(), and univariatePolynomialIsLess().

Referenced by GiNaCRA::CADSettings::getSettings().

Compares two univariate polynomials.

The behavior of this function is equivalent to a.degree() even and a.degree() < b.degree() or a.degree() >= b.degree() and GiNaC::ex_is_less( a, b ).

Parameters:
a
b
Returns:
true if a < b, false otherwise

Definition at line 300 of file UnivariatePolynomial.cpp.

References degree(), and univariatePolynomialIsLess().

Referenced by GiNaCRA::CADSettings::getSettings().

Compares two univariate polynomials.

The behavior of this function is equivalent to a.degree() < b.degree() or a.degree() >= b.degree() and GiNaC::ex_is_less( a, b ).

Parameters:
a
b
Returns:
true if a < b, false otherwise

Definition at line 278 of file UnivariatePolynomial.cpp.

References degree(), and univariatePolynomialIsLess().

Referenced by GiNaCRA::CADSettings::getSettings().

Compares two univariate polynomials.

The behavior of this function is equivalent to a.degree() odd or a.degree() >= b.degree() and GiNaC::ex_is_less( a, b ).

Parameters:
a
b
Returns:
true if a < b, false otherwise

Definition at line 283 of file UnivariatePolynomial.cpp.

References degree(), and univariatePolynomialIsLess().

Referenced by GiNaCRA::CADSettings::getSettings().

Compares two univariate polynomials.

The behavior of this function is equivalent to a.degree() odd and a.degree() < b.degree() or a.degree() >= b.degree() and GiNaC::ex_is_less( a, b ).

Parameters:
a
b
Returns:
true if a < b, false otherwise

Definition at line 289 of file UnivariatePolynomial.cpp.

References degree(), and univariatePolynomialIsLess().

Referenced by GiNaCRA::CADSettings::getSettings().


Field Documentation


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