Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Requesting columns of matrices over GF(2) is very slow #38150

Closed
2 tasks done
GiacomoPope opened this issue Jun 4, 2024 · 0 comments · Fixed by #38152
Closed
2 tasks done

Requesting columns of matrices over GF(2) is very slow #38150

GiacomoPope opened this issue Jun 4, 2024 · 0 comments · Fixed by #38152
Labels
c: linear algebra t: bug
Milestone
sage-10.4

Comments

@GiacomoPope
Copy link
Contributor

GiacomoPope commented Jun 4, 2024 •
edited
Loading

Steps To Reproduce

sage: M2 = random_matrix(GF(2), 2000, 2000)
sage: %time _  = M2.rows()
CPU times: user 8.05 ms, sys: 671 µs, total: 8.72 ms
Wall time: 8.41 ms
sage: %time _  = M2.columns()
CPU times: user 10.2 s, sys: 19.1 ms, total: 10.3 s
Wall time: 10.3 s
sage: %time _  = M2.T.rows()
CPU times: user 8.98 ms, sys: 697 µs, total: 9.67 ms
Wall time: 9.39 ms
sage: M2.T.rows() == M2.columns()
True
sage: M3 = random_matrix(GF(3), 2000, 2000)
sage:  %time _  = M3.rows()
CPU times: user 235 ms, sys: 12.9 ms, total: 248 ms
Wall time: 247 ms
sage:  %time _  = M3.columns()
CPU times: user 337 ms, sys: 15.1 ms, total: 352 ms
Wall time: 351 ms
sage: M2e = random_matrix(GF(2^4), 2000, 2000)
sage: %time _  = M2e.rows()
CPU times: user 313 ms, sys: 8.28 ms, total: 322 ms
Wall time: 321 ms
sage: %time _  = M2e.columns()
CPU times: user 341 ms, sys: 7.55 ms, total: 348 ms
Wall time: 348 ms

Expected Behavior

Requesting rows and columns should take equal time

Actual Behavior

Requesting columns is very slow

Additional Information

No response

Environment

- **Sage Version**: SageMath version 10.4.beta8

Checklist

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
  • I have read the documentation and troubleshoot guide
@GiacomoPope GiacomoPope mentioned this issue Jun 4, 2024
Merged
vbraun pushed a commit to vbraun/sage that referenced this issue Jun 8, 2024
sagemathgh-38152: Improve performance of computing columns of matrice…
ec43912 
…s over GF(2)

    
In response to issue sagemath#38150 I
have adjusted the request for columns over dense matrices over GF(2) by
replacing the standard call to columns with a transpose followed by a
request of rows.

This results in almost a 1000x speed up for large matrices (for the
example in the issue).

### Old Implementation

```py
sage: M2 = random_matrix(GF(2), 2, 2)
sage: %time _  = M2.columns()
CPU times: user 4.14 ms, sys: 1.67 ms, total: 5.81 ms
Wall time: 10.9 ms
sage: %time _  = M2.rows()
CPU times: user 109 µs, sys: 130 µs, total: 239 µs
Wall time: 1.39 ms
sage: M2 = random_matrix(GF(2), 200, 200)
sage: %time _  = M2.columns()
CPU times: user 87.9 ms, sys: 1.32 ms, total: 89.2 ms
Wall time: 88.3 ms
sage: %time _  = M2.rows()
CPU times: user 811 µs, sys: 96 µs, total: 907 µs
Wall time: 912 µs
sage: M2 = random_matrix(GF(2), 2000, 2000)
sage: %time _  = M2.columns()
CPU times: user 7.94 s, sys: 9.11 ms, total: 7.95 s
Wall time: 7.97 s
sage: %time _  = M2.rows()
CPU times: user 7.49 ms, sys: 770 µs, total: 8.26 ms
Wall time: 7.97 ms
```

### New Implementation

```py
sage: M2 = random_matrix(GF(2), 2, 2)
sage: %time _  = M2.columns()
CPU times: user 1.01 ms, sys: 261 µs, total: 1.27 ms
Wall time: 3.75 ms
sage: %time _  = M2.rows()
CPU times: user 54 µs, sys: 8 µs, total: 62 µs
Wall time: 65.1 µs
sage: M2 = random_matrix(GF(2), 200, 200)
sage: %time _  = M2.columns()
CPU times: user 1.09 ms, sys: 40 µs, total: 1.13 ms
Wall time: 1.13 ms
sage: %time _  = M2.rows()
CPU times: user 712 µs, sys: 15 µs, total: 727 µs
Wall time: 732 µs
sage: M2 = random_matrix(GF(2), 2000, 2000)
sage: %time _  = M2.columns()
CPU times: user 9.07 ms, sys: 746 µs, total: 9.82 ms
Wall time: 9.54 ms
sage: %time _  = M2.rows()
CPU times: user 7.82 ms, sys: 687 µs, total: 8.51 ms
Wall time: 8.18 ms
```

Fixes sagemath#38150
    
URL: sagemath#38152
Reported by: Giacomo Pope
Reviewer(s): grhkm21
@mkoeppe mkoeppe added this to the sage-10.4 milestone Jun 9, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: linear algebra t: bug
Projects
None yet
Milestone
sage-10.4
Development

Successfully merging a pull request may close this issue.

Improve performance of computing columns of matrices over GF(2) GiacomoPope/sage
2 participants
@mkoeppe @GiacomoPope