Feature #800
PPMonoidSparse: impl of sparse PPs
Description
Implement a PPMonoid which uses a sparse repr for the PPs.
This is useful when there are many indets.
Related issues
History
#1
Updated by John Abbott over 8 years ago
Updated by I had assumed that this issue already existed, but a quick search did not find it.
There is already a partial implementation (dating back to 2005/2007). Complete it!
#2
Updated by John Abbott over 8 years ago
- Status changed from New to In Progress
- Assignee set to John Abbott
- % Done changed from 0 to 50
There was a very incomplete impl in PPMonoidSparse.C, which was already recognized by Makefile.
Apparently the impl has long exponents; might a "big exp" version also be interesting? Anyway, I'll proceed with the long version; if we want a BigInt version later, it should be largely a copy-and-paste job :-)
Currently the impl uses internally a std::list of pairs (index, exp). The advantage of using a std::list over a std::vector is apparent only in myMulByIndetPower where a new factor may need to be inserted.
I now think that a std::vector based impl would probably be better (assuming that myMulByIndetPower is not called often when it is necessary to insert a new factor in the "middle" of the PP).
Another problem is how to handle well the various term orderings. Currently the code assumes lex which is clearly too limiting!
#3
Updated by John Abbott over 8 years ago
The currently missing functions are: myCmp, myWDeg and myCmpWDeg (& a partial version). Also myComputeDivMask.
How to implement these functions reasonably efficiently? Is efficiency even important?
Surely efficiency is important for myCmp, especially with the most common PP ordering (namely, StdDegRevLex). How to achieve this? One possible solution is to create a temporary vector into which the exponents will be placed, and then use a standard "dense" algorithm, but that seems to defeat the purpose of a sparse repr.
Might it be important to store the StdDeg along with the list of (index, exp) pairs? If it is not stored, then it must be computed (linear cost) for each comparison.
#4
Updated by John Abbott over 8 years ago
For Wdeg I am inclined to compute it "on the fly" every time it is needed. If someone reports poor execution speed, and profiling fingers WDeg as the culprit then I can consider storing the WDeg explicitly in the PP repr.
The question for the standard degree is probably different...
#5
Updated by Anna Maria Bigatti over 8 years ago
Updated by John Abbott wrote:
Might it be important to store the
StdDegalong with the list of (index, exp) pairs? If it is not stored, then it must be computed (linear cost) for each comparison.
well, as you always tell me: make the clean implementation first.... ;-)
#6
Updated by John Abbott over 8 years ago
- % Done changed from 50 to 60
I have a first (complete) version which seems to work OK -- just simple tests.
I even managed to create a sparse poly ring with 1000000 indets! :-)
#7
Updated by John Abbott over 8 years ago
Cleaned the PPMonoidSparse code; there were still a couple of incomplete fns.
#8
Updated by John Abbott over 8 years ago
Should the NewPolyRing fns automatically choose PPMonoidSparse if there are "lots of" indets? If so, how many are "lots of"? 20? 30? 40?
Comments? Suggestions?
#9
Updated by John Abbott about 8 years ago
- Priority changed from Normal to Urgent
#10
Updated by John Abbott about 8 years ago
- Related to Slug #842: PPMonoidSparse: comparisons are VERY SLOW added
#11
Updated by John Abbott almost 8 years ago
- Target version changed from CoCoALib-0.99540 Feb 2016 to CoCoALib-0.99560
As reported in issue #842 execution speed is sometimes very disappointing, so currently it may not be such a good idea to arrange for NewPolyRing to use a PPMonoidSparse yet. Nevertheless, the principle is good; I did look at the code hoping to make the change quickly, but it looked to be trickier than I'd expected :-(
#12
Updated by John Abbott over 6 years ago
- Target version changed from CoCoALib-0.99560 to CoCoALib-0.99600
#13
Updated by John Abbott almost 6 years ago
- Target version changed from CoCoALib-0.99600 to CoCoALib-0.99650 November 2019
#14
Updated by John Abbott over 4 years ago
- Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99800
#15
Updated by John Abbott about 2 years ago
- Status changed from In Progress to Resolved
- % Done changed from 60 to 80
The code is there, and there is a test: test-PPMonoidSparse1.C. However many lines are commented out in the test.
Documentation? Pah! D is for wimps! Well, I've added a few lines to PPMonoidSparse.C
I'm tempted to close this issue for 0.99720, and make a new one for improving the impl.
Ideally the repr should depend on the term order: e.g. DegRevLex favours having the IndexExp entries in reverse order!
Exercise for student?
#16
Updated by John Abbott about 2 years ago
- Related to Support #242: CoCoA-5 Projects for students (e.g. crediti F and tesi) added
#17
Updated by John Abbott about 2 years ago
- Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850
#18
Updated by John Abbott about 1 year ago
- Status changed from Resolved to Closed
- % Done changed from 80 to 100
- Estimated time set to 8.99 h
It make sense to close this issue, and let issue #842 deal with the disappointing execution speed.