Represent an ideal. More...

#include <ideal.h>

Public Member Functions
	Ideal (std::vector< Polynomial< Element >> &polynomialArray, int nbVariable, int capacity=100000, int degree=0)
	Constructor. More...

	~Ideal ()
	Destructor.

void	printInfo () const
	Print _taggedPolynomialArray.

void	printReducedGroebnerBasis (bool printBasis=false) const
	Print the reduced Groebner basis.

std::vector< std::string >	getReducedGroebnerBasis () const
	Get the reduced Groebner basis as a vector of string.

void	printReducedGroebnerBasis (string const filename, int64_t modulo) const
	Print the reduced Groebner basis in a file.

void	printMonomialAvl ()
	Print _matMons.

void	printTaggedPolynomialAvl () const
	Print _matPols.

void	printMatrix (Matrix< Element > &mat, int tabMon, int sigma, string const &filename)
	Print mat.

int	simplify (Monomial const &u, int numList)
	Simplify the product u*(_taggedPolynomialArray[numList].poly) by another polynomial with the same leading term but with less terms in its tail. More...

void	update (int index, bool purge, Stat &stat)
	Update the set of critical pair and the current basis. More...

void	appendMatrixF4 (CriticalPair< Element > &p, int &h, int &nbPiv)
	Update _matPols and _matMons with the critical pair p. More...

double	transform (Matrix< Element > &mat, int tabMon, int nbPiv, int tau, int sigma, int startTail, int *endCol)
	Transform _matPols and _matMons into an almost tringular matrix. More...

Polynomial< Element >	buildPolynomial (Element row, int tabMon, int width, int start, int *tau)
	Build a polynomial from a row of the F4 matrix. More...

void	buildPolynomial (Polynomial< Element > &res, Element row, int tabMon, int width, int start, int *tau)
	Build a polynomial from a row of the F4 matrix. More...

void	preprocessing (int &width, int &height, int &nbPiv)
	Add polynomials to _matPols in order to reduced queue of current polynomials. More...

bool	postprocessing (Matrix< Element > &matrix, int tabMon, int sigma, int *tau, int height, int width, int heightReal, int nbPiv, Stat &stat)
	Rebuild _matPols from mat, update the basis and the set of critical pairs. More...

int	f4 ()
	Compute a groebner basis of this using the F4 algorithm. More...

Private Attributes
std::vector< Polynomial < Element > >	_polynomialArray

int	_nbVariable

int	_numPol

int	_numTot

int	_numGen

std::vector< int >	_total

std::vector< int >	_basis

std::vector< TaggedPolynomial < Element > >	_taggedPolynomialArray

MonomialArray	_monomialArray

AvlCriticalPair< Element >	_criticalPairSet

vector< CriticalPair< Element > * >	_cpSet0

vector< CriticalPair< Element > * >	_cpSet1

vector< CriticalPair< Element > * >	_cpSet2

vector< CriticalPair< Element > >	_cpArray

AvlMonomial	_matMons

AvlPolynomial	_matPols

Detailed Description

template<typename Element>
class F4::Ideal< Element >

Represent an ideal.

Examples:: tutorial-big-modulo-method3.cpp, tutorial-gf2-extension-method3.cpp, tutorial-gf2-method3.cpp, and tutorial-method3.cpp.

Definition at line 67 of file ideal.h.

Constructor & Destructor Documentation

template<typename Element>

F4::Ideal< Element >::Ideal	(	std::vector< Polynomial< Element >> &	polynomialArray,
		int	nbVariable,
		int	capacity = `100000`,
		int	degree = `0`
	)

Constructor.

Parameters

polynomialArray	Array of polynomials.
nbVariable	Number of variable of the polynomial ring.
capacity	Initial size of _monomialArray.
degree	Initialise the monomial array up to monomial of degree "degree".

Member Function Documentation

template<typename Element>

void F4::Ideal< Element >::appendMatrixF4	(	CriticalPair< Element > &	p,
		int &	h,
		int &	nbPiv
	)

Update _matPols and _matMons with the critical pair p.

Parameters

p	Critical pair.
h	Height of the F4 matrix.
nbPiv	Number of pivots in the the F4 matrix.

template<typename Element>

Polynomial<Element> F4::Ideal< Element >::buildPolynomial	(	Element *	row,
		int *	tabMon,
		int	width,
		int	start,
		int *	tau
	)

Build a polynomial from a row of the F4 matrix.

Parameters

tabMon	Array of monomials involved in _matPols.
width	End of the row.
start	Beginning of the row.
tau	tau[i]=column of the monomial tabMon[i].

Returns: Build polynomial.

template<typename Element>

void F4::Ideal< Element >::buildPolynomial	(	Polynomial< Element > &	res,
		Element *	row,
		int *	tabMon,
		int	width,
		int	start,
		int *	tau
	)

Build a polynomial from a row of the F4 matrix.

Parameters

res	Resulting polynomial.
tabMon	Array of monomials involved in _matPols.
width	End of the row.
start	Beginning of the row.
tau	tau[i]=column of the monomial tabMon[i].

template<typename Element>

int F4::Ideal< Element >::f4 ( )

Compute a groebner basis of this using the F4 algorithm.

Returns: Number of generators of the groebner basis.

template<typename Element>

bool F4::Ideal< Element >::postprocessing	(	Matrix< Element > &	matrix,
		int *	tabMon,
		int *	sigma,
		int *	tau,
		int	height,
		int	width,
		int	heightReal,
		int	nbPiv,
		Stat &	stat
	)

Rebuild _matPols from mat, update the basis and the set of critical pairs.

Parameters

matrix	Matrix.
tabMon	Array of monomials involved in _matPols.
sigma	sigma[i]=index in tabMon of the column i monomial.
tau	tau[i]=column of the monomial tabMon[i].
height	Height of the matrix before echelonize.
width	Width of the matrix before echelonize.
heightReal	Height of the matrix after echelonize.
nbPiv	Number of pivots in the the F4 matrix.

Returns: false if the computation end with a trivial groebner basis (1).; true otherwise.

template<typename Element>

void F4::Ideal< Element >::preprocessing	(	int &	width,
		int &	height,
		int &	nbPiv
	)

Add polynomials to _matPols in order to reduced queue of current polynomials.

Parameters

width	Width of the F4 matrix (number of monomials).
height	Height of the F4 matrix (number of polynomials).
nbPiv	Number of pivots in the the F4 matrix.

template<typename Element>

int F4::Ideal< Element >::simplify	(	Monomial const &	u,
		int	numList
	)

Simplify the product u*(_taggedPolynomialArray[numList].poly) by another polynomial with the same leading term but with less terms in its tail.

Parameters

u	Monomial.
numList	Index of a tagged polynomial in _taggedPolynomialArray.

Returns: Index of the simplified polynomial in the array Mon_Tab.

template<typename Element>

double F4::Ideal< Element >::transform	(	Matrix< Element > &	mat,
		int *	tabMon,
		int	nbPiv,
		int *	tau,
		int *	sigma,
		int *	startTail,
		int *	endCol
	)

Transform _matPols and _matMons into an almost tringular matrix.

Parameters

mat	Matrix to fill.
tabMon	Array of monomials involved in _matPols.
nbPiv	Number of pivots in the the F4 matrix.
tau	tau[i]=column of the monomial tabMon[i].
sigma	sigma[i]=index in tabMon of the column i monomial.
startTail	startTail[i]=column of the first possibly non zero coefficient (in line i) after nbPiv if i < nbPiv. Otherwise startTail[i]=0.
endCol	endCol[i] = end of column i if i < nbPiv. Otherwise endCol[i]=end of column i without taking into account the lines under nbPiv.

Returns: Percentage of non zero coefficients in mat.

template<typename Element>

void F4::Ideal< Element >::update	(	int	index,
		bool	purge,
		Stat &	stat
	)

Update the set of critical pair and the current basis.

Parameters

index Index of a tagged polynomial in _taggedPolynomialArray.

Member Data Documentation

template<typename Element>

std::vector<int> F4::Ideal< Element >::_basis

private

Array of tagged polynomial index _total[_basis[i]] belongs to the basis

Definition at line 227 of file ideal.h.

template<typename Element>

vector<CriticalPair<Element> > F4::Ideal< Element >::_cpArray

private

Dynamic array of critical pairs used in _cpSet0, _cpSet1 and _cpSet2.

Definition at line 234 of file ideal.h.

template<typename Element>

vector<CriticalPair<Element> *> F4::Ideal< Element >::_cpSet0

private

Array of pointers on critical pairs for update

Definition at line 231 of file ideal.h.

template<typename Element>

vector<CriticalPair<Element> *> F4::Ideal< Element >::_cpSet1

private

Array of pointers on critical pairs for update

Definition at line 232 of file ideal.h.

template<typename Element>

vector<CriticalPair<Element> *> F4::Ideal< Element >::_cpSet2

private

Array of pointers on critical pairs for update

Definition at line 233 of file ideal.h.

template<typename Element>

AvlCriticalPair<Element> F4::Ideal< Element >::_criticalPairSet

private

Set of critical pairs

Definition at line 230 of file ideal.h.

template<typename Element>

AvlMonomial F4::Ideal< Element >::_matMons

private

Monomials used in _matPols, AVL of pair (numMon, lt) decreasing order

Definition at line 235 of file ideal.h.

template<typename Element>

AvlPolynomial F4::Ideal< Element >::_matPols

private

F4 Matrix = AVL of triple (tagged polynomial index, numLM, nbTerms), decreasing order

Definition at line 236 of file ideal.h.

template<typename Element>

MonomialArray F4::Ideal< Element >::_monomialArray

private

Array of monomials, endow with a tabulated product 2D array

Definition at line 229 of file ideal.h.

template<typename Element>

int F4::Ideal< Element >::_nbVariable

private

Number of variables of the polynomial ring.

Definition at line 222 of file ideal.h.

template<typename Element>

int F4::Ideal< Element >::_numGen

private

Size of _basis

Definition at line 225 of file ideal.h.

template<typename Element>

int F4::Ideal< Element >::_numPol

private

Size of _taggedPolynomialArray

Definition at line 223 of file ideal.h.

template<typename Element>

int F4::Ideal< Element >::_numTot

private

Size of _total

Definition at line 224 of file ideal.h.

template<typename Element>

std::vector<Polynomial<Element> > F4::Ideal< Element >::_polynomialArray

private

Array of polynomials

Definition at line 221 of file ideal.h.

template<typename Element>

std::vector<TaggedPolynomial<Element> > F4::Ideal< Element >::_taggedPolynomialArray

private

Array of tagged polynomials

Definition at line 228 of file ideal.h.

template<typename Element>

std::vector<int> F4::Ideal< Element >::_total

private

Array of tagged polynomial index, _total[i] is a stored multiple of a basis polynomial

Definition at line 226 of file ideal.h.

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

/home/titouan/Bureau/openf4-1.0.1/openf4/include/ideal.h

Public Member Functions

Private Attributes

Detailed Description

template<typename Element> class F4::Ideal< Element >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Element>
class F4::Ideal< Element >