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 nthiery "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]
}}}
After applying this branch:
{{{
sage: def hashmat(p): m = p.to_matrix(); m.set_immutable(); return hash(m)
sage: len(set(hashmat(p) for p in Permutations(1)))
1
sage: len(set(hashmat(p) for p in Permutations(2)))
2
sage: len(set(hashmat(p) for p in Permutations(3)))
6
sage: len(set(hashmat(p) for p in Permutations(4)))
24
sage: len(set(hashmat(p) for p in Permutations(5)))
120
sage: len(set(hashmat(p) for p in Permutations(6)))
720
sage: len(set(hashmat(p) for p in Permutations(7)))
5040
sage: len(set(hashmat(p) for p in Permutations(8)))
40320
}}}
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 sage-8.1 linear algebra Weyl groups, permutation matrices, hash sage-combinat Jeroen Demeyer N/A u/jdemeyer/the_hash_function_for_matrices_suffers_from_many_collisions_with_permutation_matrices f67a8839d7dfb843a8ed8652a2734b644be579f1 #24090