Frobby
0.9.5

This class represents a slice, which is the central data structure of the Slice Algorithm. More...
#include <Slice.h>
Public Member Functions  
Slice (SliceStrategy &strategy)  
Construct the slice in a ring of zero variables. More...  
Slice (SliceStrategy &strategy, const Ideal &ideal, const Ideal &subtract, const Term &multiply)  
Construct the slice . 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 derivativespecific 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 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...  
This class represents a slice, which is the central data structure of the Slice Algorithm.
To be precise, a slice is mathematically a 3tuple where and are monomial ideals and 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
where 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 is regarded as the base data of the slice, and is known as simply the ideal of the slice. The ideal is regarded as specifying monomials that are not to be regarded as part of the content, i.e. is subtracted from the content, so is known as the subtract of the slice. The monomial 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 , and . 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 is not divisible by some variable, i.e. some variable does not appear in any element of . In this case the content is empty.
A nontrivial base case is when is squarefree and the base case is not trivial. This is equivalent to 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 nontrivial 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.
Slice::Slice  (  SliceStrategy &  strategy  ) 
Slice::Slice  (  SliceStrategy &  strategy, 
const Ideal &  ideal,  
const Ideal &  subtract,  
const Term &  multiply  
) 
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.

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.

pure virtual 
Returns true if this slice is a base case slice, and in that case produces output in a derivativespecific 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.
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.

virtual 

inline 
Returns for a slice .
There is no nonconst 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.
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.

protectedpure virtual 
Calculates a lower bound that depends on var.
To be precise, the lower bound that is calculated is
where 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).
rename lower bound to divisor.
describe how the real functionality is slightly more sophisticated.
Implemented in MsmSlice, and HilbertSlice.

inline 

inline 

inline 

virtual 
Sets this object to the inner slice according to pivot.
To be precise, the slice is replaced by where is the pivot, and the slice is then normalized (see normalize).
Returns true if any of the colon operations and were nontrivial in the sense that it changed the support of any minimal generator.
Reimplemented in MsmSlice.
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.
Performs a deep copy of slice into this object.
Implemented in MsmSlice, and HilbertSlice.

virtual 
Sets this object to the outer slice according to pivot.
To be precise, the slice is replaced by where 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 since doing so has no effect on the content after the normalization.
Reimplemented in MsmSlice.
void Slice::print  (  FILE *  file  )  const 

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.
void Slice::resetAndSetVarCount  (  size_t  varCount  ) 

virtual 

protected 
Set this object to be the projection of slice according to projection.
I.e. each of getIdeal(), getSubtract() and getMultiply() are projected.

virtual 

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.
Implemented in MsmSlice, and HilbertSlice.
void Slice::singleDegreeSortIdeal  (  size_t  var  ) 
Calls Ideal::singleDegreeSort on getIdeal().

protected 

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.

mutableprotected 

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.

protected 

protected 