This class represents a slice, which is the central data structure of the Slice Algorithm. More...

#include <Slice.h>

Inheritance diagram for Slice:

Public Member Functions
	Slice (SliceStrategy &strategy)
	Construct the slice $(\ideal 0, \ideal 0, 1)$ in a ring of zero variables. More...

	Slice (SliceStrategy &strategy, const Ideal &ideal, const Ideal &subtract, const Term &multiply)
	Construct the slice $(\codeVar{ideal}, \codeVar{subtract}, \codeVar{multiply})$ . More...

virtual	~Slice ()

Accessors
size_t	getVarCount () const
	Returns the number of variables in the ambient ring. More...

const Ideal &	getIdeal () const
	Returns for a slice . More...

Ideal &	getSubtract ()
	Returns for a slice . More...

const Ideal &	getSubtract () const
	Returns for a slice . More...

Term &	getMultiply ()
	Returns for a slice . More...

const Term &	getMultiply () const
	Returns for a slice . More...

const Term &	getLcm () const
	Returns the least common multiple of the generators of getIdeal(). More...

void	print (FILE *file) const
	Write a text representation of this object to file in a format appropriate for debugging. More...

Public Member Functions inherited from Task
virtual	~Task ()

Mutators
Ideal	_ideal
	The of a slice . More...

Ideal	_subtract
	The of a slice . More...

Term	_multiply
	The of a slice . More...

size_t	_varCount
	The number of variables in the ambient polynomial ring. More...

Term	_lcm
	The lcm of getIdeal() if _lcmUpdated is true, and otherwise the value is undefind. More...

bool	_lcmUpdated
	Indicates whether _lcm is correct. More...

size_t	_lowerBoundHint
	A hint that starting simplification through a lower bound at the variable indicated by _lowerBoundHint is likely to yield a simplification, or at least more likely than a random other variable. More...

SliceStrategy &	_strategy

virtual bool	baseCase (bool simplified)=0
	Returns true if this slice is a base case slice, and in that case produces output in a derivative-specific way. More...

virtual Slice &	operator= (const Slice &slice)=0
	Performs a deep copy of slice into this object. More...

void	resetAndSetVarCount (size_t varCount)
	Resets this slice to $(\ideal 0, \ideal 0, 1)$ in an ambient polynomial ring of varCount variables. More...

void	clearIdealAndSubtract ()
	Clears getIdeal() and getSubtract() and does not change getMultiply(). More...

void	singleDegreeSortIdeal (size_t var)
	Calls Ideal::singleDegreeSort on getIdeal(). More...

virtual bool	innerSlice (const Term &pivot)
	Sets this object to the inner slice according to pivot. More...

virtual void	outerSlice (const Term &pivot)
	Sets this object to the outer slice according to pivot. More...

bool	normalize ()
	Removes those generators of getIdeal() that are strictly divisible by some generator of getSubtract(). More...

bool	adjustMultiply ()
	Ensure that for each var, var appears to the first power in some generator of getIdeal(). More...

virtual bool	simplify ()
	Simplifies this object such that it may become simpler without changing the content. More...

virtual bool	simplifyStep ()=0
	Like simplify(), except that only one simplification step is performed. More...

virtual void	run (TaskEngine &tasks)
	Does whatever work this task represents. More...

virtual void	dispose ()
	Called when the task is no longer used but run has not and will not be called. More...

void	setToProjOf (const Slice &slice, const Projection &projection)
	Set this object to be the projection of slice according to projection. More...

void	swap (Slice &slice)
	Simultaneously set the value of this object to that of slice and vice versa. More...

bool	pruneSubtract ()
	Removes those generators of subtract that do not strictly divide the lcm of getIdeal(), or that belong to getIdeal(). More...

bool	applyLowerBound ()
	Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with that lower bound. More...

virtual bool	getLowerBound (Term &bound, size_t var) const =0
	Calculates a lower bound that depends on var. More...

Detailed Description

This class represents a slice, which is the central data structure of the Slice Algorithm.

To be precise, a slice is mathematically a 3-tuple $(I,S,q)$ where $I$ and $S$ are monomial ideals and $q$ is a monomial. Each slice then represents some part of the output, which is known as its content. Usually the content is a set, and the content obeys the pivot split equation, which is

$\con I S q = \con {I:p} {S:p} {qp} \cup \con I {S+p} q$

where $p$ is a monomial called the pivot, and the union is disjoint. There are three slices in this equation, which are known in order from left to right as the current slice, the inner slice and the outer slice.

The ideal $I$ is regarded as the base data of the slice, and is known as simply the ideal of the slice. The ideal $S$ is regarded as specifying monomials that are not to be regarded as part of the content, i.e. $S$ is subtracted from the content, so $S$ is known as the subtract of the slice. The monomial $q$ is multiplied onto the content, so it is known as the multiply of the slice. These parts of the slice do not actually have names, since in mathematics they are conveniently referred to as simply $I$ , $S$ and $q$ . We are introducing names for these symbols to have something to call them in the code.

There are two base cases of the Slice Algorithm. A trivial base case slice is when $\lcm(min(I))$ is not divisible by some variable, i.e. some variable does not appear in any element of $\min(I)$ . In this case the content is empty.

A non-trivial base case is when $I$ is square-free and the base case is not trivial. This is equivalent to $\lcm(min(I))$ being equal to the product of all variables in the ambient polynomial ring.

The Slice Algorithm has a notion of simplification, which is to replace a slice with a different slice that is simpler and has the same content.

This class implements the notions of the Slice Algorithm that are common among different versions of the Slice Algorithm, while leaving derived classes to introduce code that is specific to a particular version. A derivative of Slice thus cooperates with a derivative of SliceStrategy to implement a specific version of the Slice Algorithm.

As the kind of output generated by a non-trivial base case slice depends on what is being computed, the general Slice interface does not provide a way to obtain the output. The suggested mechanism is for each slice derivative to store a Consumer and to provide the output to that consumer.

Definition at line 77 of file Slice.h.

Constructor & Destructor Documentation

◆ Slice() [1/2]

Slice::Slice ( SliceStrategy & strategy )

Construct the slice $(\ideal 0, \ideal 0, 1)$ in a ring of zero variables.

Definition at line 26 of file Slice.cpp.

◆ Slice() [2/2]

Slice::Slice	(	SliceStrategy &	strategy,
		const Ideal &	ideal,
		const Ideal &	subtract,
		const Term &	multiply
	)

Construct the slice $(\codeVar{ideal}, \codeVar{subtract}, \codeVar{multiply})$ .

Definition at line 33 of file Slice.cpp.

◆ ~Slice()

Slice::~Slice ( )

virtual

Definition at line 47 of file Slice.cpp.

Member Function Documentation

◆ adjustMultiply()

bool Slice::adjustMultiply ( )

Ensure that for each var, var appears to the first power in some generator of getIdeal().

Note that this does not change the content of the slice. Returns true if the slice changed.

Definition at line 162 of file Slice.cpp.

◆ applyLowerBound()

bool Slice::applyLowerBound ( )

protected

Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with that lower bound.

Note that this does not change the content of the slice. This is repeated until a fixed point is reached. Returns false if no minimal generator of getIdeal() or getSubtract() has had their support changed or if a trivial base case is detected.

Todo:: Rename lower bound to divisor.

Definition at line 289 of file Slice.cpp.

◆ baseCase()

virtual bool Slice::baseCase ( bool simplified )

pure virtual

Returns true if this slice is a base case slice, and in that case produces output in a derivative-specific way.

If simplified is true, then the slice must be fully simplified when calling baseCase(), while otherwise there is no such requirement.

Implemented in MsmSlice, and HilbertSlice.

◆ clearIdealAndSubtract()

void Slice::clearIdealAndSubtract ( )

Clears getIdeal() and getSubtract() and does not change getMultiply().

This is useful to induce this slice to be clearly a trivial base case slice, and to clear memory in preparation for reusing this slice later without having to construct a new Slice. getMultiply() is left unchanged since changing it is unnecessary for these purposes.

Definition at line 99 of file Slice.cpp.

◆ dispose()

void Slice::dispose ( )

virtual

Called when the task is no longer used but run has not and will not be called.

This can happen from a destructor being called due to an exception, so dispose must not throw an exception under any circumstances.

Implements Task.

Definition at line 325 of file Slice.cpp.

◆ getIdeal()

const Ideal& Slice::getIdeal ( ) const

inline

Returns $I$ for a slice $(I,S,q)$ .

There is no non-const getIdeal() because Slice caches properties of the ideal, and it is not possible to efficiently track changes performed directly on the ideal. To compensate for this, Slice provides a subset of the mutable interface of Ideal which allows to manipulate the ideal.

Definition at line 104 of file Slice.h.

◆ getLcm()

const Term & Slice::getLcm ( ) const

Returns the least common multiple of the generators of getIdeal().

The lcm is stored and is only recomputed once after each time the ideal changes. The lcm is always needed after each change, e.g. to detect if the slice is a base case slice, so calling this method should be regarded as an inexpensive operation.

Definition at line 52 of file Slice.cpp.

◆ getLowerBound()

virtual bool Slice::getLowerBound	(	Term &	bound,
		size_t	var
	)		const

protectedpure virtual

Calculates a lower bound that depends on var.

To be precise, the lower bound that is calculated is

$\frac{1}{x_i}\gcd(\min(I)\cap\ideal{x_i})$

where $i$ is var. Note that the real functionality is slightly more sophisticated. Returns false and does not set bound if a base case is detected (a base case is not guaranteed to be detected).

Todo:

rename lower bound to divisor.

describe how the real functionality is slightly more sophisticated.

Implemented in MsmSlice, and HilbertSlice.

◆ getMultiply() [1/2]

Term& Slice::getMultiply ( )

inline

Returns $q$ for a slice $(I,S,q)$ .

Definition at line 113 of file Slice.h.

◆ getMultiply() [2/2]

const Term& Slice::getMultiply ( ) const

inline

Returns $q$ for a slice $(I,S,q)$ .

Definition at line 116 of file Slice.h.

◆ getSubtract() [1/2]

Ideal& Slice::getSubtract ( )

inline

Returns $S$ for a slice $(I,S,q)$ .

Definition at line 107 of file Slice.h.

◆ getSubtract() [2/2]

const Ideal& Slice::getSubtract ( ) const

inline

Returns $S$ for a slice $(I,S,q)$ .

Definition at line 110 of file Slice.h.

◆ getVarCount()

size_t Slice::getVarCount ( ) const

inline

Returns the number of variables in the ambient ring.

Definition at line 96 of file Slice.h.

◆ innerSlice()

bool Slice::innerSlice ( const Term & pivot )

virtual

Sets this object to the inner slice according to pivot.

To be precise, the slice $(I,S,q)$ is replaced by $(I:p,S:p,qp)$ where $p$ is the pivot, and the slice is then normalized (see normalize).

Returns true if any of the colon operations $I:p$ and $S:p$ were non-trivial in the sense that it changed the support of any minimal generator.

Reimplemented in MsmSlice.

Definition at line 110 of file Slice.cpp.

◆ normalize()

bool Slice::normalize ( )

Removes those generators of getIdeal() that are strictly divisible by some generator of getSubtract().

Note that this does not change the content of the slice. Returns true if any generators were removed. See ::strictlyDivides for the definition of strict divisibility.

Definition at line 189 of file Slice.cpp.

◆ operator=()

Slice & Slice::operator= ( const Slice & slice )

pure virtual

Performs a deep copy of slice into this object.

Implemented in MsmSlice, and HilbertSlice.

Definition at line 77 of file Slice.cpp.

◆ outerSlice()

void Slice::outerSlice ( const Term & pivot )

virtual

Sets this object to the outer slice according to pivot.

To be precise, the slice $(I,S,q)$ is replaced by $(I,S+\ideal p,q)$ where $p$ is the pivot, and the slice is then normalized (see normalize).

Note that if pivot is a pure power, then pivot is not actually inserted into $S$ since doing so has no effect on the content after the normalization.

Reimplemented in MsmSlice.

Definition at line 132 of file Slice.cpp.

◆ print()

void Slice::print ( FILE * file ) const

Write a text representation of this object to file in a format appropriate for debugging.

Definition at line 68 of file Slice.cpp.

◆ pruneSubtract()

bool Slice::pruneSubtract ( )

protected

Removes those generators of subtract that do not strictly divide the lcm of getIdeal(), or that belong to getIdeal().

Note that removing these generators does not change the content. Returns true if any generators were removed.

Definition at line 281 of file Slice.cpp.

◆ resetAndSetVarCount()

void Slice::resetAndSetVarCount ( size_t varCount )

Resets this slice to $(\ideal 0, \ideal 0, 1)$ in an ambient polynomial ring of varCount variables.

Definition at line 89 of file Slice.cpp.

◆ run()

void Slice::run ( TaskEngine & engine )

virtual

Does whatever work this task represents.

The parameter can be used to schedule additional tasks.

Implements Task.

Definition at line 321 of file Slice.cpp.

◆ setToProjOf()

void Slice::setToProjOf	(	const Slice &	slice,
		const Projection &	projection
	)

protected

Set this object to be the projection of slice according to projection.

I.e. each of getIdeal(), getSubtract() and getMultiply() are projected.

Definition at line 217 of file Slice.cpp.

◆ simplify()

bool Slice::simplify ( )

virtual

Simplifies this object such that it may become simpler without changing the content.

It is a precondition that the slice is already normalized.

Definition at line 204 of file Slice.cpp.

◆ simplifyStep()

virtual bool Slice::simplifyStep ( )

pure virtual

Like simplify(), except that only one simplification step is performed.

If the return value is true, then the Slice may not be fully simplified yet. Iterating simplifyStep() has the same result as calling simplify(), though the performance characteristics can be worse.

Todo:: Is this method actually used, and does it return true iff this object changed?

Implemented in MsmSlice, and HilbertSlice.

◆ singleDegreeSortIdeal()

void Slice::singleDegreeSortIdeal ( size_t var )

Calls Ideal::singleDegreeSort on getIdeal().

Definition at line 106 of file Slice.cpp.

◆ swap()

void Slice::swap ( Slice & slice )

protected

Simultaneously set the value of this object to that of slice and vice versa.

This is an inexpensive operation because no copy is necessary.

Definition at line 252 of file Slice.cpp.

Member Data Documentation

◆ _ideal

Ideal Slice::_ideal

protected

The $I$ of a slice $(I,S,q)$ .

Definition at line 266 of file Slice.h.

◆ _lcm

Term Slice::_lcm

mutableprotected

The lcm of getIdeal() if _lcmUpdated is true, and otherwise the value is undefind.

_lcm will always have the correct number of variables, even when _lcmUpdated is false.

This member variable is mutable since it has to be updated by getLcm in case _lcmUpdated is false, but getLcm should be const.

Definition at line 285 of file Slice.h.

◆ _lcmUpdated

bool Slice::_lcmUpdated

mutableprotected

Indicates whether _lcm is correct.

This member variable is mutable since it has to be updated by getLcm in case _lcmUpdated is false, but getLcm should be const.

Definition at line 293 of file Slice.h.

◆ _lowerBoundHint

size_t Slice::_lowerBoundHint

protected

A hint that starting simplification through a lower bound at the variable indicated by _lowerBoundHint is likely to yield a simplification, or at least more likely than a random other variable.

The point of this is to detect variables that can be simplified sooner in order to speed up simplification.

Definition at line 301 of file Slice.h.

◆ _multiply

Term Slice::_multiply

protected

The $q$ of a slice $(I,S,q)$ .

Definition at line 272 of file Slice.h.

◆ _strategy

SliceStrategy& Slice::_strategy

protected

Definition at line 303 of file Slice.h.

◆ _subtract

Ideal Slice::_subtract

protected

The $S$ of a slice $(I,S,q)$ .

Definition at line 269 of file Slice.h.

◆ _varCount

size_t Slice::_varCount

protected

The number of variables in the ambient polynomial ring.

Definition at line 275 of file Slice.h.

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

src/Slice.h
src/Slice.cpp

Public Member Functions

Mutators

Detailed Description

Constructor & Destructor Documentation

◆ Slice() [1/2]

◆ Slice() [2/2]

◆ ~Slice()

Member Function Documentation

◆ adjustMultiply()

◆ applyLowerBound()

◆ baseCase()

◆ clearIdealAndSubtract()

◆ dispose()

◆ getIdeal()

◆ getLcm()

◆ getLowerBound()

◆ getMultiply() [1/2]

◆ getMultiply() [2/2]

◆ getSubtract() [1/2]

◆ getSubtract() [2/2]

◆ getVarCount()

◆ innerSlice()

◆ normalize()

◆ operator=()

◆ outerSlice()

◆ print()

◆ pruneSubtract()

◆ resetAndSetVarCount()

◆ run()

◆ setToProjOf()

◆ simplify()

◆ simplifyStep()

◆ singleDegreeSortIdeal()

◆ swap()

Member Data Documentation

◆ _ideal

◆ _lcm

◆ _lcmUpdated

◆ _lowerBoundHint

◆ _multiply

◆ _strategy

◆ _subtract

◆ _varCount