A class for handling regular chains of arbitrary dimension. More...

#include <regularchain.hpp>

The regular chain classes in BPAS provide a collection of routines for solving systems of algebraic equations by means of exact methods, a.k.a. symbolic computation. The main commands for accomplishing this are the $\texttt{triangularize}$ and $\texttt{intersect}$ methods of the $\texttt{RegularChain}$ class and the $\texttt{intersect}$ method of the $\texttt{ZeroDimensionalRegularChain}$ class. The objects of both these classes are regular chains . Becuase regular chains are mathematical objects that algebraically encode geometric components of the solution space, the solutions to a system of algebraic equations can be expressed as a set of regular chains. This is precisely what $\texttt{triangularize}$ and $\texttt{intersect}$ accomplish: for an input polynomial $p$ (for $\texttt{intersect}$ ) or algebraic system $S$ (for $\texttt{triangularize}$ ), the output is a description of the solution set as a collection of $\texttt{RegularChain}$ objects. More... (pdf)

Simplified semantic inheritance diagram for RegularChain< Field, RecursivePoly >:

Full inheritance diagram for RegularChain< Field, RecursivePoly >:

[legend]

Public Member Functions
	RegularChain ()
	Default constructor: creates an empty regular chain of variable size with empty list of transcendentals. More...

	RegularChain (const std::vector< Symbol > &xs)
	Construct an empty fixed variable list regular chain in the decreasingly ordered variables given by xs with empty list of transcendentals. More...

	RegularChain (const std::vector< Symbol > &xs, const std::vector< Symbol > &ts)
	Construct an empty fixed variable list regular chain in the decreasingly ordered variables given by xs and list of transcendentals given by ts. More...

	RegularChain (const RecursivePoly &p)
	Construct a variable regular chain containing p, such that the variables of p are treated as algebraic, with empty list of transcendentals. More...

	RegularChain (const RecursivePoly &p, const std::vector< Symbol > &ts)
	Construct a variable regular chain containing p, such that the variables in ts are treated as transcendental, while any remaining variables of p are treated as algebraic. More...

	RegularChain (const std::vector< RecursivePoly > polys)
	Construct a fixed regular chain containing the polynomials in polys. More...

	RegularChain (const ZeroDimensionalRegularChain< Field, RecursivePoly > &a)
	Copy constructor taking a zero-dimensional regular chain as input. More...

	RegularChain (const RegularChain< Field, RecursivePoly > &a)
	Copy constructor. More...

	RegularChain (const TriangularSet< Field, RecursivePoly > &a)
	Copy constructor taking a triangular set as input, assuming that the triangular set is a regular chain. More...

	RegularChain (ZeroDimensionalRegularChain< Field, RecursivePoly > &&a)
	Move constructor taking an r-value zero-dimensional regular chain as input. More...

	RegularChain (RegularChain< Field, RecursivePoly > &&a)
	Move constructor. More...

	RegularChain (TriangularSet< Field, RecursivePoly > &&a)
	Move constructor taking an r-value triangular set as input, assuming that the triangular set is a regular chain. More...

	RegularChain (const std::vector< Symbol > &&vs, const std::vector< Symbol > &&avs, const std::vector< Symbol > &&tvs, const std::vector< RecursivePoly > &&ts, TriangularSetMode tsm, const mpz_class &c)
	Computational constructor: creates a regular chain given all the data. More...

RegularChain< Field, RecursivePoly > &	operator= (const ZeroDimensionalRegularChain< Field, RecursivePoly > &a)
	Assignment operator = for a zero-dimensional regular chain. More...

RegularChain< Field, RecursivePoly > &	operator= (const RegularChain< Field, RecursivePoly > &a)
	Assignment operator =. More...

RegularChain< Field, RecursivePoly > &	operator= (const TriangularSet< Field, RecursivePoly > &a)

BPASTriangularSet< Field, RecursivePoly > &	operator= (const BPASTriangularSet< Field, RecursivePoly > &a) override
	Assignment operator = imposed by abstract class BPASTriangularSet. More...

BPASRegularChain< Field, RecursivePoly > &	operator= (const BPASRegularChain< Field, RecursivePoly > &a) override
	Assignment operator = imposed by abstract class BPASRegularChain. More...

RegularChain< Field, RecursivePoly > &	operator= (ZeroDimensionalRegularChain< Field, RecursivePoly > &&a)
	Move assignment operator = taking an r-value zero-dimensional regular chain as input. More...

RegularChain< Field, RecursivePoly > &	operator= (RegularChain< Field, RecursivePoly > &&a)
	Move assignment operator =. More...

RegularChain< Field, RecursivePoly > &	operator= (TriangularSet< Field, RecursivePoly > &&a)

BPASTriangularSet< Field, RecursivePoly > &	operator= (BPASTriangularSet< Field, RecursivePoly > &&a) override
	Move assignment operator = imposed by abstract class BPASTriangularSet. More...

BPASRegularChain< Field, RecursivePoly > &	operator= (BPASRegularChain< Field, RecursivePoly > &&a) override
	Move assignment operator = imposed by abstract class BPASRegularChain. More...

RegularChain< Field, RecursivePoly >	operator+ (const RecursivePoly &p) const
	Add operator +: Adds a polynomial to a regular chain and returns a new regular chain, assuming that the main variable of p is above any in the current object and that init(p) is regular modulo the saturated ideal of the current object. More...

RegularChain< Field, RecursivePoly > &	operator+= (const RecursivePoly &p)
	Add assignment operator +=: Adds a polynomial to a regular chain, assuming that the main variable of p is above any in the current object and that init(p) is regular modulo the saturated ideal of the current object. More...

RegularChain< Field, RecursivePoly >	operator+ (const RegularChain< Field, RecursivePoly > &T) const
	Add operator +: Adds a regular chain to a regular chain and returns a new regular chain, assuming that the input is above the current object and the result of adding the chains is a regular chain. More...

RegularChain< Field, RecursivePoly > &	operator+= (const RegularChain< Field, RecursivePoly > &T)
	Add assignment operator +=: Adds a regular chain to a regular chain, assuming that the input is above the current object and the result adding the chains is a regular chain. More...

bool	operator== (const RegularChain< Field, RecursivePoly > &a) const
	Identity operator ==. More...

bool	operator!= (const RegularChain< Field, RecursivePoly > &a) const
	Negated identity operator !=. More...

int	numberOfVariables () const
	Get the number of (potentially algebraic) variables in the current object. More...

int	options () const
	Get the encoded options of the regular chain, a bitwise or of RegularChainOption values. More...

void	setOptions (int opts)
	Set the encoded options of the regular chain. More...

bool	isSquareFree () const
	Find out if the regular chain is known to be squarefree. More...

bool	isSaturatedIdealPrime () const

bool	isInSaturatedIdealMinimal (const RecursivePoly &p) const
	Efficiently find out if the input polynomial is in the saturated ideal of the current regular chain. More...

bool	isInSaturatedIdealMinimal_inner (const RecursivePoly &p) const

bool	isInSaturatedIdeal (const RecursivePoly &p) const
	Find out if the input polynomial is in the saturated ideal of the current regular chain. More...

bool	isInSaturatedIdeal (const RecursivePoly &p, RecursivePoly &redp) const
	Find out if the input polynomial is in the saturated ideal of the current regular chain. More...

bool	isInRadicalSaturatedIdeal (const RecursivePoly &p) const
	Find out if the input polynomial is in the radical saturated ideal of the current regular chain. More...

bool	isRegular (const RecursivePoly &p) const
	Find out if the input polynomial is regular modulo the saturated ideal of the current regular chain. More...

bool	isIteratedResultantZeroModular (const RecursivePoly &p) const
	Using a modular method determine if the iterated resultant of p and this regular chain is zero or not. More...

std::vector< Symbol >	variables () const
	Get the (potentially algebriac) variable names in decreasing order. More...

RecursivePoly	select (const Symbol &s) const
	Select the polynomial in the current object with main variable s, if it exists. More...

void	lower (const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
	Returns the regular chain consisting of polynomials with main variable strictly less than s. More...

void	upper (const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
	Returns the regular chain consisting of polynomials with main variable strictly greater than s. More...

void	lowerSlice (const Symbol &s)
	Destructively converts the current object into lower(s) by changing the set of (potentially algebraic) variables to be only those below s in the variable order. More...

std::vector< RegularChain< Field, RecursivePoly > >	triangularize (const std::vector< RecursivePoly > &F, bool lazardDecompose=false, int type=0)
	Compute a triangular decomposition of the list of input polynomials. More...

std::vector< RegularChain< Field, RecursivePoly > >	intersect (const RecursivePoly &p, bool lazardDecompose=false, int heightBound=0) const
	Compute the common solutions of the input polynomial and the current regular chain. More...

std::vector< PolyChainPair< RecursivePoly, RegularChain< Field, RecursivePoly > > >	regularize (const RecursivePoly &p, bool lazardDecompose=false, int heightBound=0) const
	Compute a decomposition of the current object such that on each component the input polynomial is either zero or regular modulo the saturated ideal of that component. More...

std::vector< PolyChainPair< RecursivePoly, RegularChain< Field, RecursivePoly > > >	regularGCD (const RecursivePoly &p, const RecursivePoly &q, const Symbol &v, const SubResultantChain< RecursivePoly, RecursivePoly > &src, bool lazardDecompose=false, int heightBound=0) const
	Compute the gcd of two input polynomials p and q modulo the saturated ideal of the current object. More...

std::vector< RegularChain< Field, RecursivePoly > >	squareFreePart (const RecursivePoly &p, const Symbol &v, bool lazardDecompose=false, int heightBound=0, int options=ASSUME_REGULAR) const
	A routine that decomposes the regular chain formed from the current object and an input polynomial into a set of squarefree regular chains. More...

void	randomRegularChain (int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
	Generate a random regular chain based on the number of terms of the polynomials in the chain. More...

void	randomRegularChain (int nVars, int nAlgVars, int nTrcVars, std::vector< int > maxDegs, unsigned long int coefBound, double pSparsity, bool includeNeg)
	Generate a random regular chain based on a list of maximum degrees of variables in the polynomials in the chain. More...

bool	cleanSet (std::vector< RecursivePoly > &polys) const
	Reduce the polynomials of the input vector modulo the saturated ideal of the current object and detect any obvious inconsistency among the set. More...

Public Member Functions inherited from TriangularSet< Field, RecursivePoly >
	TriangularSet ()
	Default constructor: creates an empty triangular set of variable size with empty list of transcendentals. More...

	TriangularSet (const std::vector< Symbol > &xs)
	Construct an empty triangular set of fixed size in the s decreasingly ordered variables given by xs with empty list of transcendentals. More...

	TriangularSet (const std::vector< Symbol > &xs, const std::vector< Symbol > &ts)
	Construct an empty triangular set of fixed size in the s decreasingly ordered variables given by xs and list of transcendentals given by ts. More...

	TriangularSet (const RecursivePoly &p)
	Construct a variable triangular set containing p, such that the variables of p are treated as (potentially algebraic) variables, with empty list of transcendentals. More...

	TriangularSet (const RecursivePoly &p, const std::vector< Symbol > &ts)
	Construct a variable triangular set containing p, such that the variables in ts are treated as transcendental, while any remaining variables of p are treated as (potentially algebraic) variables. More...

	TriangularSet (const TriangularSet< Field, RecursivePoly > &a)
	Copy constructor. More...

	TriangularSet (TriangularSet< Field, RecursivePoly > &&a)
	Copy constructor. More...

	TriangularSet (const std::vector< Symbol > &&vs, const std::vector< Symbol > &&avs, const std::vector< Symbol > &&tvs, const std::vector< RecursivePoly > &&ts, TriangularSetMode tsm, const mpz_class &c)
	Move constructor. More...

	~TriangularSet ()
	Deconstructor. More...

bool	isEmpty () const
	Copy an object derived from abstract BPASTriangularSet class to type of current object. More...

bool	isConstantPolynomial (const RecursivePoly &p) const
	Tests if the polynomial is constant relative to the TriangularSet, i.e., whether it is and element of the Field or its only variables are transcendental. More...

TriangularSet< Field, RecursivePoly > &	operator= (const TriangularSet< Field, RecursivePoly > &a)
	Assignment operator =. More...

BPASTriangularSet< Field, RecursivePoly > &	operator= (const BPASTriangularSet< Field, RecursivePoly > &a) override
	Assignment operator =. More...

TriangularSet< Field, RecursivePoly > &	operator= (TriangularSet< Field, RecursivePoly > &&a)
	Move assignment operator =. More...

BPASTriangularSet< Field, RecursivePoly > &	operator= (BPASTriangularSet< Field, RecursivePoly > &&a) override
	Move assignment operator =. More...

TriangularSet< Field, RecursivePoly >	operator+ (const RecursivePoly &p)
	Add operator +. More...

TriangularSet< Field, RecursivePoly > &	operator+= (const RecursivePoly &p)
	Add assignment operator +=. More...

bool	operator== (const TriangularSet< Field, RecursivePoly > &a) const
	Identity operator ==. More...

bool	operator!= (const TriangularSet< Field, RecursivePoly > &a) const
	Negated identity operator !=. More...

int	numberOfVariables () const
	Get the number of variables. More...

int	size () const
	Get the size of the triangular set. More...

int	numberOfAlgebraicVariables () const
	Get the number of algebraic variables. More...

int	numberOfTranscendentalVariables () const
	Get the number of transcendental variables. More...

std::vector< Symbol >	variables () const
	Get the variable names in decreasing order. More...

std::vector< Symbol >	mainVariables () const
	Get the algebraic variables. More...

std::vector< Symbol >	transcendentalVariables () const
	Get the transcendentalVariables variables. More...

std::vector< Symbol >	allVariables () const
	Get the list of variables followed by the transcendental variables. More...

bool	isAlgebraic (const Symbol &s) const
	Determine if the input variable s is algebraic, i.e., if the triangular set contains a polynomial with s its as leading variable. More...

bool	isStronglyNormalized () const
	Return true if the triangular set is strongly normalized, i.e., the initals of all polynomials are in the Field; return false otherwise. More...

std::vector< RecursivePoly >	polynomials () const
	Get the vector of polynoials in the triangular set. More...

int	dimension () const
	Return the dimension of the triangular set (understood in terms of the space of (potentially algebraic) variables). More...

int	dimensionLower (Symbol v) const
	Return the dimension of the triangular set lower(v) (understood in terms of the space of (potentially algebraic) variables). More...

int	codimension () const
	Return the codimension of the triangular set (understood in terms of the space of (potentially algebraic) variables). More...

bool	canComputeInDimensionZero (const RecursivePoly &p, bool excludeMainVariable=false) const
	Test to determine whether the triangular set can be treated as zero dimensional, i.e., whether the triangular set becomes zero dimensional when all non-algebraic variables are removed and whether the polynomial p contains only algebraic variables. More...

bool	isZeroDimensionalMathematically () const
	Test to determine if only algebraic variables (aside from transcendentals) appear in the polynomials of the triangular set. More...

RecursivePoly	select (const Symbol &s) const
	Select a polynomial given the leading variable; if no such polynomial, 0 is returned. More...

void	makePrimitive ()
	Replace each polynomial of the triangular set with its primitive part. More...

void	lower (const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
	Returns the triangular set consisting of polynomials with main variable strictly less than s. More...

void	upper (const Symbol &s, BPASTriangularSet< Field, RecursivePoly > &ts) const
	Returns the triangular set consisting of polynomials with main variable strictly greater than s. More...

void	cutChain (const TriangularSet< Field, RecursivePoly > &T, const Symbol &v, TriangularSet< Field, RecursivePoly > &Tlv, RecursivePoly &Tv, TriangularSet< Field, RecursivePoly > &Tgv) const
	Cut an input triangular set at the symbol v, returning the subchain below v, the polynomial with main variable v and the subchain above v. More...

void	cutChain (const Symbol &v, RecursivePoly &Tv, TriangularSet< Field, RecursivePoly > &Tgv) const
	Cut the current object at the symbol v, returning the polynomial with main variable v and the subchain above v. More...

void	cutChain (const Symbol &v, TriangularSet< Field, RecursivePoly > &Tlv, RecursivePoly &Tv) const
	Cut the current object at the symbol v, returning the subchain below v and the polynomial with main variable v. More...

RecursivePoly	pseudoDivide (const RecursivePoly &p, std::vector< RecursivePoly > quo=NULL, RecursivePoly c=NULL) const
	Pseudo division: return the pseudo-remainder, the pseudo-quotients and c such that c*p = ∑(q_i T_i) + r. More...

RecursivePoly	normalForm (const RecursivePoly &p, std::vector< RecursivePoly > *Q=NULL) const
	Return the normalForm of the input polynomial modulo the triangular set in the sense of Groebner basis. More...

RecursivePoly	reduce (const RecursivePoly &p) const
	Reduce the input polynomial modulo the triangular set. More...

RecursivePoly	reduce (const RecursivePoly &p, RecursivePoly &c, bool takeMainPrimitivePart=false, bool onlyInDimZero=false) const
	returns r such that c*r = p modulo sat(T) such that c has no algebraic variables, and c is returned as an input parameter. More...

RecursivePoly	randomTriangularSetPolynomial (std::vector< Symbol > variables, int algVar, std::vector< Symbol > transcendentalVariables, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
	Generate a random triangular set polynomial based on its number of terms. More...

RecursivePoly	randomTriangularSetPolynomial (std::vector< Symbol > variables, int algVar, std::vector< Symbol > transcendentalVariables, std::vector< int > maxDegs, unsigned long int coefBound, double pSparsity, bool includeNeg)
	Generate a random triangular set polynomial based on its maximum degrees in its variables. More...

void	randomTriangularSet (int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
	Generate a random triangular set based on the number of terms of its polynomials. More...

void	randomStronglyNormalizedTriangularSet (int nVars, int nAlgVars, int nTrcVars, int nTerms, unsigned long int coefBound, int pSparsity, bool includeNeg)
	Generate a random strongly normalized triangular set based on the number of terms in its polynomials. More...

void	display ()
	Display the triangular set. More...

ExpressionTree	convertToExpressionTree () const
	Convert a triangular set to an expression tree (array of its polynomials). More...

Static Public Member Functions
static std::vector< RegularChain< Field, RecursivePoly > >	constructChains (const TriangularSet< Field, RecursivePoly > &T)
	Construct a set of regular chains from an input triangular set by triangularizing the elements of the input. More...

static bool	compareCertifiedNoSplit (const RegularChain< Field, RecursivePoly > &rc1, const RegularChain< Field, RecursivePoly > &rc2)
	Determine whether or not the quasicomponent of the first regular chain is contained in the quasicomponent of the second using a certified method that returns true if the first is contained in the second and false if not. More...

static bool	compareHeuristicNoSplit (const RegularChain< Field, RecursivePoly > &rc1, const RegularChain< Field, RecursivePoly > &rc2)
	Determine whether or not the quasicomponent of the first regular chain is contained in the quasicomponent of the second using a heuristic method that returns true when the first is contained in the second and false when no conclusion is possible. More...

static void	removeRedundantChains (const std::vector< RegularChain< Field, RecursivePoly >> &lrc, std::vector< RegularChain< Field, RecursivePoly >> &results)
	Remove redundancy from the input list of regular chains. More...

Friends
void	triangularizeTask (const RegularChain< Field, RecursivePoly > &rc, std::vector< RecursivePoly > &polys, bool lazardDecompose, int heightBound, TaskScheduler *tasks, std::shared_ptr< SynchronizedWriteVector< RegularChain< Field, RecursivePoly >>> results)

void	intersectOne (int j, const RegularChain< Field, RecursivePoly > &T, const RecursivePoly &p, int lazardDecompose, int heightBound, SynchronizedWriteVector< RegularChain< Field, RecursivePoly >> &)

Detailed Description

template<class Field, class RecursivePoly>
class RegularChain< Field, RecursivePoly >

A class for handling regular chains of arbitrary dimension.

A RegularChain contains polynomials of type BPASRecursivelyViewedPolynomial, which have coefficients in a BPASField.

Constructor & Destructor Documentation

◆ RegularChain() [1/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( )

Default constructor: creates an empty regular chain of variable size with empty list of transcendentals.

Parameters

◆ RegularChain() [2/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( const std::vector< Symbol > & xs )

Construct an empty fixed variable list regular chain in the decreasingly ordered variables given by xs with empty list of transcendentals.

Parameters

xs	The variable names

◆ RegularChain() [3/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain	(	const std::vector< Symbol > &	xs,
		const std::vector< Symbol > &	ts
	)

Construct an empty fixed variable list regular chain in the decreasingly ordered variables given by xs and list of transcendentals given by ts.

Parameters

xs	The variable names
ts	The transcendental variable names

◆ RegularChain() [4/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( const RecursivePoly & p )

Construct a variable regular chain containing p, such that the variables of p are treated as algebraic, with empty list of transcendentals.

Parameters

p	The polynomial to add

◆ RegularChain() [5/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain	(	const RecursivePoly &	p,
		const std::vector< Symbol > &	ts
	)

Construct a variable regular chain containing p, such that the variables in ts are treated as transcendental, while any remaining variables of p are treated as algebraic.

Parameters

p	The polynomial to add
ts	The transcendental variable names

◆ RegularChain() [6/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( const std::vector< RecursivePoly > polys )

Construct a fixed regular chain containing the polynomials in polys.

It is assumed that the polynomials in polys form a valid regular chain.

Parameters

polys a list of recursively viewed polynomials.

◆ RegularChain() [7/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( const ZeroDimensionalRegularChain< Field, RecursivePoly > & a )

Copy constructor taking a zero-dimensional regular chain as input.

Parameters

a	A zero-dimensional regular chain

◆ RegularChain() [8/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( const RegularChain< Field, RecursivePoly > & a )

Copy constructor.

Parameters

a	A regular chain

◆ RegularChain() [9/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( const TriangularSet< Field, RecursivePoly > & a )

Copy constructor taking a triangular set as input, assuming that the triangular set is a regular chain.

Parameters

a	A triangular set

◆ RegularChain() [10/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( ZeroDimensionalRegularChain< Field, RecursivePoly > && a )

Move constructor taking an r-value zero-dimensional regular chain as input.

Parameters

a	An r-value reference zero-dimensional regular chain

◆ RegularChain() [11/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( RegularChain< Field, RecursivePoly > && a )

Move constructor.

Parameters

a	An r-value reference regular chain

◆ RegularChain() [12/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain ( TriangularSet< Field, RecursivePoly > && a )

Move constructor taking an r-value triangular set as input, assuming that the triangular set is a regular chain.

Parameters

a	An r-value reference triangular set

◆ RegularChain() [13/13]

template<class Field, class RecursivePoly>

RegularChain< Field, RecursivePoly >::RegularChain	(	const std::vector< Symbol > &&	vs,
		const std::vector< Symbol > &&	avs,
		const std::vector< Symbol > &&	tvs,
		const std::vector< RecursivePoly > &&	ts,
		TriangularSetMode	tsm,
		const mpz_class &	c
	)

Computational constructor: creates a regular chain given all the data.

Parameters

vs	rvalue reference to variables of the regular chain
avs	rvalue reference to algebraic variables of the regular chain
tvs	rvalue reference to transcendental variables of the regular chain
polys	rvalue reference to polynomials of the regular chain
tsm	whether the regular chain is variable or fixed
c	characteristic of the regular chain

Member Function Documentation

◆ cleanSet()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::cleanSet ( std::vector< RecursivePoly > & polys ) const

Reduce the polynomials of the input vector modulo the saturated ideal of the current object and detect any obvious inconsistency among the set.

Parameters

polys a vector of recursively viewed polynomials

◆ compareCertifiedNoSplit()

template<class Field, class RecursivePoly>

static bool RegularChain< Field, RecursivePoly >::compareCertifiedNoSplit	(	const RegularChain< Field, RecursivePoly > &	rc1,
		const RegularChain< Field, RecursivePoly > &	rc2
	)

static

Determine whether or not the quasicomponent of the first regular chain is contained in the quasicomponent of the second using a certified method that returns true if the first is contained in the second and false if not.

Parameters

rc1	the first regular chain
rc1	the second regular chain

◆ compareHeuristicNoSplit()

template<class Field, class RecursivePoly>

static bool RegularChain< Field, RecursivePoly >::compareHeuristicNoSplit	(	const RegularChain< Field, RecursivePoly > &	rc1,
		const RegularChain< Field, RecursivePoly > &	rc2
	)

static

Determine whether or not the quasicomponent of the first regular chain is contained in the quasicomponent of the second using a heuristic method that returns true when the first is contained in the second and false when no conclusion is possible.

Parameters

rc1	the first regular chain
rc1	the second regular chain

◆ constructChains()

template<class Field, class RecursivePoly>

static std::vector<RegularChain<Field,RecursivePoly> > RegularChain< Field, RecursivePoly >::constructChains ( const TriangularSet< Field, RecursivePoly > & T )

static

Construct a set of regular chains from an input triangular set by triangularizing the elements of the input.

Parameters

T	A triangular set

◆ intersect()

template<class Field, class RecursivePoly>

std::vector<RegularChain<Field,RecursivePoly> > RegularChain< Field, RecursivePoly >::intersect	(	const RecursivePoly &	p,
		bool	lazardDecompose = `false`,
		int	heightBound = `0`
	)		const

Compute the common solutions of the input polynomial and the current regular chain.

More precisely, this routine computes the intersection of the varieties of the input polynomial and the current regular chain, expressed as a set of regular chains.

Parameters

p	a recursively viewed polynomial

◆ isInRadicalSaturatedIdeal()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isInRadicalSaturatedIdeal ( const RecursivePoly & p ) const

Find out if the input polynomial is in the radical saturated ideal of the current regular chain.

Parameters

p	a recursively viewed polynomial

◆ isInSaturatedIdeal() [1/2]

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isInSaturatedIdeal ( const RecursivePoly & p ) const

Find out if the input polynomial is in the saturated ideal of the current regular chain.

Parameters

p	a recursively viewed polynomial

◆ isInSaturatedIdeal() [2/2]

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isInSaturatedIdeal	(	const RecursivePoly &	p,
		RecursivePoly &	redp
	)		const

Find out if the input polynomial is in the saturated ideal of the current regular chain.

and return the reduced input polynomial.

Parameters

p	a recursively viewed polynomial

◆ isInSaturatedIdealMinimal()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isInSaturatedIdealMinimal ( const RecursivePoly & p ) const

Efficiently find out if the input polynomial is in the saturated ideal of the current regular chain.

Parameters

p	a recursively viewed polynomial

◆ isIteratedResultantZeroModular()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isIteratedResultantZeroModular ( const RecursivePoly & p ) const

Using a modular method determine if the iterated resultant of p and this regular chain is zero or not.

Parameters

p	a recursively viewed polynomial

Returns: true iff the iterated resultant is zero.

◆ isRegular()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isRegular ( const RecursivePoly & p ) const

Find out if the input polynomial is regular modulo the saturated ideal of the current regular chain.

Parameters

p	a recursively viewed polynomial

◆ isSquareFree()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::isSquareFree ( ) const

inline

Find out if the regular chain is known to be squarefree.

Parameters

◆ lower()

template<class Field, class RecursivePoly>

void RegularChain< Field, RecursivePoly >::lower	(	const Symbol &	s,
		BPASTriangularSet< Field, RecursivePoly > &	ts
	)		const

virtual

Returns the regular chain consisting of polynomials with main variable strictly less than s.

Parameters

s	symbol of the main variable of specified element of the regular chain
ts	The returned regular chain

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ lowerSlice()

template<class Field, class RecursivePoly>

void RegularChain< Field, RecursivePoly >::lowerSlice ( const Symbol & s )

Destructively converts the current object into lower(s) by changing the set of (potentially algebraic) variables to be only those below s in the variable order.

Parameters

s	symbol of the main variable of specified element of the regular chain

◆ numberOfVariables()

template<class Field, class RecursivePoly>

int RegularChain< Field, RecursivePoly >::numberOfVariables ( ) const

inlinevirtual

Get the number of (potentially algebraic) variables in the current object.

Parameters

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ operator!=()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::operator!= ( const RegularChain< Field, RecursivePoly > & a ) const

Negated identity operator !=.

Parameters

a	A regular chain

◆ operator+() [1/2]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly> RegularChain< Field, RecursivePoly >::operator+ ( const RecursivePoly & p ) const

Add operator +: Adds a polynomial to a regular chain and returns a new regular chain, assuming that the main variable of p is above any in the current object and that init(p) is regular modulo the saturated ideal of the current object.

Parameters

p	A recursively viewed polynomial

◆ operator+() [2/2]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly> RegularChain< Field, RecursivePoly >::operator+ ( const RegularChain< Field, RecursivePoly > & T ) const

Add operator +: Adds a regular chain to a regular chain and returns a new regular chain, assuming that the input is above the current object and the result of adding the chains is a regular chain.

Parameters

p	A regular chain

◆ operator+=() [1/2]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator+= ( const RecursivePoly & p )

Add assignment operator +=: Adds a polynomial to a regular chain, assuming that the main variable of p is above any in the current object and that init(p) is regular modulo the saturated ideal of the current object.

Parameters

p	A recursively viewed polynomial

◆ operator+=() [2/2]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator+= ( const RegularChain< Field, RecursivePoly > & T )

Add assignment operator +=: Adds a regular chain to a regular chain, assuming that the input is above the current object and the result adding the chains is a regular chain.

Parameters

p	A regular chain

◆ operator=() [1/8]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( const ZeroDimensionalRegularChain< Field, RecursivePoly > & a )

Assignment operator = for a zero-dimensional regular chain.

Parameters

a	A regular chain

◆ operator=() [2/8]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( const RegularChain< Field, RecursivePoly > & a )

Assignment operator =.

Parameters

a	A regular chain

◆ operator=() [3/8]

template<class Field, class RecursivePoly>

BPASTriangularSet<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( const BPASTriangularSet< Field, RecursivePoly > & a )

overridevirtual

Assignment operator = imposed by abstract class BPASTriangularSet.

Parameters

a	A triangular set

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ operator=() [4/8]

template<class Field, class RecursivePoly>

BPASRegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( const BPASRegularChain< Field, RecursivePoly > & a )

overridevirtual

Assignment operator = imposed by abstract class BPASRegularChain.

Parameters

a	A regular chain

Implements BPASRegularChain< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ operator=() [5/8]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( ZeroDimensionalRegularChain< Field, RecursivePoly > && a )

Move assignment operator = taking an r-value zero-dimensional regular chain as input.

Parameters

a	An r-value reference zero-dimensional regular chain

◆ operator=() [6/8]

template<class Field, class RecursivePoly>

RegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( RegularChain< Field, RecursivePoly > && a )

Move assignment operator =.

Parameters

a	An r-value reference regular chain

◆ operator=() [7/8]

template<class Field, class RecursivePoly>

BPASTriangularSet<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( BPASTriangularSet< Field, RecursivePoly > && a )

overridevirtual

Move assignment operator = imposed by abstract class BPASTriangularSet.

Parameters

a	An r-value reference triangular set

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ operator=() [8/8]

template<class Field, class RecursivePoly>

BPASRegularChain<Field,RecursivePoly>& RegularChain< Field, RecursivePoly >::operator= ( BPASRegularChain< Field, RecursivePoly > && a )

overridevirtual

Move assignment operator = imposed by abstract class BPASRegularChain.

Parameters

a	An r-value reference regular chain

Implements BPASRegularChain< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ operator==()

template<class Field, class RecursivePoly>

bool RegularChain< Field, RecursivePoly >::operator== ( const RegularChain< Field, RecursivePoly > & a ) const

Identity operator ==.

Parameters

a	A regular chain

◆ options()

template<class Field, class RecursivePoly>

int RegularChain< Field, RecursivePoly >::options ( ) const

Get the encoded options of the regular chain, a bitwise or of RegularChainOption values.

Parameters

◆ randomRegularChain() [1/2]

template<class Field, class RecursivePoly>

void RegularChain< Field, RecursivePoly >::randomRegularChain	(	int	nVars,
		int	nAlgVars,
		int	nTrcVars,
		int	nTerms,
		unsigned long int	coefBound,
		int	pSparsity,
		bool	includeNeg
	)

Generate a random regular chain based on the number of terms of the polynomials in the chain.

Parameters

nVars	number of variables
nAlgVars	number of algebraic variables
nTrcVars	number of transcendental variables
nTerms	number of terms in each polynomial
coefBound	bound on the coefficient size
pSparsity	sparsity of the polynomial in the term separation sense
includeNeg	whether to include negative coefficients

◆ randomRegularChain() [2/2]

template<class Field, class RecursivePoly>

void RegularChain< Field, RecursivePoly >::randomRegularChain	(	int	nVars,
		int	nAlgVars,
		int	nTrcVars,
		std::vector< int >	maxDegs,
		unsigned long int	coefBound,
		double	pSparsity,
		bool	includeNeg
	)

Generate a random regular chain based on a list of maximum degrees of variables in the polynomials in the chain.

Parameters

nVars	number of variables
nAlgVars	number of algebraic variables
nTrcVars	number of transcendental variables
maxDegs	maximum degrees among the full list of variables
coefBound	bound on the coefficient size
pSparsity	sparsity of the polynomial in the term separation sense
includeNeg	whether to include negative coefficients

◆ regularGCD()

template<class Field, class RecursivePoly>

std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly> > > RegularChain< Field, RecursivePoly >::regularGCD	(	const RecursivePoly &	p,
		const RecursivePoly &	q,
		const Symbol &	v,
		const SubResultantChain< RecursivePoly, RecursivePoly > &	src,
		bool	lazardDecompose = `false`,
		int	heightBound = `0`
	)		const

Compute the gcd of two input polynomials p and q modulo the saturated ideal of the current object.

The result is a list of pairs (g_i,T_i) of polynomials g_i and regular chains T_i, where g_i is gcd(p,q) modulo the saturated ideal of T_i.

Parameters

p	a recursively viewed polynomial
q	a recursively viewed polynomial
v	the common main variable of p and q
src	the subresultant chain of p and q

◆ regularize()

template<class Field, class RecursivePoly>

std::vector<PolyChainPair<RecursivePoly,RegularChain<Field,RecursivePoly> > > RegularChain< Field, RecursivePoly >::regularize	(	const RecursivePoly &	p,
		bool	lazardDecompose = `false`,
		int	heightBound = `0`
	)		const

Compute a decomposition of the current object such that on each component the input polynomial is either zero or regular modulo the saturated ideal of that component.

If the polynomial is zero, (0, T_i) is returned; if the polynomial is regular, (p_i, T_i), is returned, where p_i is equivalent to p modulo the saturated ideal of T_i.

Parameters

p	a recursively viewed polynomial

◆ removeRedundantChains()

template<class Field, class RecursivePoly>

static void RegularChain< Field, RecursivePoly >::removeRedundantChains	(	const std::vector< RegularChain< Field, RecursivePoly >> &	lrc,
		std::vector< RegularChain< Field, RecursivePoly >> &	results
	)

static

Remove redundancy from the input list of regular chains.

Parameters

lrc	a list of regular chains

◆ select()

template<class Field, class RecursivePoly>

RecursivePoly RegularChain< Field, RecursivePoly >::select ( const Symbol & s ) const

inlinevirtual

Select the polynomial in the current object with main variable s, if it exists.

Parameters

s a symbol

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ setOptions()

template<class Field, class RecursivePoly>

void RegularChain< Field, RecursivePoly >::setOptions ( int opts )

Set the encoded options of the regular chain.

Parameters

opts	bitwise or of RegularChainOption values

◆ squareFreePart()

template<class Field, class RecursivePoly>

std::vector<RegularChain<Field,RecursivePoly> > RegularChain< Field, RecursivePoly >::squareFreePart	(	const RecursivePoly &	p,
		const Symbol &	v,
		bool	lazardDecompose = `false`,
		int	heightBound = `0`,
		int	options = `ASSUME_REGULAR`
	)		const

A routine that decomposes the regular chain formed from the current object and an input polynomial into a set of squarefree regular chains.

Parameters

p	a recursively viewed polynomial such that init(p) is regular modulo the saturated ideal of the current object
v	the main variable of p
options	a bitwise or of RegularChainOption values (default assume that T+p is a regular chain, where T is the current object)

◆ triangularize()

template<class Field, class RecursivePoly>

std::vector<RegularChain<Field,RecursivePoly> > RegularChain< Field, RecursivePoly >::triangularize	(	const std::vector< RecursivePoly > &	F,
		bool	lazardDecompose = `false`,
		int	type = `0`
	)

Compute a triangular decomposition of the list of input polynomials.

Parameters

F	a vector of recursively viewed polynomials
type	a flag to determine what strategy to use (type = 0 processes tasks as they are generated, type = 1 process by level of the tree of chains generted in the decomposition process)

◆ upper()

template<class Field, class RecursivePoly>

void RegularChain< Field, RecursivePoly >::upper	(	const Symbol &	s,
		BPASTriangularSet< Field, RecursivePoly > &	ts
	)		const

virtual

Returns the regular chain consisting of polynomials with main variable strictly greater than s.

Parameters

s	symbol of the main variable of specified element of the regular chain
ts	The returned regular chain

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

◆ variables()

template<class Field, class RecursivePoly>

std::vector<Symbol> RegularChain< Field, RecursivePoly >::variables ( ) const

inlinevirtual

Get the (potentially algebriac) variable names in decreasing order.

Parameters

Implements BPASTriangularSet< Field, RecursivePoly >.

Reimplemented in ZeroDimensionalRegularChain< Field, RecursivePoly >.

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

include/RegularChain/regularchain.hpp

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

template<class Field, class RecursivePoly> class RegularChain< Field, RecursivePoly >

Constructor & Destructor Documentation

◆ RegularChain() [1/13]

◆ RegularChain() [2/13]

◆ RegularChain() [3/13]

◆ RegularChain() [4/13]

◆ RegularChain() [5/13]

◆ RegularChain() [6/13]

◆ RegularChain() [7/13]

◆ RegularChain() [8/13]

◆ RegularChain() [9/13]

◆ RegularChain() [10/13]

◆ RegularChain() [11/13]

◆ RegularChain() [12/13]

◆ RegularChain() [13/13]

Member Function Documentation

◆ cleanSet()

◆ compareCertifiedNoSplit()

◆ compareHeuristicNoSplit()

◆ constructChains()

◆ intersect()

◆ isInRadicalSaturatedIdeal()

◆ isInSaturatedIdeal() [1/2]

◆ isInSaturatedIdeal() [2/2]

◆ isInSaturatedIdealMinimal()

◆ isIteratedResultantZeroModular()

◆ isRegular()

◆ isSquareFree()

◆ lower()

◆ lowerSlice()

◆ numberOfVariables()

◆ operator!=()

◆ operator+() [1/2]

◆ operator+() [2/2]

◆ operator+=() [1/2]

◆ operator+=() [2/2]

◆ operator=() [1/8]

◆ operator=() [2/8]

◆ operator=() [3/8]

◆ operator=() [4/8]

◆ operator=() [5/8]

◆ operator=() [6/8]

◆ operator=() [7/8]

◆ operator=() [8/8]

◆ operator==()

◆ options()

◆ randomRegularChain() [1/2]

◆ randomRegularChain() [2/2]

◆ regularGCD()

◆ regularize()

◆ removeRedundantChains()

◆ select()

◆ setOptions()

◆ squareFreePart()

◆ triangularize()

◆ upper()

◆ variables()

template<class Field, class RecursivePoly>
class RegularChain< Field, RecursivePoly >