Opened 9 years ago
Closed 8 years ago
#15148 closed enhancement (fixed)
Improve point counting for hyperelliptic curves
Reported by: | goncalves | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.2 |
Component: | algebraic geometry | Keywords: | sd53 hyperelliptic curve |
Cc: | defeo | Merged in: | |
Authors: | Cécile Gonçalves, Jean-Pierre Flori, Jan Tuitman | Reviewers: | Jan Tuitman, Jennifer Balakrishnan, Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | 8029bc6 (Commits, GitHub, GitLab) | Commit: | 8029bc64eb47fe659c3b06df7fa2caad5be8d40e |
Dependencies: | #15108 | Stopgaps: |
Description (last modified by )
Harvey's hypellfrob program is shipped with Sage but was not actually used to count points on hyperelliptic curves.
This ticket intends to fix that (and add several other minor improvements).
Change History (24)
comment:1 Changed 9 years ago by
- Branch set to u/goncalves/ticket/15148
- Created changed from 09/03/13 13:42:47 to 09/03/13 13:42:47
- Modified changed from 09/03/13 13:42:47 to 09/03/13 13:42:47
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
comment:4 Changed 9 years ago by
- Keywords sd53 hyperelliptic curve added
comment:5 Changed 9 years ago by
- Branch changed from u/goncalves/ticket/15148 to u/jpflori/15148
- Description modified (diff)
- Status changed from new to needs_review
- Summary changed from Make count_points() faster to Improve point counting for hyperelliptic curves
comment:6 Changed 9 years ago by
- Commit set to 55cdcf39b1b37f443ba441a2a861b69e8ab726f5
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:55cdcf3] | Refactor point counting code for hyperelliptic curves. |
[changeset:86261b1] | Improve count_points |
[changeset:a1f9bec] | Merge remote-tracking branch 'origin/build_system' into build_system |
[changeset:4cb7db9] | Merge remote-tracking branch 'origin' into build_system |
comment:7 Changed 9 years ago by
- Commit changed from 55cdcf39b1b37f443ba441a2a861b69e8ab726f5 to fc7a56981dac741302fb1b540cdf448a759347f2
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:fc7a569] | First bunch of fixes and missing examples. |
comment:8 Changed 9 years ago by
- Reviewers set to Jan Tuitman
comment:9 Changed 9 years ago by
- Branch changed from u/jpflori/15148 to u/jpflori/ticket/15148
comment:10 Changed 9 years ago by
See #11980 for a follow-up.
comment:11 Changed 9 years ago by
- Reviewers changed from Jan Tuitman to Jan Tuitman, Jennifer Balakrishnan
- Status changed from needs_review to positive_review
This looks good to me.
comment:12 Changed 8 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:13 Changed 8 years ago by
This ticket leads to some test failures (did you check long doctests?). Please fix...
comment:14 Changed 8 years ago by
- Status changed from positive_review to needs_work
I thought so... I'll try to fix the failures tonight.
comment:15 Changed 8 years ago by
- Dependencies set to #15108
- Work issues set to rebase tests on top of #15108
I think that the doctest failure are caused by #15108 which makes base extension of hyperellipticurves smarter and triggers use of the new code for hyperelliptic curves introduced here and which wasn't used for more general schemes... The fix should be trivial.
comment:16 Changed 8 years ago by
And of course I cannot built the latest versions of Sage on my laptop because of glibc's bug in scanf.
comment:17 Changed 8 years ago by
- Commit changed from fc7a56981dac741302fb1b540cdf448a759347f2 to 63bf717e1ecb11767db4dfd49af4e03ae291129e
Branch pushed to git repo; I updated commit sha1. New commits:
63bf717 | Rebase on top of #15108.
|
comment:18 Changed 8 years ago by
- Status changed from needs_work to needs_review
- Work issues rebase tests on top of #15108 deleted
Tests and some doc (trivially) updated. Passes all tests (on POWER7...).
comment:19 Changed 8 years ago by
For a potential reviewer, the ticket used to be positively reviewed, and the latest changes are really trivial, taking the inclusion of another ticket into account.
comment:20 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:21 Changed 8 years ago by
- Cc defeo added
comment:22 Changed 8 years ago by
- Commit changed from 63bf717e1ecb11767db4dfd49af4e03ae291129e to 8029bc64eb47fe659c3b06df7fa2caad5be8d40e
Branch pushed to git repo; I updated commit sha1. New commits:
8029bc6 | Merge remote-tracking branch 'trac/develop' into ticket/15148
|
comment:23 Changed 8 years ago by
- Reviewers changed from Jan Tuitman, Jennifer Balakrishnan to Jan Tuitman, Jennifer Balakrishnan, Volker Braun
- Status changed from needs_review to positive_review
comment:24 Changed 8 years ago by
- Branch changed from u/jpflori/ticket/15148 to 8029bc64eb47fe659c3b06df7fa2caad5be8d40e
- Resolution set to fixed
- Status changed from positive_review to closed
When you only want the number of rational points (and not the complete zeta function) you can use a (g times) lower precision. In this case you shouldn't use .frobenius_polynomial but ._frobenius_matrix and compute the trace of this matrix.
It is not necessary to exclude the case n>2g, but in this case (and already for n>=g) it is probably better to use .frobenius_polynomial and compute the number of points by expanding a power series (as we discussed in Rennes).
So:
1) for n<g use ._frobenius_matrix to compute matrix F and compute the traces of F, ... ,Fn.
2) for n>=g use .frobenius_polynomial and compute the coefficients of the log of the zeta function.
Would you like to change this, or can I give it a try? (I'm at SAGE days this week, trying to do something useful)