README.md 10.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

cmh: computation of genus 2 class polynomials.
==============================================

This software package computes Igusa (genus 2) class polynomials, which
parameterize the CM points in the moduli space of 2-dimensional abelian
varieties, i.e. Jacobians of hyperelliptic curves.

This program is also able to compute theta constants at arbitrary
precision (but the interface for this is still to be documented more
clearly).

This documentation consists of several chapters.
 - [Introduction](#introduction)
 - [License](#license)
 - [Prerequisites](#prerequisites)
 - [Compiling](#compiling)
 - [Using](#using)
 - [Output](#output)
 - [Caveats](#caveats)
 - [Internal documentation](#internal-documentation)
 - [Advanced usage, including (but not limited to) MPI](#advanced-usage-including-but-not-limited-to-mpi)


Introduction
------------

CMH computes Igusa class polynomials.

Emmanuel Thomé's avatar
Emmanuel Thomé committed
30 31 32 33
See the [releases](../../releases) page for releases. Note that much of
the development of CMH has happened only in the git repository om the
recent years.

34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
The main authors are:

 - [Andreas Enge](http://www.math.u-bordeaux1.fr/~enge/)
 - [Emmanuel Thomé](http://www.loria.fr/~thome/)

A code base by [Régis
Dupont](http://www.lix.polytechnique.fr/Labo/Regis.Dupont/) is at the
origin of this work.

In March, 2014, we announced the computation of class polynomials for
Shimura class number 20,016. See the separate [announcement
text](announcement-record-computation-cm2.txt) for this computation.

License
-------

```
    cmh -- computation of genus 2 class polynomials and theta constants.
    Copyright (C) 2006, 2010, 2011, 2012, 2013, 2014, 2015 Régis Dupont, Andreas
    Enge, Emmanuel Thomé

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
```

Prerequisites
-------------

The following software libraries are required to compile and use cmh;
we usually recommend to use the latest version and not the absolutely
minimally required one:
 - [GNU MP](http://gmplib.org/) version 4.3.2 or above
 - [GNU MPFR](http://mpfr.org/) version 2.4.2 or above
 - [GNU MPC](http://mpc.multiprecision.org/) version 1.0 or above
 - [MPFRCX](http://mpfrcx.multiprecision.org/) version 0.4.2 or above
 - [FPLLL](http://perso.ens-lyon.fr/damien.stehle/fplll/) version 4.0.4 or above
 - [PARI/GP](http://pari.math.u-bordeaux.fr/) version 2.7.0 or above

The following libraries are optional
 - MPI implementation: any implementation can be used, e.g. openmpi,
   mpich, mvapich2, ...

The development platform is recent Debian GNU/Linux, and most testing has
been done in this environment. As a general rule of thumb, if things bomb
out, a reasonable explanation could be subtle distribution differences,
which are not that hard to fix, but terribly annoying indeed.

A convenience script for fetching and building all the software
prerequisites is in `./config/build-dependencies.sh` ; this builds all the
needed packages in `$topdir/cmh-deps`, but can also be tuned to build
elsewhere (see the script for more information).

Compiling
---------

Distributed tarballs should ship with a `./configure` shell script.
Development checkouts do not. For generating `./configure`, please run the
`./config/autogen.sh` script, which requires the usual autotools
dependencies (`autoconf`, `automake`, `libtool`)

To compile and install, type:
```
./configure [[all relevant flags]]
make
make install
```
It might be very relevant to pass an appropriate `--prefix` option to the
configure script, so that installation is done to a directory writable by
the user.

out-of-source build is supported.

The recognized flags are
```
  --enable-mpi            use mpi to compile a parallel version [default=no]
  --with-gmp=DIR          GMP installation directory
  --with-mpfr=DIR         MPFR installation directory
  --with-mpc=DIR          MPC installation directory
  --with-mpfrcx=DIR       MPFRCX installation directory
  --with-fplll=DIR        FPLLL installation directory
  --with-pari=DIR         PARI installation directory
```
For MPI, see the section later in this document.

Note that `make install` is *not* optional, since making the program run
without doing `make install` first is difficult.

Using
-----

The input to this program is a defining equation for a (for the moment,
only dihedral) quartic CM field, in the form of two nonnegative integers
$`A`$,$`B`$ for a corresponding defining equation $`X^4+A X^2+B`$.  The
pair $`(A,B)`$ must be so that $`A^2-4B`$ is a positive integer which is
not a perfect square, and $`(A,B)`$ minimal in the sense that no smaller
pair defines the same field (the script complains if this is the case).
The special case where the Galois group of $`X^4+A X^2+B`$ is $`Z/2
\times Z/2`$ is also forbidden.

The main entry point is the script placed in the following location by
`make install`:
```
    $prefix/bin/cmh-classpol.sh
```

Its syntax is:
```
    $prefix/bin/cmh-classpol.sh -p -f A B
```

where $`A`$ and $`B`$ are the integers defining the CM field as discussed
above.  This, in effects, does the two out of three possible steps.
 - The `-p` option does the "preparation", which consists in computing a
   list of period matrices corresponding to one orbit under complex
   multiplication. This list ends up in the `.in` file (see next section
   for location and naming).
 - The `-f` option does the big part of the computation, which is the
   computation of class polynomials from the config files. This is
   programmed in C (here and there, when we refer to "the C code", this
   designates the code which gets run for this step). An optional feature
   is provided for doing this step in parallel over several processors or
   nodes. The output ends up in the `.pol` file (again see below).

Additionally, adding the `-c` flag does a third step, which checks the
computed class polynomial for correctness as follows (see also
[`BUGS`](BUGS)).
 - find a Weil number $`p`$
 - find a triple of Igusa invariants corresponding to roots of the class
   polynomials mod $`p`$
 - use Mestre's algorithm to reconstruct a hyperelliptic curve from its
   invariants
 - check that the Jacobian of the curve above has cardinal `$\operatorname{Norm}(1\pm pi)$`.

Some other flags are mostly for interal use. Noteworthy ones are `-N`,
which disables the temporary checkpoint data creation, and `-b xxxx`, which
modifies the starting precision.

Output
------

All output of the program goes to the `data/` directory (which may be a
symbolic link to auxiliary storage).

All files are created with a common prefix `D_A_B`, where $`D`$,$`A`$,$`B`$ are three
integers. $`A`$ and $`B`$ are the integers discussed above, while $`D`$ is the
discriminant of the real quadratic subfield (this is the fundamental
discriminant of $`\mathbb{Q}(\sqrt{A^2-4B})`$.

| file name         | description |
| ----------------- | ----------------------------------------------------------
| `D_A_B.in`        | description of the set of period matrices describing the different irreducible factors of the class polynomials.  The format of this file is used internally, but its details are discussed in the "internal details" section. |
| `D_A_B.pol`       | the different irreducible factors of the class polynomials (more precisely of the CM variety in the moduli space). This is given in triangular form `(H1,H2hat,H3hat)`, and discussed in the "internal details" section. These polynomials are defined over the real quadratic subfield of the reflex field. |
| `D_A_B.gp.log`    | output (terse) of the pari/gp program which computes the `.in` file from (A,B) |
| `D_A_B.out`       | output of the C code for computing `.pol` from `.in` |
| `D_A_B.check.log` | output of the pari/gp program which computes a hyperelliptic curve whose Jacobian has CM by the desired field, and checks its cardinality for consistency with the expected value.  [ only if `-c` was provided on the command line of cmh-classpol.sh ] |
| `D_A_B/`          | temporary checkpointing and restart data. The precise meaning and format of these files is not documented, and subject to incompatible change without notice. |

Caveats
-------

See [`BUGS`](BUGS)

Internal documentation
----------------------

The `.in` and `.pol` file formats are discussed in
[`README.format`](README.format)

Advanced usage, including (but not limited to) MPI
--------------------------------------------------

The main C binary which is used to compute class polynomials (the `.pol`
file) from orbits of period matrices (the `.in` file) has an MPI version.
This version can be compiled by passing `--enable-mpi` to configure.

The non-parallel binary is called `cm2`, and the binary is created in the
`$builddir/src`. `make install` installs `cm2` in `$prefix/bin/cm2`

The parallel binary is called `cm2-mpi`, and the binary is created in the
`$builddir/src`. Obviously, `cm2-mpi` is created only if `--enable-mpi` is
passed to configure. `make install` installs `cm2-mpi` in
`$prefix/bin/cm2-mpi`

If you intend to use MPI for computing the class polynomials, this very
likely means that you are well beyond the intended scope for the
`cmh-classpol.sh` script. For this reason, `cmh-classpol.sh` has no provision
for calling `cm2-mpi` directly, and this binary must be called manually.

We assume that you have successfully created a `.in` file (using
`cmh-classpol.sh -p`). Then, the syntax for `cm2`, or `cm2-mpi`, is:
```
    cm2 -i D_A_B.in -o D_A_B.pol [other flags]

    mpirun -n #jobs [other mpi options] cm2-mpi -i D_A_B.in -o D_A_B.pol [other flags]
```


This will eventually write the result in `D_A_B.pol` ; the code has
provision for resuming interrupted computations, as intermediate
computation checkpoints are saved in a subdirectory called `D_A_B/` ;
checkpoints are enabled by default, but they may be disabled using the
`--no-checkpoints` command-line option.