#10950: The Hash function for matrices has many collisions with permutation
matrices:
------------------------------+---------------------------------------------
Reporter: nthiery | Owner: jason, was
Type: defect | Status: new
Priority: major | Milestone:
Component: linear algebra | Keywords: Weyl groups
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10950>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
