Projects

Put flint2 into Sage

• People: Bill H., Mike H., Fredrik J., Andy N., Sebastian P.
• Building flint2 in Sage

  1. Update MPFR to 3.1.0 - http://trac.sagemath.org/sage_trac/ticket/11666

     • http://sage.math.washington.edu/mpfr-3.1.0.spkg (Mike Hansen)

  2. Update MPFI to 1.5.0 - http://trac.sagemath.org/sage_trac/ticket/12171

     • http://sage.math.washington.edu/home/mhansen/mpfi-1.5.0.spkg (Mike Hansen)

  3. Reinstall http://sagemath.org/packages/standard/libfplll-3.0.12.p1.spkg

  4. Install flint2 spkg (beware, this will break Sage)

     • http://sage.math.washington.edu/flint-2.3.spkg

  5. touch SAGE_ROOT/devel/sage/sage/combinat/partitions.*
  6. Run "sage -b"

Switch some of the /eclib/mwrank code to use flint2, and upgrade the eclib spkg in Sage

• People: John C., David H., Martin R., Maarten D., Flint developers

• Sage has a rather old version of eclib in it. It should be easy to upgrade the spkg. DONE: http://trac.sagemath.org/sage_trac/ticket/10993 is ready for review -- in fact has just received a positive review!

Help the Singular developers make better use of flint2

• People: Martin L., Simon K., Burcin E., Flint developers

Updated my (mlee) experimental interface from Flint2 to Singular, to make use of the new polynomial factorization over Z/p. This sped up some of Singular's tests by a factor of 2 (compared to the regular Singular which uses NTL). However there are still some issues related to maybe mpir and/or the lack of a half gcd in Flint2 which need to be investaged.

You can have a look at the Singular FLINT interface here: https://github.com/mmklee/Sources/wiki/Singular-With-Flint2. And hopefully this will be extended soon (use FLINT multiplication, division etc. during multivariate polynomial factorization)

In the near future it would be great if FLINT supported:

• asymptotically fast GCD for Z[x]
• build system improvements
  • version number in header file (to help auto* decide if we have the right version)

To replace NTL completely, we need:

• factorization over Z[x]
• factorization over GF(p^k)[x]
• LLL

--(Linear algebra mod p, for log_2 p = 64)--

• People: Martin A.

Flint2 has an implementation for asymptotically fast linear algebra mod p for p up to 2^64. I (malb) am curious whether it can be improved using ideas inspired by M4RIE, i.e., replace multiplications by additions using pre-computation tables. Whether this is beneficial will depend on how much slower multiplication is than additions.

Update (2011-12-15 10:57): It seems the difference between scalar multiplication and addition is too small for these tricks to make sense.

Update (2011-12-20 11:10): Okay, project cancelled, none of the tricks I could think of make sense.

#include <flint.h>
#include <nmod_mat.h>
#include <profiler.h>
#include <stdio.h>

#include "cpucycles-20060326/cpucycles.h"

int main(int argc, char *argv[]) {
  nmod_mat_t A,B,C;
  flint_rand_t state;
  unsigned long long cc0 = 0, cc1 = 0;
  unsigned long i,j;

  unsigned long long p = 4294967311ULL;

  flint_randinit(state);

  nmod_mat_init(A, 2000, 2000, p);
  nmod_mat_init(C, 2000, 2000, p);
  nmod_mat_randfull(A, state);

  cc0 = cpucycles();
  nmod_mat_scalar_mul(C, A, 14234);
  cc0 = cpucycles() - cc0;
  printf("scalar multiplication: %llu\n",cc0);

  cc1 = cpucycles();
  for (i = 0; i < A->r; i++) {
    for (j = 0; j < A->c; j++) {
      C->rows[i][j] =  A->rows[i][j] + A->rows[i][j];
    }
  }
  cc1 = cpucycles() - cc1;
  printf("addition: %llu\n",cc1);

  printf("ratio: %lf\n",((double)cc0)/(double)cc1);

  nmod_mat_clear(A);
  nmod_mat_clear(C);
  flint_randclear(state);
  return 0;
}

Gives a ratio of about 4.5. But then, some of it is due to load/store times, so it might still make sense to try.

Linear algebra mod p^n, for log_2 p small-ish

• People: Martin A., Simon K., Johan B., Burcin E.

Linear algebra over GF(p^k) can be reduced to linear algebra over GF(p) and for GF(2^k) the performance is very nice. Hence, it would be a good project to develop some somewhat generic infrastructure for dense matrices over GF(p^k), or even *any* extension field? The natural place to put this would be LinBox but perhaps we can start stand-alone and then integrate it with LinBox if LinBox is too scary to start with. Some references (concerning prime slicing) are given at trac ticket #12177

• #12177 contains an experimental patch implementing templated matrix classes with the polynomial with matrix coefficients representation. The patch also implements naive and toom multiplication of matrices over GF(p^k) using FFLAS.

Some timings:

p = 17, n = 2000

k  magma        naive   toom
2    2.620      4.51     4.39
3   17.900      10.25    7.32
4   54.320      19.35   10.11
5   33.480      28.80   13.07
6   50.120      44.75   15.93
7   46.860      56.35   19.12
8   71.590      81.65   22.04
9   79.580

- magma timings are on a different machine with similar performance

BKZ 2.0

• People: Martin A., Andy N.

At AsiaCrypt 2011 Chen and Nguyen presented their new BKZ implementation which is much much more efficient than that in NTL. As far as I understand, the main improvements are due to "extreme pruning" as presented in a paper at EuroCrypt 2010 and perhaps careful parameter choice. As far as I understand, they do not plan to make their code available. I don't know how much work it would be, but perhaps it would be a nice idea to patch NTL's BKZ to include extreme pruning and/or to port it to Flint2?

Improve polynomial factoring mod p in flint2

• People: Fredrik J., Andy N., David H.

The Cantor-Zassenhaus implementation in the flint2 nmod_poly module could be optimized:

• Make exponentiation faster by precomputing a Newton inverse of the modulus
• Use sliding window exponentiation
• Use the von zur Gathen / Shoup algorithm (adapt the fast power series composition code for modular composition)

Modular forms code in Sage

• People: David L., John C., Jan V., Frithjof, Johan B., Maarten D., Martin R., Simon K.
• review patches

  • #5048: Johan B. has done this one. (reviewed positivly)

  • #11601: depends on #5048; now rebased; Johan working on this. Done. (reviewed positively)

  • #10546: depends on #11601; Jan V to take a look (reviewed positively)

  • #12043: DL to work on this (needs review)

  • #10658: Martin R and Frithjof will have a look at this (reviewed positively)

  • #12124: Martin R and Frithjof will have a look at this (reviewed positively)

• Start working towards putting Edixhoven's algorithm into Sage. The meta-ticket for this is #12132.

  • Implement the upper half plane: #9439

  • Add a LLL for matrices over QQ and RR: #12501. Andy Novocin proposed some other methods to use LLL to handle Johan's problem.

Open MP and FLINT

• People: David H., Fredrik J., Bogdan B., Julian R.,

Miscellaneous Sage Algebra and Number Theory patches

• People: Francis C., Monique v B., Florian B., Sam S., Michiel K, Bogdan B., Colton, Jan, Marco S., Paul Z., Johan B., Daniel B.
• Patches with positive review or closed tickets:

  • #11319 Cannot create homomorphism from prime residue field to finite field

  • #11417 binomial of polynomial is not polynomial

  • #11673 is_unit not properly implemented for algebraic integers

  • #11838 Multivariate factorization over non-prime finite fields hangs

  • #12156 Pretty print LatexExpr directly

  • #12176 Compute Minkowski bound for relative number fields

  • #12182 Calculate the trace dual of an order in a number field

  • #12183 Absolute and relative norm functions for number field elements

  • #12185 Bug in norm for orders of relative number fields

  • #12191 is_squarefree for integer polynomials

  • #12196 Improve latex for quadratic fields

  • #12210 GF(p) constructor should check primality of p only once

  • #12218 Content of general polynomial

• Patches needing review:

  • #11930 Disallow non-smooth hyperelliptic curves, and let hyperelliptic curves know they are not singular (needs review!)

• Patches needing work or info:

  • #4283 A Speed-up Patch for NTL's ZZXFactoring.c (needs work)

  • #11235 Make the ipython edit magic command edit the right file and show both files when doing "??" (needs work)

  • #12179 Binomial of integer (mod n) returns integer (needs work)

  • #12186 Faster norm calculations (needs work).

Simon and ComputeL GP scripts

• People: John C., Martin R.

• Revive work of March Sage Days: see http://trac.sagemath.org/sage_trac/ticket/11005

Elliptic curve isogenies

• People: Kimi T., John C., François Morain., Monique v B., Özge Ç., Marco S.

• Sage has a fast implementation of l-isogenies for l=2,3,5,7,13 (for which X_0(l) has genus zero). Kimi has a similarly fast algorithm for those l for which X_0(l) is hyperelliptic (l up to 71), implemented in Sage, which need to be made into a patch for Sage.

Mestre's algorithm for constructing hyperelliptic curves from their invariants

• People: Florian B., Marco S., Lassina D.
• Trac tickets:

  • #6341 (needs work) contains Florian's code for

    • Mestre's algorithm
    • The covariant z_0
    • SL2(ZZ)-reduction

  • #12199 (new) case of curves with automorphisms

  • #12200 (new) case of characteristic two (and three, and five)

  • #12204 (needs work, depends on #6341) reducing the defining polynomial of hyperelliptic curves

  • no ticket yet: no code yet for covariant z, reference for the invariant: http://www.warwick.ac.uk/~masgaj/papers/redp1.pdf

  • no ticket yet: SL2(number field)-reduction
    • case of real quadratic fields of class number one: bad code that works surprisingly well (Marco, not on trac), to be finished later

Tate's Algorithm over function fields

• People: Frithjof S, John C., Marco S., Julian R.

There is a Magma implementation based on John's number field implementation here.

Fix some memory leak that was found using elliptic curves

• People: Simon K., Jean-Pierre F., Paul Z.

The solution is to use weak references for caching homsets. Little problem: Up to now, it was possible to have category objects that are no instances of CategoryObject and thus do not support weak references. But people seem to agree that this should be strongly deprecated. #11521 needs review!

The topic is also related with #715, which proposes to use weak references for the coerce map cache. The problem is that the cache uses a special hand-made dictionary (for efficiency), and so we have no simple drop-in replacement such as WeakKeyDictionary.

Implement finite algebras

• People: Johan B., Michiel K.

The trac ticket for this is 12141.

Things related to PARI/GP

• People: Jeroen D.

• #12203: Implement is_PariGpElement

• #12158: Segfault in PARI's err_init() during pari_init_opts(): positive_review

• #9948: Conversion between p-adics and PARI/GP