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
