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: 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) Commit: 8029bc64eb47fe659c3b06df7fa2caad5be8d40e
Dependencies: #15108 Stopgaps:

Description (last modified by jpflori)

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 goncalves

  • 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 goncalves

  • Description modified (diff)

comment:3 Changed 6 years ago by jantuitman

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)

comment:4 Changed 6 years ago by jpflori

  • Keywords sd53 hyperelliptic curve added

comment:5 Changed 6 years ago by jpflori

  • Authors changed from Cécile Gonçalves to Cécile Gonçalves, Jean-Pierre Flori, Jan Tuitman
  • 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 git

  • 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 6 years ago by git

  • 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 jpflori

  • Reviewers set to Jan Tuitman

comment:9 Changed 6 years ago by jpflori

  • Branch changed from u/jpflori/15148 to u/jpflori/ticket/15148

comment:10 Changed 6 years ago by jpflori

See #11980 for a follow-up.

comment:11 Changed 6 years ago by jen

  • 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 vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:14 Changed 6 years ago by jpflori

  • 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 jpflori

  • 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 jpflori

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 git

  • Commit changed from fc7a56981dac741302fb1b540cdf448a759347f2 to 63bf717e1ecb11767db4dfd49af4e03ae291129e

Branch pushed to git repo; I updated commit sha1. New commits:

​63bf717Rebase on top of #15108.

comment:18 Changed 6 years ago by jpflori

  • 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 jpflori

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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:21 Changed 6 years ago by jpflori

  • Cc defeo added

comment:22 Changed 6 years ago by git

  • Commit changed from 63bf717e1ecb11767db4dfd49af4e03ae291129e to 8029bc64eb47fe659c3b06df7fa2caad5be8d40e

Branch pushed to git repo; I updated commit sha1. New commits:

​8029bc6Merge remote-tracking branch 'trac/develop' into ticket/15148

comment:23 Changed 6 years ago by vbraun

  • 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 vbraun

  • Branch changed from u/jpflori/ticket/15148 to 8029bc64eb47fe659c3b06df7fa2caad5be8d40e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.