Opened 10 years ago
Last modified 3 years ago
#10950 closed defect
The Hash function for matrices suffers from many collisions with permutation matrices — at Version 1
Reported by: | nthiery | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-8.1 |
Component: | linear algebra | Keywords: | Weyl groups, permutation matrices, hash |
Cc: | sage-combinat | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The current hash function for generic dense matrices suffers from hard collisions with permutation matrices. For example: all permutation matrices of size 4 have hash 0!
sage: def mat(p): m = p.to_matrix(); m.set_immutable(); return m sage: [ hash(mat(p)) for p in Permutations(4) ] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
In general, we would hope to get n! below:
sage: len(set([ hash(mat(p)) for p in Permutations(1) ])) 1 sage: len(set([ hash(mat(p)) for p in Permutations(2) ])) 1 sage: len(set([ hash(mat(p)) for p in Permutations(3) ])) 5 sage: len(set([ hash(mat(p)) for p in Permutations(4) ])) 1 sage: len(set([ hash(mat(p)) for p in Permutations(5) ])) 16 sage: len(set([ hash(mat(p)) for p in Permutations(6) ])) 16 sage: len(set([ hash(mat(p)) for p in Permutations(7) ])) 32 sage: len(set([ hash(mat(p)) for p in Permutations(8) ])) 1
I stumbled on this when profiling some code using Weyl groups that heavily used caching (the hash of a weyl group element is the hash of the underlying matrix). I gained a speed factor of 10x by just tweaking the hash of matrices as in the attached patch. Now, I have no idea if in general that would be a good hash for matrices, so please some expert write an appropriate patch.
Cheers,
Nicolas
Change History (2)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Description modified (diff)
- Summary changed from The Hash function for matrices has many collisions with permutation matrices: to The Hash function for matrices suffers from many collisions with permutation matrices