Skip to content

Fix caching in Khuri-Makdisi Jacobian implementation #40221

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.

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

Merged
merged 4 commits into from
Jun 14, 2025

Conversation

vincentmacri
Copy link
Member

@vincentmacri vincentmacri commented Jun 6, 2025

This PR fixes a bug with caching of some expensive parts of the Khuri-Makdisi Jacobian implementation. This speeds up constructing the Jacobian group by approximately 95% on the example below. The speedup was significant enough that I was able to remove long test from all but one test in the Khuri-Makdisi implementation. Testing the entire Khuri-Makdisi implementation takes slightly longer now that we are including more tests, but all the tests I've included finish in under 5 seconds (at least on my machine, if the CI complains we can put back some of the long test markers).

K = GF(5)
Kx.<x> = FunctionField(K)
t = polygen(Kx)
F.<y> = Kx.extension(t^3 + (2*x^2 + 3*x + 3)*t^2 + (3*x^2 + x)*t + x^5 + 3*x^4 + 4*x^3 + 4*x^2 + x + 4)
J = F.jacobian(model='km_small')
%time J.group()  # Before: About 1 minute. After: about 3 seconds.

The performance increase is similar for km_medium and km_large.

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation and checked the documentation preview.

⌛ Dependencies

None

@vincentmacri vincentmacri marked this pull request as ready for review June 6, 2025 23:17
@vincentmacri vincentmacri requested a review from kwankyu June 6, 2025 23:18
Copy link

github-actions bot commented Jun 7, 2025

Documentation preview for this PR (built with commit d85d786; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@kwankyu
Copy link
Collaborator

kwankyu commented Jun 8, 2025

Wow. That was the worst bug I've ever made! Thanks a lot for fixing this.

vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 8, 2025
This PR fixes a bug with caching of some expensive parts of the Khuri-
Makdisi Jacobian implementation. This speeds up constructing the
Jacobian group by approximately 95% on the example below. The speedup
was significant enough that I was able to remove `long test` from all
but one test in the Khuri-Makdisi implementation. Testing the entire
Khuri-Makdisi implementation takes slightly longer now that we are
including more tests, but all the tests I've included finish in under 5
seconds (at least on my machine, if the CI complains we can put back
some of the `long test` markers).

```
K = GF(5)
Kx.<x> = FunctionField(K)
t = polygen(Kx)
F.<y> = Kx.extension(t^3 + (2*x^2 + 3*x + 3)*t^2 + (3*x^2 + x)*t + x^5 +
3*x^4 + 4*x^3 + 4*x^2 + x + 4)
J = F.jacobian(model='km_small')
%time J.group()  # Before: About 1 minute. After: about 3 seconds.
```

The performance increase is similar for `km_medium` and `km_large`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
None

URL: sagemath#40221
Reported by: Vincent Macri
Reviewer(s): Kwankyu Lee
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 9, 2025
This PR fixes a bug with caching of some expensive parts of the Khuri-
Makdisi Jacobian implementation. This speeds up constructing the
Jacobian group by approximately 95% on the example below. The speedup
was significant enough that I was able to remove `long test` from all
but one test in the Khuri-Makdisi implementation. Testing the entire
Khuri-Makdisi implementation takes slightly longer now that we are
including more tests, but all the tests I've included finish in under 5
seconds (at least on my machine, if the CI complains we can put back
some of the `long test` markers).

```
K = GF(5)
Kx.<x> = FunctionField(K)
t = polygen(Kx)
F.<y> = Kx.extension(t^3 + (2*x^2 + 3*x + 3)*t^2 + (3*x^2 + x)*t + x^5 +
3*x^4 + 4*x^3 + 4*x^2 + x + 4)
J = F.jacobian(model='km_small')
%time J.group()  # Before: About 1 minute. After: about 3 seconds.
```

The performance increase is similar for `km_medium` and `km_large`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
None

URL: sagemath#40221
Reported by: Vincent Macri
Reviewer(s): Kwankyu Lee
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 9, 2025
sagemathgh-40221: Fix caching in Khuri-Makdisi Jacobian implementation
    
This PR fixes a bug with caching of some expensive parts of the Khuri-
Makdisi Jacobian implementation. This speeds up constructing the
Jacobian group by approximately 95% on the example below. The speedup
was significant enough that I was able to remove `long test` from all
but one test in the Khuri-Makdisi implementation. Testing the entire
Khuri-Makdisi implementation takes slightly longer now that we are
including more tests, but all the tests I've included finish in under 5
seconds (at least on my machine, if the CI complains we can put back
some of the `long test` markers).

```
K = GF(5)
Kx.<x> = FunctionField(K)
t = polygen(Kx)
F.<y> = Kx.extension(t^3 + (2*x^2 + 3*x + 3)*t^2 + (3*x^2 + x)*t + x^5 +
3*x^4 + 4*x^3 + 4*x^2 + x + 4)
J = F.jacobian(model='km_small')
%time J.group()  # Before: About 1 minute. After: about 3 seconds.
```

The performance increase is similar for `km_medium` and `km_large`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
None
    
URL: sagemath#40221
Reported by: Vincent Macri
Reviewer(s): Kwankyu Lee
@vincentmacri
Copy link
Member Author

Thanks for the quick review!

vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 9, 2025
sagemathgh-40221: Fix caching in Khuri-Makdisi Jacobian implementation
    
This PR fixes a bug with caching of some expensive parts of the Khuri-
Makdisi Jacobian implementation. This speeds up constructing the
Jacobian group by approximately 95% on the example below. The speedup
was significant enough that I was able to remove `long test` from all
but one test in the Khuri-Makdisi implementation. Testing the entire
Khuri-Makdisi implementation takes slightly longer now that we are
including more tests, but all the tests I've included finish in under 5
seconds (at least on my machine, if the CI complains we can put back
some of the `long test` markers).

```
K = GF(5)
Kx.<x> = FunctionField(K)
t = polygen(Kx)
F.<y> = Kx.extension(t^3 + (2*x^2 + 3*x + 3)*t^2 + (3*x^2 + x)*t + x^5 +
3*x^4 + 4*x^3 + 4*x^2 + x + 4)
J = F.jacobian(model='km_small')
%time J.group()  # Before: About 1 minute. After: about 3 seconds.
```

The performance increase is similar for `km_medium` and `km_large`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
None
    
URL: sagemath#40221
Reported by: Vincent Macri
Reviewer(s): Kwankyu Lee
@vbraun vbraun merged commit a1f9934 into sagemath:develop Jun 14, 2025
22 of 24 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants