Opened 6 years ago
Closed 5 years ago
#12489 closed defect (fixed)
Fix equality of combinatorial free module on non totally ordered basis
Reported by: | hivert | Owned by: | sage-combinat |
---|---|---|---|
Priority: | critical | Milestone: | sage-5.0 |
Component: | combinatorics | Keywords: | CombinatorialFreeModule, equality, Cernay2012 |
Cc: | sage-combinat | Merged in: | sage-5.0.beta5 |
Authors: | Nicolas M. Thiéry | Reviewers: | Florent Hivert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12490 | Stopgaps: |
Description (last modified by )
The following is obviously wrong:
sage: F = CombinatorialFreeModule(QQ, Subsets([1,2,3])) sage: x = F.an_element() sage: x+0 == x False sage: x+F.zero() == x False
The reason is
sage: (x+F.zero()).terms() # random [2*B[{1}], 3*B[{2}], B[{}]] sage: x.terms() # random [2*B[{1}], B[{}], 3*B[{2}]]
Fixing equality testing also revealed a bug in sage.combinat.sf.dual: the conversion back from the dual basis did not strip cancelled terms from the dictionary. This conversion now uses dict_linear_combination which fixes the bug, factors out code and should be faster.
See also the possible optimization in #12508
Attachments (1)
Change History (14)
comment:1 Changed 6 years ago by
- Dependencies set to #12490
- Keywords Cernay2012 added
comment:2 Changed 6 years ago by
- Status changed from new to needs_review
comment:3 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:5 follow-ups: ↓ 6 ↓ 9 Changed 6 years ago by
- Status changed from positive_review to needs_work
sage -t --long "devel/sage-main/sage/combinat/sf/dual.py" ********************************************************************** File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/devel/sage-main/sage/combinat/sf/dual.py", line 33: sage: TestSuite(f).run() # long time (11s on sage.math, 2011) Expected nothing Got: Failure in _test_one: Traceback (most recent call last): File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/categories/monoids.py", line 126, in _tes t_one tester.assert_(x * one == x) File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python2.7/unittest/case.py", line 420, in assertTrue raise self.failureException(msg) AssertionError: False is not true [...]
comment:6 in reply to: ↑ 5 Changed 6 years ago by
Replying to jdemeyer:
sage -t --long "devel/sage-main/sage/combinat/sf/dual.py" ********************************************************************** File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/devel/sage-main/sage/combinat/sf/dual.py", line 33: sage: TestSuite(f).run() # long time (11s on sage.math, 2011) Expected nothing Got: Failure in _test_one: Traceback (most recent call last): File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python/site-packages/sage/categories/monoids.py", line 126, in _tes t_one tester.assert_(x * one == x) File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.beta4/local/lib/python2.7/unittest/case.py", line 420, in assertTrue raise self.failureException(msg) AssertionError: False is not true [...]
Thanks for catching that. I am working on it. First thing, I am extracting the call to _test_associativity to only set # long on it, and not on the full testsuite (otherwise I would have caught the error myself). The other thing is that the new equality test highlighted a preexisting bug: x*f.one() contains zero coefficients in its dictionary.
comment:7 Changed 6 years ago by
- Status changed from needs_work to needs_review
Changed 6 years ago by
comment:8 Changed 6 years ago by
- Description modified (diff)
comment:9 in reply to: ↑ 5 Changed 6 years ago by
Replying to jdemeyer:
sage -t --long "devel/sage-main/sage/combinat/sf/dual.py" [...]
AssertionError?: False is not true
}}}
Sorry for not catching this ealier ! I didn't launch the -long
tests during my review.
comment:10 follow-up: ↓ 11 Changed 6 years ago by
Nicolas: using dict_linear_combination
is clearly the good solution here. I'm testing all these and will get back to positive review if the tests pass. Do you have auto tests on sageange working the way we had on massena ?
Florent
comment:11 in reply to: ↑ 10 Changed 6 years ago by
Replying to hivert:
Nicolas: using
dict_linear_combination
is clearly the good solution here. I'm testing all these and will get back to positive review if the tests pass. Do you have auto tests on sageange working the way we had on massena ?
Yes, that's where I ran the test mentionned above. I'll put sage-combinat-commits in CC next time.
comment:12 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
I put back to positive review while waiting for the result of the tests.
comment:13 Changed 5 years ago by
- Merged in set to sage-5.0.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
I uploaded the patch on behalf of Nicolas and put a positive review since I'm Ok with it (the test suite is currently running).
Nicolas: I just put the correct trac ticket number and added one more test compared to your patch. I don't think this needs a new review.