Opened 6 years ago
Closed 6 years ago
#15148 closed enhancement (fixed)
Improve point counting for hyperelliptic curves
Reported by:  goncalves  Owned by:  

Priority:  minor  Milestone:  sage6.2 
Component:  algebraic geometry  Keywords:  sd53 hyperelliptic curve 
Cc:  defeo  Merged in:  
Authors:  Cécile Gonçalves, JeanPierre Flori, Jan Tuitman  Reviewers:  Jan Tuitman, Jennifer Balakrishnan, Volker Braun 
Report Upstream:  N/A  Work issues:  
Branch:  8029bc6 (Commits)  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 6 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 6 years ago by
 Description modified (diff)
comment:3 Changed 6 years ago by
comment:4 Changed 6 years ago by
 Keywords sd53 hyperelliptic curve added
comment:5 Changed 6 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 6 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 remotetracking branch 'origin/build_system' into build_system 
[changeset:4cb7db9]  Merge remotetracking branch 'origin' into build_system 
comment:7 Changed 6 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 6 years ago by
 Reviewers set to Jan Tuitman
comment:9 Changed 6 years ago by
 Branch changed from u/jpflori/15148 to u/jpflori/ticket/15148
comment:10 Changed 6 years ago by
See #11980 for a followup.
comment:11 Changed 6 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 6 years ago by
 Milestone changed from sage6.0 to sage6.1
comment:13 Changed 6 years ago by
This ticket leads to some test failures (did you check long doctests?). Please fix...
comment:14 Changed 6 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 6 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 6 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 6 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 6 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 6 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 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:21 Changed 6 years ago by
 Cc defeo added
comment:22 Changed 6 years ago by
 Commit changed from 63bf717e1ecb11767db4dfd49af4e03ae291129e to 8029bc64eb47fe659c3b06df7fa2caad5be8d40e
Branch pushed to git repo; I updated commit sha1. New commits:
8029bc6  Merge remotetracking branch 'trac/develop' into ticket/15148

comment:23 Changed 6 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 6 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, ... ,F^{n. }
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)