A class providing useful static methods which produce instances of RealAlgebraicNumberIR. More...

#include <RealAlgebraicNumberFactory.h>

Static Public Member Functions
static bool	equal (const RealAlgebraicNumberPtr &a, const RealAlgebraicNumberPtr &b)
	Tests if the objects encapsulated by the pointers are equal.
static bool	less (const RealAlgebraicNumberPtr &a, const RealAlgebraicNumberPtr &b)
	Compares the objects encapsulated by the pointers and returns true if `a` is less than `b` regardless of the type.
static bool	isRealAlgebraicNumberNR (const RealAlgebraicNumberPtr &a)
	Checks whether `a` is a pointer to a numeric representation.
static bool	isRealAlgebraicNumberIR (const RealAlgebraicNumberPtr &a)
	Checks whether `a` is a pointer to a interval representation.
static list < RealAlgebraicNumberPtr >	realRoots (const RationalUnivariatePolynomial &p, RealAlgebraicNumberSettings::IsolationStrategy pivoting=RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY)
	Isolates the real roots of the given rational univariate polynomial.
static list < RealAlgebraicNumberPtr >	realRootsEval (const UnivariatePolynomial &p, const evalmap &m, RealAlgebraicNumberSettings::IsolationStrategy pivoting=RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY) throw ( invalid_argument )
	Isolates the real roots of the given univariate polynomial by evaluating its parameterized coefficients according to the given evalmap map.
static list < RealAlgebraicNumberPtr >	realRootsEval (const UnivariatePolynomial &p, const vector< RealAlgebraicNumberIRPtr > &a, const vector< symbol > &v, RealAlgebraicNumberSettings::IsolationStrategy pivoting=RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY) throw ( invalid_argument )
	Isolates the real roots of the given univariate polynomial by evaluating its parameterized coefficients according to the given evalmap map.
static list < RealAlgebraicNumberPtr >	commonRealRoots (const list< RationalUnivariatePolynomial > &l)
	Computes the list of common real roots of the given list of rational univariate polynomials.
static const RealAlgebraicNumberPtr	evaluateIR (const UnivariatePolynomial &p, const vector< RealAlgebraicNumberIRPtr > &a, const vector< symbol > &v) throw ( invalid_argument )
	Evaluates the given polynomial p in `variables`, at the given vector of `RealAlgeraicNumberIR`s `r` by substituting all variables.
static const RealAlgebraicNumberPtr	evaluateIR (const UnivariatePolynomial &p, const evalmap m) throw ( invalid_argument )
	Evaluates the coefficients of the given polynomial p, univariate in a variable not occurring in `variables`, at the given vector of `RealAlgeraicNumberIR`s `r` by substituting all variables.
Static Private Member Functions
static void	searchRealRoots (const unsigned varMinLeft, const RationalUnivariatePolynomial &p, const list< RationalUnivariatePolynomial > &seq, const OpenInterval &i, list< RealAlgebraicNumberPtr > *roots, unsigned offset, RealAlgebraicNumberSettings::IsolationStrategy pivoting)
	Helping method to find the real roots of a polynomial recursively.

Detailed Description

A class providing useful static methods which produce instances of RealAlgebraicNumberIR.

Since:: 2011-10-18

Version:: 2012-03-15

Author:: Joachim Redies; Ulrich Loup

Definition at line 49 of file RealAlgebraicNumberFactory.h.

Member Function Documentation

list< RealAlgebraicNumberPtr > GiNaCRA::RealAlgebraicNumberFactory::commonRealRoots ( const list< RationalUnivariatePolynomial > & l ) [static]

Computes the list of common real roots of the given list of rational univariate polynomials.

Note that the contents of the polynomials in l can be changed due to a normalization within the RealAlgebraicNumberIR constructor.

Parameters:

l	list of rational univariate polynomials

Returns:: vector containing the common real roots of the given list of polynomials

Definition at line 279 of file RealAlgebraicNumberFactory.cpp.

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

bool GiNaCRA::RealAlgebraicNumberFactory::equal	(	const RealAlgebraicNumberPtr &	a,
		const RealAlgebraicNumberPtr &	b
	)		`[static]`

Tests if the objects encapsulated by the pointers are equal.

Parameters:

a	smart pointer to a real algebraic number
b	smart pointer to a real algebraic number

Returns:: true if a == b otherwise false

Equal-type equality goes back to original operators. Equality of a numerically-represented object N and an by-interval-represented object I is: N == I iff (A): I.Polynomial() vanishes at N [thus N is among the zeros of the polynomial] and (B): N is contained in I.Interval() [thus N is the zero represented by I].

Definition at line 66 of file RealAlgebraicNumberFactory.cpp.

Referenced by GiNaCRA::SampleList::insert(), less(), GiNaCRA::CAD::liftCheck(), GiNaCRA::operator!=(), and GiNaCRA::operator==().

const RealAlgebraicNumberPtr GiNaCRA::RealAlgebraicNumberFactory::evaluateIR	(	const UnivariatePolynomial &	p,
		const vector< RealAlgebraicNumberIRPtr > &	a,
		const vector< symbol > &	v
	)		throw ( invalid_argument ) `[static]`

Evaluates the given polynomial p in variables, at the given vector of RealAlgeraicNumberIRs r by substituting all variables.

r shall only contain RealAlgebraicNumberIRPtr.

The algorithm assumes that the variables in variables are all variables occurring in p.

Parameters:

p	polynomial to be evaluated in the given variables.
a	vector with interval-represented RealAlgebraicNumbers
v	the variables for evaluation corresponding to the real algebraic point

Returns:: Real algebraic number representing the value of p evaluated at r

See also:: Constraint::satisfiedBy and CAD::samples for usages of this method

Definition at line 450 of file RealAlgebraicNumberFactory.cpp.

Referenced by GiNaCRA::Constraint::satisfiedBy().

const RealAlgebraicNumberPtr GiNaCRA::RealAlgebraicNumberFactory::evaluateIR	(	const UnivariatePolynomial &	p,
		const evalmap	m
	)		throw ( invalid_argument ) `[static]`

Evaluates the coefficients of the given polynomial p, univariate in a variable not occurring in variables, at the given vector of RealAlgeraicNumberIRs r by substituting all variables.

r shall only contain RealAlgebraicNumberIRPtr.

Note that variable i is replaced with an appropriate numeric value corresponding to the i-th RealAlgeraicNumberIR. The algorithm assumes that all variables in variables are coefficient variables.

Parameters:

p	polynomial to be evaluated in the given variables. This should be a univariate polynomial in a variable not occurring in `variables`.
m	map assigning each variable of `p` an interval-represented RealAlgebraicNumber

Returns:: Real algebraic number representing the value of p evaluated according to m

See also:: Constraint::satisfiedBy and CAD::samples for usages of this method

Definition at line 461 of file RealAlgebraicNumberFactory.cpp.

References GiNaCRA::RationalUnivariatePolynomial::countRealRoots(), GiNaCRA::UnivariatePolynomial::diff(), GiNaCRA::OpenInterval::evaluate(), GiNaCRA::UnivariatePolynomial::resultant(), and GiNaCRA::RationalUnivariatePolynomial::standardSturmSequence().

bool GiNaCRA::RealAlgebraicNumberFactory::isRealAlgebraicNumberIR ( const RealAlgebraicNumberPtr & a ) [static]

Checks whether a is a pointer to a interval representation.

Returns:: true if it is a interval representation otherwise false.

Definition at line 142 of file RealAlgebraicNumberFactory.cpp.

bool GiNaCRA::RealAlgebraicNumberFactory::isRealAlgebraicNumberNR ( const RealAlgebraicNumberPtr & a ) [static]

Checks whether a is a pointer to a numeric representation.

Returns:: true if it is a numeric representation otherwise false.

Definition at line 133 of file RealAlgebraicNumberFactory.cpp.

bool GiNaCRA::RealAlgebraicNumberFactory::less	(	const RealAlgebraicNumberPtr &	a,
		const RealAlgebraicNumberPtr &	b
	)		`[static]`

Compares the objects encapsulated by the pointers and returns true if a is less than b regardless of the type.

Parameters:

a	smart pointer to a real algebraic number
b	smart pointer to a real algebraic number

Returns:: true if a < b otherwise false

now intervals in possible IRs are disjoint, as well as numerics of NRs are not contained in the isolating intervals
both numbers can be regarded as unequal (weak ordering is enough)

Definition at line 102 of file RealAlgebraicNumberFactory.cpp.

References equal(), and GiNaCRA::RealAlgebraicNumber::value().

Referenced by GiNaCRA::SampleList::contains(), GiNaCRA::SampleList::insert(), GiNaCRA::CAD::liftCheck(), GiNaCRA::operator<(), GiNaCRA::SampleList::pop(), GiNaCRA::SampleList::popNonroot(), GiNaCRA::SampleList::popNR(), GiNaCRA::SampleList::popRoot(), and GiNaCRA::SampleList::simplify().

list< RealAlgebraicNumberPtr > GiNaCRA::RealAlgebraicNumberFactory::realRoots	(	const RationalUnivariatePolynomial &	p,
		RealAlgebraicNumberSettings::IsolationStrategy	pivoting = `RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY`
	)		`[static]`

Isolates the real roots of the given rational univariate polynomial.

Note that the contents of p can be changed due to a normalization within the RealAlgebraicNumberIR constructor.

Parameters:

p	rational univariate polynomial
pivoting	strategy selection according to RealAlgebraicNumberSettings::IsolationStrategy (standard option is RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY)

Returns:: list containing the real roots of the given polynomial

Definition at line 155 of file RealAlgebraicNumberFactory.cpp.

References GiNaCRA::RationalUnivariatePolynomial::cauchyBound(), GiNaCRA::UnivariatePolynomial::diff(), GiNaCRA::UnivariatePolynomial::hasZeroRoot(), GiNaCRA::UnivariatePolynomial::isConstant(), GiNaCRA::RationalUnivariatePolynomial::maximumNorm(), GiNaCRA::UnivariatePolynomial::nonzeropart(), searchRealRoots(), GiNaCRA::RationalUnivariatePolynomial::signVariations(), and GiNaCRA::RationalUnivariatePolynomial::standardSturmSequence().

Referenced by commonRealRoots(), and GiNaCRA::CAD::samples().

list< RealAlgebraicNumberPtr > GiNaCRA::RealAlgebraicNumberFactory::realRootsEval	(	const UnivariatePolynomial &	p,
		const evalmap &	m,
		RealAlgebraicNumberSettings::IsolationStrategy	pivoting = `RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY`
	)		throw ( invalid_argument ) `[static]`

Isolates the real roots of the given univariate polynomial by evaluating its parameterized coefficients according to the given evalmap map.

Parameters:

p	possibly parameterized univariate polynomial
m	evaluation map for the coefficients of p
pivoting	strategy selection according to RealAlgebraicNumberSettings::IsolationStrategy (standard option is RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY)

Returns:: list containing the real roots of the given polynomial, which is evaluated according to the given evalmap map

Definition at line 199 of file RealAlgebraicNumberFactory.cpp.

References GiNaCRA::abs(), GiNaCRA::UnivariatePolynomial::diff(), GiNaCRA::OpenInterval::evaluate(), GiNaCRA::UnivariatePolynomial::hasZeroRoot(), GiNaCRA::OpenInterval::isZero(), GiNaCRA::RationalUnivariatePolynomial::maximumNorm(), GiNaCRA::UnivariatePolynomial::nonzeropart(), GiNaCRA::RationalUnivariatePolynomial::signVariations(), and GiNaCRA::RationalUnivariatePolynomial::standardSturmSequence().

Referenced by realRootsEval(), and GiNaCRA::CAD::samples().

list< RealAlgebraicNumberPtr > GiNaCRA::RealAlgebraicNumberFactory::realRootsEval	(	const UnivariatePolynomial &	p,
		const vector< RealAlgebraicNumberIRPtr > &	a,
		const vector< symbol > &	v,
		RealAlgebraicNumberSettings::IsolationStrategy	pivoting = `RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY`
	)		throw ( invalid_argument ) `[static]`

Isolates the real roots of the given univariate polynomial by evaluating its parameterized coefficients according to the given evalmap map.

Parameters:

p	possibly parameterized univariate polynomial
a	vector with interval-represented RealAlgebraicNumbers
v	the variables for evaluation corresponding to the real algebraic point
pivoting	strategy selection according to RealAlgebraicNumberSettings::IsolationStrategy (standard option is RealAlgebraicNumberSettings::DEFAULT_ISOLATIONSTRATEGY)

Returns:: list containing the real roots of the given polynomial, which is evaluated according to the given variables/numbers

Definition at line 265 of file RealAlgebraicNumberFactory.cpp.

References realRootsEval().

void GiNaCRA::RealAlgebraicNumberFactory::searchRealRoots	(	const unsigned	varMinLeft,
		const RationalUnivariatePolynomial &	p,
		const list< RationalUnivariatePolynomial > &	seq,
		const OpenInterval &	i,
		list< RealAlgebraicNumberPtr > *	roots,
		unsigned	offset,
		RealAlgebraicNumberSettings::IsolationStrategy	pivoting
	)		`[static, private]`

Helping method to find the real roots of a polynomial recursively.

This method offers several solving strategies available by setting the argument pivoting. All have in common that 0 is returned as RealAlgebraicNumberNR if it happens to be a valid root. For details on the strategies

See also:

Parameters:

varMinLeft	number of sign variations of seq at the minimal left endpoint
p	polynomial whose roots are searched
seq	standard Sturm of p
i	isolating interval which shall be searched for real roots recursively
offset	the number of roots to subtract from the actual root count in the interval `i`. The standard value is 0 which also holds for the initial call by the Cauchy bounds. The offset should be set to `(p.sgn(i.Left()) == GiNaC::ZERO_SIGN) + (p.sgn(i.Right()) == GiNaC::ZERO_SIGN)`.
roots	list of roots found so far
pivoting	strategy selection according to RealAlgebraicNumberSettings::IsolationStrategy

rootCount is the number of real roots in i due to Sturm's theorem, where i is viewed as a CLOSED interval. Note that the left and right bounds of the interval i must be no roots of the polynomial p in Sturm's theorem. Since this might happen anyway, we have to check the bounds before the recursive calls and introduce appropriate offsets.

Definition at line 299 of file RealAlgebraicNumberFactory.cpp.

References GiNaCRA::RationalUnivariatePolynomial::approximateRealRoot(), GiNaCRA::RealAlgebraicNumberSettings::BINARYSAMPLE_ISOLATIONSTRATEGY, GiNaCRA::RealAlgebraicNumberSettings::GENERIC_ISOLATIONSTRATEGY, GiNaCRA::OpenInterval::left(), GiNaCRA::OpenInterval::midpoint(), GiNaCRA::OpenInterval::right(), GiNaCRA::OpenInterval::sample(), GiNaCRA::RationalUnivariatePolynomial::sgn(), GiNaCRA::RationalUnivariatePolynomial::signVariations(), GiNaCRA::RealAlgebraicNumberSettings::SIMPLE_ISOLATIONSTRATEGY, GiNaCRA::RealAlgebraicNumberSettings::TERNARYNEWTON_ISOLATIONSTRATEGY, GiNaCRA::RealAlgebraicNumberSettings::TERNARYSAMPLE_ISOLATIONSTRATEGY, and GiNaC::ZERO_SIGN.

Referenced by realRoots().

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

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Function Documentation