|
Frobby 0.10.0
|
#include <Slice.h>


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



![\[ \con I S q = \con {I:p} {S:p} {qp} \cup \con I {S+p} q
\]](form_80.png)
where 
The ideal 







There are two base cases of the Slice Algorithm. A trivial base case slice is when 

A non-trivial base case is when 

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.
| Slice::Slice | ( | SliceStrategy & | strategy | ) |
Construct the slice 
| Slice::Slice | ( | SliceStrategy & | strategy, |
| const Ideal & | ideal, | ||
| const Ideal & | subtract, | ||
| const Term & | multiply ) |
Construct the slice 
| 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 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.
| 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 |
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.
|
inline |
Returns 

| 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
![\[ \frac{1}{x_i}\gcd(\min(I)\cap\ideal{x_i})
\]](form_90.png)
where 
rename lower bound to divisor.
describe how the real functionality is slightly more sophisticated.
|
inline |
Returns 

|
inline |
Returns 

|
inline |
Returns 

|
inline |
Returns 

|
inline |
Returns the number of variables in the ambient ring.
|
virtual |
Sets this object to the inner slice according to pivot. To be precise, the slice 


Returns true if any of the colon operations 

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 HilbertSlice, and MsmSlice.
|
virtual |
Sets this object to the outer slice according to pivot. To be precise, the slice 


Note that if pivot is a pure power, then pivot is not actually inserted into 
Reimplemented in MsmSlice.
| void Slice::print | ( | FILE * | file | ) | const |
Write a text representation of this object to file in a format appropriate for debugging.
|
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 | ) |
Resets this slice to 
|
virtual |
Does whatever work this task represents. The parameter can be used to schedule additional tasks.
Implements Task.
|
protected |
Set this object to be the projection of slice according to projection. I.e. each of getIdeal(), getSubtract() and getMultiply() are projected.
|
virtual |
Simplifies this object such that it may become simpler without changing the content. It is a precondition that the slice is already normalized.
|
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 HilbertSlice, and MsmSlice.
| void Slice::singleDegreeSortIdeal | ( | size_t | var | ) |
Calls Ideal::singleDegreeSort on getIdeal().
|
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.
|
protected |
The 

|
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 |
The 

|
protected |
The 

|
protected |
The number of variables in the ambient polynomial ring.