I don't see an attached patch, but a criteria is that it's easy to
compute for both dense and sparse matrices and for is a function of
the hash of its elements to satisfy equal matrices over different
parents having the same hash.
On Wed, Mar 16, 2011 at 11:09 AM, Nicolas M. Thiery
<nicolas.thi...@u-psud.fr> wrote:
> 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
> --
> Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
> http://Nicolas.Thiery.name/
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
