Ticket #3969 (closed defect: fixed)

Opened 3 months ago

Last modified 3 months ago

[with patch, positive review] Matrix_mod2_dense hashs follow-up (see #3724)

Reported by: malb Assigned to: was
Priority: major Milestone: sage-3.1.2
Component: linear algebra Keywords:
Cc:

Description

Robert wrote: """ 

Matrix hashes are specifically designed to be compatible with each other: 
sage: M = random_matrix(GF(2), 10, 10)
sage: M.set_immutable()
sage: hash(M)
561
sage: MZ = M.change_ring(ZZ)
sage: MZ.set_immutable()
sage: hash(MZ)
561
sage: MS = M.sparse_matrix()
sage: MS.set_immutable()
sage: hash(MS)
561

This patch seems to break that. At a minimum, it seems sparse and dense should hash to the same thing. If we want to change this policy, we should at least ask on sage-devel. """

Attachments

3969-fast-matmod2-hash.patch (6.1 kB) - added by robertwb on 08/31/2008 03:33:31 AM.
3969-fast-matmod2-hash-rebased.patch (7.0 kB) - added by malb on 08/31/2008 12:33:53 PM.

Change History

08/31/2008 03:33:31 AM changed by robertwb

  • attachment 3969-fast-matmod2-hash.patch added.

08/31/2008 03:36:46 AM changed by robertwb

  • summary changed from Matrix_mod2_dense hashs follow-up (see #3724) to [with patch, needs review] Matrix_mod2_dense hashs follow-up (see #3724).

This is not as fast as xoring all the matrix entries, but is still very fast, and compatible (as possible) with the all the other matrices. 

sage: M = random_matrix(GF(2), 3500, 3500)
sage: M.set_immutable()
sage: time hash(M)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
1523294
sage: M = random_matrix(GF(2), 10000, 10000)
sage: M.set_immutable()
sage: time hash(M)
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
37785898

08/31/2008 12:33:53 PM changed by malb

  • attachment 3969-fast-matmod2-hash-rebased.patch added.

08/31/2008 12:39:40 PM changed by malb

  • summary changed from [with patch, needs review] Matrix_mod2_dense hashs follow-up (see #3724) to [with patch, positive review] Matrix_mod2_dense hashs follow-up (see #3724).

I rebased the patch to 3.1.2.alpha3 and fixed a small typo in a comment. I get the overall idea of the algorithm, which I find a rather elegant approach. Doctests pass. Positive review. I'm not sure if there could be an issue with 32-bit machines and matching hashs.

09/01/2008 05:06:28 AM changed by mabshoff

malb's patch has a stray 32bit in it that causes the following failure: 

sage -t  devel/sage/sage/matrix/matrix_mod2_dense.pyx       
**********************************************************************
File "/Users/mabshoff/sage-3.1.2.alpha3/tmp/matrix_mod2_dense.py", line 284:
    sage: {B:0} # indirect doctest
Expected:
    {[0 1 0]
    [0 1 1]
    [0 0 0]: 0}
    '-0x21524113' 
Got:
    {[0 1 0]
    [0 1 1]
    [0 0 0]: 0}
**********************************************************************

This is obviously trivial to fix :)

Cheers,

Michael

09/01/2008 05:09:17 AM changed by malb

Looks like a merge error, IMHO.

09/01/2008 05:21:05 AM changed by mabshoff

  • status changed from new to closed.
  • resolution set to fixed.

Merged 3969-fast-matmod2-hash-rebased.patch (minus the one line doctest merge accident) in Sage 3.1.2.alpha4