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 <RationalUnivariatePolynomial.h>

Inheritance diagram for GiNaCRA::RationalUnivariatePolynomial:

[legend]

Collaboration diagram for GiNaCRA::RationalUnivariatePolynomial:

[legend]

Public Types
enum	subresultantStrategy { GENERIC_SUBRESULTANTSTRATEGY, LAZARDS_SUBRESULTANTSTRATEGY, DUCOS_SUBRESULTANTSTRATEGY }
	Predefined flags for different solving strategies in `UnivariatePolynomial::subresultants`. More...
Public Member Functions
	RationalUnivariatePolynomial ()
	Constructs a univariate polynomial consisting of the standard variable defined in constants.h.
	RationalUnivariatePolynomial (const ex &p, const symbol &s) throw ( invalid_argument )
	Constructs a rational univariate polynomial in case the given expression is a rational univariate polynomial in the specified variable.
	RationalUnivariatePolynomial (const UnivariatePolynomial &p) throw ( invalid_argument )
	Constructs a rational univariate polynomial as copy of a univariate polynomial in case it is rational.
numeric	coeff (int i) const
numeric	lcoeff () const
numeric	tcoeff () const
GiNaC::sign	sgn (const numeric &a) const
	Returns sign (-1, 0, 1) of the rational univariate polynomial at the specified numeric.
numeric	evaluateAt (const numeric &a) const
	Evaluation of the rational univariate polynomial at the specified numeric, yielding a new numeric.
numeric	oneNorm () const
numeric	twoNorm () const
numeric	maximumNorm () const
numeric	cauchyBound () const
	Computes the (upper) Cauchy bound, following Notation 10.1 (ISBN 0-387-94090-1).
unsigned	countRealRoots () const
	Computes the number of real roots of the polynomial `p`.
numeric	approximateRealRoot (const numeric start, const OpenInterval &i, unsigned steps=3) const
	Searches a real root of this polynomial within the given interval i, starting at position start, which is returned if there was no result after steps+1 iterations of the Newton's method.
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
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 < RationalUnivariatePolynomial >	standardSturmSequence (const RationalUnivariatePolynomial &a, const RationalUnivariatePolynomial &b)
	Generates a standard Sturm sequence by generating an additively inverted polynomial remainder sequence.
static unsigned	signVariations (const list< RationalUnivariatePolynomial > &seq, const numeric &a)
	Counts the changes of sign when evaluating the given sequence of real algebraic univariate polynomials at the given numeric.
static int	calculateSturmCauchyIndex (const RationalUnivariatePolynomial &p, const RationalUnivariatePolynomial &q)
	Calculates the Cauchy-Index.
static unsigned	countRealRoots (const list< RationalUnivariatePolynomial > &seq, const OpenInterval &i)
	Computes the number of real roots of a polynomial in the specified interval, by using its standard Sturm sequence.
static unsigned	countRealRoots (const RationalUnivariatePolynomial &p, const OpenInterval &i)
	Computes the number of real roots of the polynomial `p` in the specified interval.
static int	calculateRemainderTarskiQuery (const RationalUnivariatePolynomial &p, const RationalUnivariatePolynomial &q)
	Calculates the TarskiQuery.
static list< UnivariatePolynomial >	standardSturmSequence (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.

This special superclass of UnivariatePolynomial is for rational coefficients only.

Author:: Ulrich Loup

Since:: 2010-09-07

Version:: 2012-04-15

See also:: ISBN 0-387-94090-1 and ISBN-13: 978-3642069642

Definition at line 42 of file RationalUnivariatePolynomial.h.

Member Enumeration Documentation

enum GiNaCRA::UnivariatePolynomial::subresultantStrategy [inherited]

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

GiNaCRA::RationalUnivariatePolynomial::RationalUnivariatePolynomial ( ) [inline]

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

Definition at line 54 of file RationalUnivariatePolynomial.h.

GiNaCRA::RationalUnivariatePolynomial::RationalUnivariatePolynomial	(	const ex &	p,
		const symbol &	s
	)		throw ( invalid_argument )

Constructs a rational univariate polynomial in case the given expression is a rational univariate polynomial in the specified variable.

Parameters:

p	polynomial
s	main variable of the univariate polynomial p

Definition at line 60 of file RationalUnivariatePolynomial.cpp.

References GiNaC::is_rational_polynomial().

GiNaCRA::RationalUnivariatePolynomial::RationalUnivariatePolynomial ( const UnivariatePolynomial & p ) throw ( invalid_argument )

Constructs a rational univariate polynomial as copy of a univariate polynomial in case it is rational.

Parameters:

p	univariate polynomial

Definition at line 48 of file RationalUnivariatePolynomial.cpp.

References GiNaC::is_rational_polynomial(), and GiNaCRA::UnivariatePolynomial::variable().

Member Function Documentation

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::add ( const UnivariatePolynomial & o ) const [inline, inherited]

Compute the sum of this and o in this variable.

Parameters:

o	other polynomial

Returns:

Definition at line 311 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

Referenced by GiNaCRA::operator+().

numeric GiNaCRA::RationalUnivariatePolynomial::approximateRealRoot	(	const numeric	start,
		const OpenInterval &	i,
		unsigned	steps = `3`
	)		const

Searches a real root of this polynomial within the given interval i, starting at position start, which is returned if there was no result after steps+1 iterations of the Newton's method.

Parameters:

start
i
steps

Returns:: a real root of this polynomial within the given interval i or start if no such root is found within the given number of steps+1

Definition at line 154 of file RationalUnivariatePolynomial.cpp.

References GiNaCRA::OpenInterval::contains(), GiNaCRA::UnivariatePolynomial::diff(), evaluateAt(), sgn(), and GiNaC::ZERO_SIGN.

Referenced by GiNaCRA::RealAlgebraicNumberIR::refine(), and GiNaCRA::RealAlgebraicNumberFactory::searchRealRoots().

int GiNaCRA::RationalUnivariatePolynomial::calculateRemainderTarskiQuery	(	const RationalUnivariatePolynomial &	p,
		const RationalUnivariatePolynomial &	q
	)		`[static]`

Calculates the TarskiQuery.

Parameters:

p	Univariate nonzero polynomial
q	Univariate polynomial

Returns:: The TarskiQuery TaQ(q,p), defined as the sum over the signs(q(x)) where x are roots of p

See also:: Algorithm 9.2 TODO implement a more efficient way to calculate it by using algorithm 9.5.

Definition at line 211 of file RationalUnivariatePolynomial.cpp.

References calculateSturmCauchyIndex(), and GiNaCRA::UnivariatePolynomial::diff().

int GiNaCRA::RationalUnivariatePolynomial::calculateSturmCauchyIndex	(	const RationalUnivariatePolynomial &	p,
		const RationalUnivariatePolynomial &	q
	)		`[static]`

Calculates the Cauchy-Index.

Parameters:

p	Univariate nonzero polynomial
q	Univariate polynomial

Returns:: the Cauchy-Index Ind(Q/P)

See also:: Algorithm 9.1 TODO implement an overloaded cauchyIndex with custom bounds.

Definition at line 198 of file RationalUnivariatePolynomial.cpp.

References cauchyBound(), signVariations(), and standardSturmSequence().

Referenced by calculateRemainderTarskiQuery().

numeric GiNaCRA::RationalUnivariatePolynomial::cauchyBound ( ) const

Computes the (upper) Cauchy bound, following Notation 10.1 (ISBN 0-387-94090-1).

Returns:: the (upper) Cauchy bound, following Notation 10.1 (ISBN 0-387-94090-1)

Definition at line 135 of file RationalUnivariatePolynomial.cpp.

References GiNaCRA::abs(), GiNaCRA::UnivariatePolynomial::coeff(), GiNaCRA::UnivariatePolynomial::degree(), GiNaCRA::UnivariatePolynomial::lcoeff(), and GiNaCRA::UnivariatePolynomial::ldegree().

Referenced by calculateSturmCauchyIndex(), countRealRoots(), and GiNaCRA::RealAlgebraicNumberFactory::realRoots().

numeric GiNaCRA::RationalUnivariatePolynomial::coeff ( int i ) const [inline]

Parameters:

i	degree of which the coefficient shall be returned

Returns:: the i-th coefficient of this polynomial

Reimplemented from GiNaCRA::UnivariatePolynomial.

Definition at line 79 of file RationalUnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable.

Referenced by evaluateAt(), maximumNorm(), oneNorm(), and twoNorm().

ex GiNaCRA::UnivariatePolynomial::content ( ) const [inline, inherited]

Returns:: the content of this polynomial

Definition at line 172 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable.

unsigned GiNaCRA::RationalUnivariatePolynomial::countRealRoots ( ) const

Computes the number of real roots of the polynomial p.

Returns:: the number of real roots of the polynomial

Definition at line 146 of file RationalUnivariatePolynomial.cpp.

References cauchyBound(), GiNaCRA::UnivariatePolynomial::diff(), GiNaCRA::OpenInterval::left(), GiNaCRA::OpenInterval::right(), signVariations(), and standardSturmSequence().

Referenced by GiNaCRA::CAD::addPolynomials(), GiNaCRA::CAD::CAD(), GiNaCRA::RealAlgebraicNumberFactory::evaluateIR(), GiNaCRA::operator*(), GiNaCRA::operator+(), GiNaCRA::operator-(), and GiNaCRA::RealAlgebraicNumberIR::refineAvoiding().

static unsigned GiNaCRA::RationalUnivariatePolynomial::countRealRoots	(	const list< RationalUnivariatePolynomial > &	seq,
		const OpenInterval &	i
	)		`[inline, static]`

Computes the number of real roots of a polynomial in the specified interval, by using its standard Sturm sequence.

Parameters:

seq
i	isolating interval where the real roots w.r.t. seq shall be counted

Returns:: the number of real roots of the polynomial, whose standard Sturm sequence is given, in the interval i

Definition at line 183 of file RationalUnivariatePolynomial.h.

References GiNaCRA::OpenInterval::left(), GiNaCRA::OpenInterval::right(), and signVariations().

static unsigned GiNaCRA::RationalUnivariatePolynomial::countRealRoots	(	const RationalUnivariatePolynomial &	p,
		const OpenInterval &	i
	)		`[inline, static]`

Computes the number of real roots of the polynomial p in the specified interval.

Parameters:

p
i	isolating interval where the real roots of p shall be counted

Returns:: the number of real roots of the polynomial in the interval i

Definition at line 194 of file RationalUnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::diff(), GiNaCRA::OpenInterval::left(), GiNaCRA::OpenInterval::right(), signVariations(), and standardSturmSequence().

int GiNaCRA::UnivariatePolynomial::degree ( ) const [inline, inherited]

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

Definition at line 212 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable.

Referenced by cauchyBound(), GiNaCRA::RealAlgebraicNumberFactory::commonRealRoots(), evaluateAt(), GiNaCRA::RealAlgebraicNumberIR::inverse(), GiNaCRA::UnivariatePolynomial::isConstant(), maximumNorm(), GiNaCRA::UnivariatePolynomial::nonzeropart(), oneNorm(), GiNaCRA::UnivariatePolynomial::subresultants(), twoNorm(), GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessEvenDeg(), GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessEvenLowDeg(), GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessLowDeg(), GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessOddDeg(), and GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessOddLowDeg().

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::diff ( unsigned nth = 1 ) const [inline, inherited]

Parameters:

nth

Returns:: nth derivative of the univariate polynomial in the given symbol

Definition at line 181 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

Referenced by GiNaCRA::RealAlgebraicNumberIR::add(), approximateRealRoot(), calculateRemainderTarskiQuery(), countRealRoots(), GiNaCRA::CAD::elimination(), GiNaCRA::RealAlgebraicNumberFactory::evaluateIR(), GiNaCRA::RealAlgebraicNumberIR::mul(), GiNaCRA::RealAlgebraicNumberFactory::realRoots(), GiNaCRA::RealAlgebraicNumberFactory::realRootsEval(), GiNaCRA::UnivariatePolynomial::sepapart(), and GiNaCRA::RealAlgebraicNumberIR::sgn().

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

Definition at line 62 of file UnivariatePolynomial.cpp.

References GiNaCRA::UnivariatePolynomial::mVariable.

const bool GiNaCRA::UnivariatePolynomial::enabledPolynomialCheck ( ) const [inline, inherited]

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 GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck.

Referenced by GiNaCRA::operator-().

numeric GiNaCRA::RationalUnivariatePolynomial::evaluateAt ( const numeric & a ) const

Evaluation of the rational univariate polynomial at the specified numeric, yielding a new numeric.

Parameters:

a numeric

Returns:: value of the univariate polynomial at the specified numeric.

Definition at line 95 of file RationalUnivariatePolynomial.cpp.

References coeff(), and GiNaCRA::UnivariatePolynomial::degree().

Referenced by approximateRealRoot(), and sgn().

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

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

Parameters:

a	an expression for evaluation

Returns:: value of the univariate polynomial at the specified numeric.

Definition at line 277 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::gcd ( const UnivariatePolynomial & o ) const [inline, inherited]

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(), GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

Referenced by GiNaCRA::UnivariatePolynomial::sepapart().

const bool GiNaCRA::UnivariatePolynomial::hasZeroRoot ( ) const [inline, inherited]

Returns:: true in case the polynomial's lowest degree is not 0

Definition at line 204 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::ldegree().

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

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::inVariable ( const symbol & x ) const [inline, inherited]

Definition at line 123 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

bool GiNaCRA::UnivariatePolynomial::isCompatible ( const UnivariatePolynomial & o ) const [inline, inherited]

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 GiNaCRA::UnivariatePolynomial::mVariable.

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

bool GiNaCRA::UnivariatePolynomial::isConstant ( ) const [inline, inherited]

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 GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::mVariable.

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

const bool GiNaCRA::UnivariatePolynomial::isEqual ( const UnivariatePolynomial & o ) const [inline, inherited]

Parameters:

o

Returns:: true in case the other univariate polynomial equals this

Definition at line 378 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable.

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

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

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 GiNaCRA::UnivariatePolynomial::subresultants().

numeric GiNaCRA::RationalUnivariatePolynomial::lcoeff ( ) const [inline]

Returns:: the leading coefficient of this polynomial

Reimplemented from GiNaCRA::UnivariatePolynomial.

Definition at line 87 of file RationalUnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable.

int GiNaCRA::UnivariatePolynomial::ldegree ( ) const [inline, inherited]

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 GiNaCRA::UnivariatePolynomial::mVariable.

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

numeric GiNaCRA::RationalUnivariatePolynomial::maximumNorm ( ) const

Returns:: Maximum-norm of the real algebraic univariate polynomial in case this has numeric coefficients.

Definition at line 122 of file RationalUnivariatePolynomial.cpp.

References GiNaCRA::abs(), coeff(), GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::ldegree().

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

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::mul ( const UnivariatePolynomial & o ) const [inline, inherited]

Compute the product of this and o in this variable.

Parameters:

o	other polynomial

Returns:

Definition at line 321 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

Referenced by GiNaCRA::operator*().

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::nonzeropart ( ) const [inherited]

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 GiNaCRA::UnivariatePolynomial::coeff(), GiNaCRA::UnivariatePolynomial::degree(), GiNaCRA::UnivariatePolynomial::ldegree(), GiNaCRA::UnivariatePolynomial::mVariable, GiNaCRA::UnivariatePolynomial::UnivariatePolynomial(), and GiNaCRA::UnivariatePolynomial::variable().

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

numeric GiNaCRA::RationalUnivariatePolynomial::oneNorm ( ) const

Returns:: One-norm of the rational univariate polynomial in case this has numeric coefficients.

Definition at line 104 of file RationalUnivariatePolynomial.cpp.

References GiNaCRA::abs(), coeff(), GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::ldegree().

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::primpart ( ) const [inline, inherited]

Returns:: primitive part of the univariate polynomial

Definition at line 228 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

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

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::primpart ( const ex & content ) const [inline, inherited]

Parameters:

content precomputed content of this polynomial

Returns:: primitive part of the univariate polynomial

Definition at line 237 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

const vector< ex > GiNaCRA::UnivariatePolynomial::principalSubresultantCoefficients	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b,
		const subresultantStrategy	strategy = `GENERIC_SUBRESULTANTSTRATEGY`
	)		`[static, inherited]`

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

Parameters:

a	the first Polynomial
b	the second Polynomial
strategy	choice 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 GiNaCRA::UnivariatePolynomial::subresultants().

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

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::quo ( const UnivariatePolynomial & o ) const [inline, inherited]

Compute the quotient of division by o in this variable.

Parameters:

o	other polynomial

Returns:

Definition at line 301 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

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

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::rem ( const UnivariatePolynomial & o ) const [inline, inherited]

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

Parameters:

o	other polynomial

Returns:

Definition at line 291 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

Referenced by GiNaCRA::operator%().

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::resultant ( const UnivariatePolynomial & o ) const [inline, inherited]

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

The resultant ist the subresultant of lowest degree.

Parameters:

o	other polynomial

Returns:: the resultant of this polynomial and o

See also:: subresultants, GiNaC::resultant

Definition at line 364 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

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

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::sepapart ( ) const [inherited]

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 GiNaCRA::UnivariatePolynomial::diff(), GiNaCRA::UnivariatePolynomial::gcd(), GiNaCRA::UnivariatePolynomial::isConstant(), GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, GiNaCRA::UnivariatePolynomial::primpart(), GiNaCRA::UnivariatePolynomial::quo(), and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

GiNaC::sign GiNaCRA::RationalUnivariatePolynomial::sgn ( const numeric & a ) const

Returns sign (-1, 0, 1) of the rational univariate polynomial at the specified numeric.

Parameters:

a numeric

Returns:: sign of the rational univariate polynomial at the specified numeric.

Definition at line 85 of file RationalUnivariatePolynomial.cpp.

References evaluateAt(), GiNaC::NEGATIVE_SIGN, GiNaC::POSITIVE_SIGN, and GiNaC::ZERO_SIGN.

Referenced by approximateRealRoot(), GiNaCRA::RealAlgebraicNumberIR::refine(), GiNaCRA::RealAlgebraicNumberIR::refineAvoiding(), GiNaCRA::RealAlgebraicNumberFactory::searchRealRoots(), and GiNaCRA::RealAlgebraicNumberNR::sgn().

unsigned GiNaCRA::RationalUnivariatePolynomial::signVariations	(	const list< RationalUnivariatePolynomial > &	seq,
		const numeric &	a
	)		`[static]`

Counts the changes of sign when evaluating the given sequence of real algebraic univariate polynomials at the given numeric.

This method is specially tailored to RationalUnivariatePolynomial.

Parameters:

seq	A sequence of univariate polynomials in possibly different variables.
a

Returns:: positive int

Definition at line 183 of file RationalUnivariatePolynomial.cpp.

References GiNaC::ZERO_SIGN.

Referenced by GiNaCRA::RealAlgebraicNumberIR::add(), calculateSturmCauchyIndex(), countRealRoots(), GiNaCRA::RealAlgebraicNumberIR::mul(), GiNaCRA::RealAlgebraicNumberIR::normalizeInterval(), GiNaCRA::RealAlgebraicNumberFactory::realRoots(), GiNaCRA::RealAlgebraicNumberFactory::realRootsEval(), GiNaCRA::RealAlgebraicNumberIR::refine(), GiNaCRA::RealAlgebraicNumberIR::refineAvoiding(), GiNaCRA::RealAlgebraicNumberFactory::searchRealRoots(), and GiNaCRA::RealAlgebraicNumberIR::sgn().

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::square ( ) const [inline, inherited]

Calculates the square.

Returns:: this polynomial squared

Definition at line 340 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

list< RationalUnivariatePolynomial > GiNaCRA::RationalUnivariatePolynomial::standardSturmSequence	(	const RationalUnivariatePolynomial &	a,
		const RationalUnivariatePolynomial &	b
	)		`[static]`

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

This method is specially tailored to RationalUnivariatePolynomial.

Parameters:

a
b

Returns:: Vector of pointers to the elements of the standard Sturm sequence

Todo:: naming is not according to the source of our other algorithms, this is actually the computation of the signed remainder sequence. SturmSequences are SRemS over P,P'.

Definition at line 173 of file RationalUnivariatePolynomial.cpp.

Referenced by GiNaCRA::RealAlgebraicNumberIR::add(), calculateSturmCauchyIndex(), countRealRoots(), GiNaCRA::RealAlgebraicNumberFactory::evaluateIR(), GiNaCRA::RealAlgebraicNumberIR::mul(), GiNaCRA::RealAlgebraicNumberFactory::realRoots(), GiNaCRA::RealAlgebraicNumberFactory::realRootsEval(), and GiNaCRA::RealAlgebraicNumberIR::sgn().

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

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.

const UnivariatePolynomial GiNaCRA::UnivariatePolynomial::sub ( const UnivariatePolynomial & o ) const [inline, inherited]

Compute the subtraction of this by o in this variable.

Parameters:

o	other polynomial

Returns:

Definition at line 331 of file UnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mEnabledPolynomialCheck, GiNaCRA::UnivariatePolynomial::mVariable, and GiNaCRA::UnivariatePolynomial::UnivariatePolynomial().

Referenced by GiNaCRA::operator-().

const vector< ex > GiNaCRA::UnivariatePolynomial::subresultantCoefficients	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b,
		const subresultantStrategy	strategy = `GENERIC_SUBRESULTANTSTRATEGY`
	)		`[static, inherited]`

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

Parameters:

a	the first Polynomial
b	the second Polynomial
strategy	choice 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 GiNaCRA::UnivariatePolynomial::subresultants().

const list< UnivariatePolynomial > GiNaCRA::UnivariatePolynomial::subresultants	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b,
		const subresultantStrategy	strategy = `GENERIC_SUBRESULTANTSTRATEGY`
	)		`[static, inherited]`

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:

a	the first Polynomial
b	the second Polynomial
strategy	choice 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.

Referenced by GiNaCRA::UnivariatePolynomial::principalSubresultantCoefficients(), and GiNaCRA::UnivariatePolynomial::subresultantCoefficients().

numeric GiNaCRA::RationalUnivariatePolynomial::tcoeff ( ) const [inline]

Returns:: the trailing coefficient of this polynomial

Reimplemented from GiNaCRA::UnivariatePolynomial.

Definition at line 95 of file RationalUnivariatePolynomial.h.

References GiNaCRA::UnivariatePolynomial::mVariable.

UnivariatePolynomial GiNaCRA::UnivariatePolynomial::trunc ( ) const [inherited]

Removes the leading term.

Returns:: the polynomial without leading term

Definition at line 93 of file UnivariatePolynomial.cpp.

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

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

numeric GiNaCRA::RationalUnivariatePolynomial::twoNorm ( ) const

Returns:: Two-norm of the rational univariate polynomial in case this has numeric coefficients.

Definition at line 113 of file RationalUnivariatePolynomial.cpp.

References coeff(), GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::ldegree().

bool GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLess	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b
	)		`[static, inherited]`

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 GiNaCRA::UnivariatePolynomial::isEqual().

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

bool GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessEvenDeg	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b
	)		`[static, inherited]`

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 GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLess().

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

bool GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessEvenLowDeg	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b
	)		`[static, inherited]`

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 GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLess().

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

bool GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessLowDeg	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b
	)		`[static, inherited]`

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 GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLess().

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

bool GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessOddDeg	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b
	)		`[static, inherited]`

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 GiNaCRA::UnivariatePolynomial::degree(), and GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLess().

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

bool GiNaCRA::UnivariatePolynomial::univariatePolynomialIsLessOddLowDeg	(	const UnivariatePolynomial &	a,
		const UnivariatePolynomial &	b
	)		`[static, inherited]`

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: