Feature #802
DivMask: extend interface?
Description
The new PPMonoidSparse
impl needs to supply a myComputeDivMask
mem fn.
The current interface is well suited to dense PP reprs, but not well suited to a sparse repr.
Perhaps extend the interface to allow a sparse repr?
Discuss; decide; implement (if appropriate)
Related issues
History
#1 Updated by John Abbott over 8 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
Currently the only way to make a (non-trivial) DivMask
is to use the function myAssignFromExpv
which clearly suits a dense representation.
The sparse repr naturally presents a PP as a succession of (index,exp) pairs with the guarantee that the indexes are distinct (perhaps even in increasing order). As far as I can see all the current divmask rules would happily allow a divmask to be built up one (index,exp) pair at a time.
An alternative would simply be to create an exponent vector from the sparse repr and the use that to build the DivMask
, but that could be expensive (e.g. if there are many thousands of indets but only very few actually appear).
#2 Updated by John Abbott over 8 years ago
DivMask
to accommodate the sparse repr, what should the extended interface expect:
- (A) a
std::list
orstd::vector
of (index,exp) pairs - (B) a single (index,exp) pair (and allow multiple updates)
- (C) something else?
A disadvantage of (A) is that it would expose the internal structure used inside sparse PPs; or it could accept both std::list
and std::vector
?
A disadvantage of (B) (with multiple updates) is that there is no easy/cheap way to check whether there are (index,exp) pairs sharing the same index -- maybe that is not such a serious problem.
A disadvantage of (C) is that I have no idea what it might be :-/
ADDENDUM Option (B) seems to be the most "essential"; I'm unsure how serious is the inability to check whether there are repeated updates with the same index. A careless user may end up producing a junk result with no error/warning that something suspect is happening. Right now I do not see a genuine situation where it would be useful to be able to re-update with the same indet index (but the overhead for checking would be too great).
#3 Updated by Anna Maria Bigatti over 8 years ago
John Abbott wrote:
If we do extend the interface ofDivMask
to accommodate the sparse repr, what should the extended interface expect:
- (A) a
std::list
orstd::vector
of (index,exp) pairs- (B) a single (index,exp) pair (and allow multiple updates)
- (C) something else?
I liked B to start with, but then I thought of the problem that we might not be able to update a DivMask: if I add (i, 4) and (i, 5) does this mean that we have x[i]^(4+5)? then DivMaskHashing might have problems updating the DivMask
I think we should go for A with list and/or vector (requiring there are repeated indices)
#4 Updated by John Abbott over 8 years ago
I think updating would mean replacing the div-mask with that for the LCM of the old value and the new indet-power. Thus:
dm = Initially 0; // corr to PP = 1 dm.update(x,2); // now corr to x^2 = LCM(1, x^2) dm.update(x,3); // now corr to x^3 = LCM(x^2, x^3)
I think bitwise-or of two div-masks means getting the div-mask for the LCM of their PPs
[am I right?]
#5 Updated by Anna Maria Bigatti over 8 years ago
John Abbott wrote:
I think updating would mean replacing the div-mask with that for the LCM of the old value and the new indet-power. Thus:
Ok, with that definition of "updating" I think it might work (of course keeping in mind that a DM does not know which PP it's coming from)
I recall here that our definition of DM is: if PP1 | PP2 then DM | DM (bitwise)
#6 Updated by John Abbott over 8 years ago
I think we should implement (B) with the "LCM" meaning from comment 4.
I can do this after checking in the current (working!) version of PPMonoidSparse
#7 Updated by John Abbott over 8 years ago
Maybe I can do this next week?
#8 Updated by John Abbott over 8 years ago
- Assignee set to John Abbott
- Priority changed from Normal to Urgent
- Target version changed from CoCoALib-0.99540 Feb 2016 to CoCoALib-0.99550 spring 2017
- % Done changed from 10 to 50
#9 Updated by John Abbott almost 8 years ago
- Target version changed from CoCoALib-0.99550 spring 2017 to CoCoALib-0.99560
#10 Updated by John Abbott over 6 years ago
- Target version changed from CoCoALib-0.99560 to CoCoALib-0.99600
#11 Updated by Anna Maria Bigatti almost 6 years ago
- Target version changed from CoCoALib-0.99600 to CoCoALib-0.99650 November 2019
#12 Updated by John Abbott almost 5 years ago
- Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99800
#13 Updated by John Abbott over 4 years ago
- Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850
#14 Updated by John Abbott 4 months ago
- Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880