Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#7715 closed enhancement (fixed)

implement vectors mod 2 as M4RI matrices with one row

Reported by: malb Owned by: was
Priority: major Milestone: sage-4.3
Component: linear algebra Keywords: vector, M4RI, matrix, GF(2)
Cc: SimonKing Merged in: sage-4.3.rc1
Authors: Martin Albrecht Reviewers: Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

In order to resolve the embarrassing situation at #3684, we need faster vectors mod 2.

Attachments (1)

vector_mod2_dense.patch​ (47.9 KB) - added by malb 12 years ago.

Download all attachments as: .zip

Change History (5)

comment:1 Changed 12 years ago by malb

The speed-up provided by this patch is considerable (but not as much as one would hope for). Here's the example from #3684:

Before 

sage: A = random_matrix(GF(2),1000,2000)
sage: %time K = A.right_kernel()
CPU times: user 11.24 s, sys: 0.02 s, total: 11.25 s
Wall time: 11.42 s

After 

sage: A = random_matrix(GF(2),1000,2000)
sage: %time K = A.right_kernel()
CPU times: user 0.15 s, sys: 0.00 s, total: 0.15 s
Wall time: 0.16 s

Speed-up: 11.25/0.15 = 75

Another example

Before 

sage: VS = VectorSpace(GF(2),10^4)
sage: e = VS.random_element()
sage: f = VS.random_element()
sage: %timeit e+f
10000 loops, best of 3: 89.8 µs per loop
sage: %timeit e*f
10000 loops, best of 3: 146 µs per loop

After 

sage: VS = VectorSpace(GF(2),10^4)
sage: e = VS.random_element()
sage: f = VS.random_element()
sage: %timeit e+f
1000000 loops, best of 3: 1.08 µs per loop
sage: %timeit e*f
100000 loops, best of 3: 2.47 µs per loop

Speed-ups: 83 and 59.

The attached patch might indeed depend on #3684.

Changed 12 years ago by malb

comment:2 Changed 12 years ago by malb

  • Status changed from new to needs_review

comment:3 Changed 12 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Reviewers set to Mike Hansen
  • Status changed from needs_review to closed

Looks good to me.

comment:4 Changed 12 years ago by mhansen

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.