Ticket #7715 (closed enhancement: fixed)

Opened 3 years ago

Last modified 3 years ago

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 Work issues:
Report Upstream: N/A Reviewers: Mike Hansen
Authors: Martin Albrecht Merged in: sage-4.3.rc1
Dependencies: Stopgaps:

Description

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

Attachments

vector_mod2_dense.patch Download (47.9 KB) - added by malb 3 years ago.

Change History

comment:1 Changed 3 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 3 years ago by malb

comment:2 Changed 3 years ago by malb

  • Status changed from new to needs_review

comment:3 Changed 3 years ago by mhansen

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

Looks good to me.

comment:4 Changed 3 years ago by mhansen

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