Opened 10 years ago

Last modified 3 years ago

#10950 closed defect

The Hash function for matrices suffers from many collisions with permutation matrices — at Version 1

Reported by: nthiery Owned by: jason, was
Priority: major Milestone: sage-8.1
Component: linear algebra Keywords: Weyl groups, permutation matrices, hash
Cc: sage-combinat Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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]

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

Change History (2)

Changed 10 years ago by nthiery

comment:1 Changed 10 years ago by nthiery

  • Description modified (diff)
  • Summary changed from The Hash function for matrices has many collisions with permutation matrices: to The Hash function for matrices suffers from many collisions with permutation matrices
Note: See TracTickets for help on using tickets.