Frobby 0.10.0
Loading...
Searching...
No Matches
Slice Class Referenceabstract

#include <Slice.h>

Inheritance diagram for Slice:
Collaboration diagram for Slice:

Public Member Functions

 Slice (SliceStrategy &strategy)
 Slice (SliceStrategy &strategy, const Ideal &ideal, const Ideal &subtract, const Term &multiply)
Accessors
size_t getVarCount () const
const Ideal & getIdeal () const
Ideal & getSubtract ()
const Ideal & getSubtract () const
Term & getMultiply ()
const Term & getMultiply () const
const Term & getLcm () const
void print (FILE *file) const

Mutators

Ideal _ideal
Ideal _subtract
Term _multiply
size_t _varCount
Term _lcm
bool _lcmUpdated
size_t _lowerBoundHint
SliceStrategy & _strategy
virtual bool baseCase (bool simplified)=0
virtual Slice & operator= (const Slice &slice)=0
void resetAndSetVarCount (size_t varCount)
void clearIdealAndSubtract ()
void singleDegreeSortIdeal (size_t var)
virtual bool innerSlice (const Term &pivot)
virtual void outerSlice (const Term &pivot)
bool normalize ()
bool adjustMultiply ()
virtual bool simplify ()
virtual bool simplifyStep ()=0
virtual void run (TaskEngine &tasks)
virtual void dispose ()
void setToProjOf (const Slice &slice, const Projection &projection)
void swap (Slice &slice)
bool pruneSubtract ()
bool applyLowerBound ()
virtual bool getLowerBound (Term &bound, size_t var) const =0

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.

Constructor & Destructor Documentation

◆ Slice() [1/2]

Slice::Slice ( SliceStrategy & strategy)

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

◆ 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})$.

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.

◆ 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.

◆ 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 HilbertSlice, and MsmSlice.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ getMultiply() [1/2]

Term & Slice::getMultiply ( )
inline

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

◆ getMultiply() [2/2]

const Term & Slice::getMultiply ( ) const
inline

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

◆ getSubtract() [1/2]

Ideal & Slice::getSubtract ( )
inline

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

◆ getSubtract() [2/2]

const Ideal & Slice::getSubtract ( ) const
inline

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

◆ getVarCount()

size_t Slice::getVarCount ( ) const
inline

Returns the number of variables in the ambient ring.

◆ 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.

◆ 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.

◆ operator=()

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

Performs a deep copy of slice into this object.

Implemented in HilbertSlice, and MsmSlice.

◆ 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.

◆ print()

void Slice::print ( FILE * file) const

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

◆ 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.

◆ resetAndSetVarCount()

void Slice::resetAndSetVarCount ( size_t varCount)

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

◆ run()

void Slice::run ( TaskEngine & engine)
virtual

Does whatever work this task represents. The parameter can be used to schedule additional tasks.

Implements Task.

◆ 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.

◆ 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.

◆ 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 HilbertSlice, and MsmSlice.

◆ singleDegreeSortIdeal()

void Slice::singleDegreeSortIdeal ( size_t var)

Calls Ideal::singleDegreeSort on getIdeal().

◆ 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.

Member Data Documentation

◆ _ideal

Ideal Slice::_ideal
protected

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

◆ _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.

◆ _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.

◆ _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.

◆ _multiply

Term Slice::_multiply
protected

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

◆ _subtract

Ideal Slice::_subtract
protected

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

◆ _varCount

size_t Slice::_varCount
protected

The number of variables in the ambient polynomial ring.


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