Projects

Contents

  1. Projects
    1. Put flint2 into Sage
    2. Switch some of the /eclib/mwrank code to use flint2, and upgrade the eclib spkg in Sage
    3. Help the Singular developers make better use of flint2
    4. --(Linear algebra mod p, for log_2 p = 64)--
    5. Linear algebra mod p^n, for log_2 p small-ish
    6. BKZ 2.0
    7. Improve polynomial factoring mod p in flint2
    8. Modular forms code in Sage
    9. Open MP and FLINT
    10. Miscellaneous Sage Algebra and Number Theory patches
    11. Simon and ComputeL GP scripts
    12. Elliptic curve isogenies
    13. Mestre's algorithm for constructing hyperelliptic curves from their invariants
    14. Tate's Algorithm over function fields
    15. Fix some memory leak that was found using elliptic curves
    16. Implement finite algebras
    17. Things related to PARI/GP

Put flint2 into Sage

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

Help the Singular developers make better use of flint2

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:

To replace NTL completely, we need:

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

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

Linear algebra over GF(pk) can be reduced to linear algebra over GF(p) and for GF(2k) 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

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

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

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

Modular forms code in Sage

Open MP and FLINT

Miscellaneous Sage Algebra and Number Theory patches

Simon and ComputeL GP scripts

Elliptic curve isogenies

Mestre's algorithm for constructing hyperelliptic curves from their invariants

Tate's Algorithm over function fields

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

Fix some memory leak that was found using elliptic curves

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

The trac ticket for this is 12141.

SageFlintDays/projects (last edited 2012-02-06 10:39:37 by mstreng)