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 ![]() | |
Slice (SliceStrategy &strategy, const Ideal &ideal, const Ideal &subtract, const Term &multiply) | |
Construct the slice ![]() | |
virtual | ~Slice () |
Accessors | |
size_t | getVarCount () const |
Returns the number of variables in the ambient ring. | |
const Ideal & | getIdeal () const |
Returns ![]() ![]() | |
Ideal & | getSubtract () |
Returns ![]() ![]() | |
const Ideal & | getSubtract () const |
Returns ![]() ![]() | |
Term & | getMultiply () |
Returns ![]() ![]() | |
const Term & | getMultiply () const |
Returns ![]() ![]() | |
const Term & | getLcm () const |
Returns the least common multiple of the generators of getIdeal(). | |
void | print (FILE *file) const |
Write a text representation of this object to file in a format appropriate for debugging. | |
![]() | |
virtual | ~Task () |
Mutators | |
Ideal | _ideal |
The ![]() ![]() | |
Ideal | _subtract |
The ![]() ![]() | |
Term | _multiply |
The ![]() ![]() | |
size_t | _varCount |
The number of variables in the ambient polynomial ring. | |
Term | _lcm |
The lcm of getIdeal() if _lcmUpdated is true, and otherwise the value is undefind. | |
bool | _lcmUpdated |
Indicates whether _lcm is correct. | |
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. | |
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. | |
virtual Slice & | operator= (const Slice &slice)=0 |
Performs a deep copy of slice into this object. | |
void | resetAndSetVarCount (size_t varCount) |
Resets this slice to ![]() | |
void | clearIdealAndSubtract () |
Clears getIdeal() and getSubtract() and does not change getMultiply(). | |
void | singleDegreeSortIdeal (size_t var) |
Calls Ideal::singleDegreeSort on getIdeal(). | |
virtual bool | innerSlice (const Term &pivot) |
Sets this object to the inner slice according to pivot. | |
virtual void | outerSlice (const Term &pivot) |
Sets this object to the outer slice according to pivot. | |
bool | normalize () |
Removes those generators of getIdeal() that are strictly divisible by some generator of getSubtract(). | |
bool | adjustMultiply () |
Ensure that for each var, var appears to the first power in some generator of getIdeal(). | |
virtual bool | simplify () |
Simplifies this object such that it may become simpler without changing the content. | |
virtual bool | simplifyStep ()=0 |
Like simplify(), except that only one simplification step is performed. | |
virtual void | run (TaskEngine &tasks) |
Does whatever work this task represents. | |
virtual void | dispose () |
Called when the task is no longer used but run has not and will not be called. | |
void | setToProjOf (const Slice &slice, const Projection &projection) |
Set this object to be the projection of slice according to projection. | |
void | swap (Slice &slice) |
Simultaneously set the value of this object to that of slice and vice versa. | |
bool | pruneSubtract () |
Removes those generators of subtract that do not strictly divide the lcm of getIdeal(), or that belong to getIdeal(). | |
bool | applyLowerBound () |
Calculates a lower bound on the content of the slice using getLowerBound() and calls innerSlice with that lower bound. | |
virtual bool | getLowerBound (Term &bound, size_t var) const =0 |
Calculates a lower bound that depends on var. | |
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
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 | ) |
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 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 |
|
inline |
Returns
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.
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
rename lower bound to divisor.
describe how the real functionality is slightly more sophisticated.
Implemented in HilbertSlice, and MsmSlice.
|
inline |
|
inline |
|
inline |
|
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 |
|
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 HilbertSlice, and MsmSlice.
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 |