Opened 10 years ago

Last modified 12 months ago

#13376 needs_info enhancement

Optional SPKG for SmallJac — at Version 8

Reported by: pavpanchekha Owned by: tbd
Priority: major Milestone: sage-wishlist
Component: packages: optional Keywords:
Cc: jpflori, kedlaya Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by pavpanchekha)

Smalljac is a library and set of programs for computing L-polynomials and Jacobian group structures of low genus curves over finite fields. Given a curve C of genus 1 or 2 defined over Q or a quadratic number field, it will efficiently compute either the sequence of L-polynomials or Jacobian group structures arising from the reduction of C at all primes of good reduction up to a specified norm bound.

This set of SPKGs and the corresponding patch to Sage 5.6 add support for using smallJac from Sage.

  • EllipticCurve.aplist can be run with algorithm="smalljac", yielding run times of six times faster on a single core.
  • EllipticCurve.aplists provides more usable representation the above, and supports number fields (multiple reductions per prime norm). See the documentation for more, but in general aplist couldn't be made very easy to use for the number field case.
  • EllipticCurve.grouplists gives the abelian groups isomorphic to various reductions of a curve.
  • EllipticCurve.lpolylists yields the L-Polynomials of reductions of a curve.
  • EllipticCurve.guess_sato_tate_group attempts to guess the Sato-Tate group of the Jacobian of a curve of genus 1 or 2 based on the distribution of its L-polynomial coefficients.
  • EllipticCurve.moments yields the moments of the distribution of coefficients of the L-Polynomials.
  • EllipticCurve.trace_histogram gives a very simple histogram for the distribution of traces of Frobenius of a curve, reduced at a range of primes.

For all of the above methods (except aplist), identical functionality exists (with the same name) for genus 2 curves. All of the above methods also parallelize over multiple cores (currently, to a power of two cores). For large problems, this achieves approximately linear speedup; for example, computing the first billion traces of Frobenius of an ordinary elliptic curve is 178 times faster on 32 cores.

For each of these features, there is Sage documentation docstring-style documentation.

The SPKGs only compile and work on 64-bit machines, since SmallJac? only supports 64-bit architectures, and require GMP. Two SPKGs are provided, since SmallJac? depends on ff_poly, but so does some of Drew Sutherland's other code, so it makes sense to split the two. They've been tested to work on a completely clean install of Sage on at least two differently-configured machines.

The patch has been tested to apply cleanly to 5.6.

SPKGs are available at http://www.mit.edu/~pavpan/. Install first the ff_poly package and then the smalljac package, with the normal Sage package installation mechanisms. Then apply the patch to a fresh branch of the source code and recompile that branch.

Change History (13)

Changed 10 years ago by pavpanchekha

SPKG for ff_poly

Changed 10 years ago by pavpanchekha

SPKG for smalljac

Changed 10 years ago by pavpanchekha

Patch to Sage 5.2 to support interfacing with SmallJac?

comment:1 Changed 9 years ago by jpflori

  • Cc jpflori added

Changed 9 years ago by pavpanchekha

Changed 9 years ago by pavpanchekha

comment:2 Changed 9 years ago by pavpanchekha

I've attached three more files -- SPKGs for up-to-date versions of smalljac and ff_poly, and a patch against Sage 5.6. The list of features is identical -- bug fixes, performance improvements, and basic stabilization has happened in the mean time.

comment:3 follow-up: Changed 9 years ago by ohanar

a few of quick comments:

  • don't touch unrelated files (e.g. sage/numerical/backends/glpk_backend.pxd)
  • it would probably make more sense to default to smalljac over pari if it is installed
  • it would help if your trac ticket included installation instructions at the bottom, and if it is ready to be reviewed, you should change the status to needs review

also, I'm not the most knowledgeable on the matter, but my understanding was that optional packages need to work on all supported platforms, so it might be more of an experimental package since it doesn't work on 32bit platforms

comment:4 follow-up: Changed 9 years ago by ohanar

This currently doesn't work at all since you didn't add the file sage/libs/smalljac/*. Also, please do not attach spkgs to tickets in the future, instead post a link to the file.

comment:5 in reply to: ↑ 4 Changed 9 years ago by leif

Replying to ohanar:

Also, please do not attach spkgs to tickets in the future, instead post a link to the file.

Note that this doesn't even depend on its size; in general, binary files shouldn't be attached.

By convention, we also add which patch to apply (in which order) to which of the Sage repositories to the ticket's description.

Also, the 'Authors' field is empty...

comment:6 Changed 9 years ago by fbissey

Don't like the spkgs. Both SPKG.txt aren't updated to reflect the version changes. The first thing that I see in both is

#!/usr/bin/env bash

CFLAGS="-fPIC -mtune=k8 -pedantic -std=gnu99"
LDFLAGS="-static"

-fPIC and -static are kind of opposite but you will want to fold a library that you only know how to build static into a shared object so you need the -fPIC. Would be better to build shared in the first place. Is the "-mtune=k8" the thing that impose 64bitness? Anyway that assume way too much about the underlying cpu even on x86_64. We have people working on arm and ppc64, that's 64bit too.

When you say 64bit do you mean x86_64 as in "I have used simmd instructions that are only available on this cpus"(pet hate) or something else?

If you have used x86_64 specific instructions I am not sure we can ever move this out of optional since we support (or at least aim to) a larger range of hardware.

And just looking I have found assembly....

comment:7 in reply to: ↑ 3 Changed 9 years ago by pavpanchekha

Replying to ohanar:

  • don't touch unrelated files (e.g. sage/numerical/backends/glpk_backend.pxd)

My mistake, sorry. I've updated the patch file to remove such garbage and add the actual files instead.

  • it would probably make more sense to default to smalljac over pari if it is installed

This seemed like a more controversial option, though of course that wouldn't be a problem.

  • it would help if your trac ticket included installation instructions at the bottom, and if it is ready to be reviewed, you should change the status to needs review

Will do. I read through the developer guide, but either forgot or didn't see things like this.

Replying to ohanar:

Also, please do not attach spkgs to tickets in the future, instead post a link to the file.

Alright. Links to the two SPKGs are at http://www.mit.edu/~pavpan/. They have small updates from the ones included above.

Replying to leif:

Also, the 'Authors' field is empty...

Where?

Replying to fbissey:

Anyway that assume way too much about the underlying cpu even on x86_64.

When you say 64bit do you mean x86_64 as in "I have used simmd instructions that are only available on this cpus"(pet hate) or something else?

And just looking I have found assembly....

No, I think the meaning (and I am not Drew Sutherland so I do not know exactly) is that fast 64-bit integer operations are assumed throughout, and some algorithms are optimized to use the extra registers available on 64-bit systems. The single assembly instruction used is that which yields the high bit of an unsigned integer. This can always be written as a loop, but that will hurt performance. I do not know if such an instruction is available on arm, ppc, or elsewhere.

-fPIC and -static are kind of opposite but you will want to fold a library that you only know how to build static into a shared object so you need the -fPIC. Would be better to build shared in the first place.

I believe static compilation is for performance reasons. I can ask Drew Sutherland how important that is. The compilation certainly works without it. Similarly the tuning parameter, though suggesting to GCC that it is compiling to a platform with a full x86_64 register set and integer size is again important to performance.

comment:8 Changed 9 years ago by pavpanchekha

  • Description modified (diff)
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.