id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
10950 The Hash function for matrices suffers from many collisions with permutation matrices nthiery jason was "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
" defect new major linear algebra Weyl groups sage-combinat N/A