#10950: The Hash function for matrices suffers from 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: |
------------------------------+---------------------------------------------
Description changed by nthiery:
Old description:
> 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
New description:
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#comment:1>
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.
