Differences between revisions 59 and 60
Revision 59 as of 2011-12-19 12:16:29
Size: 8878
Editor: johanbosman
Comment:
Revision 60 as of 2011-12-19 12:18:57
Size: 9248
Editor: MvanBeek
Comment:
Deletions are marked like this. Additions are marked like this.
Line 160: Line 160:
    * http://trac.sagemath.org/sage_trac/ticket/12186 (needs review)
    * http://trac.sagemath.org/sage_trac/ticket/12179 (needs uploading!)
    * http://trac.sagemath.org/sage_trac/ticket/12183 (positive review)


---- /!\ '''Edit conflict - other version:''' ----
Line 161: Line 167:

---- /!\ '''Edit conflict - your version:''' ----

---- /!\ '''End of edit conflict''' ----

Projects

Please feel free to add more

Put flint2 into Sage

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.

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.

#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(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

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 positivly)

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

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

    • #10658: Martin R and Frithjof will have a look at this (needs work by David)

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

Open MP and FLINT

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

Miscellaneous Sage Algebra and Number Theory patches


/!\ Edit conflict - other version:



/!\ Edit conflict - your version:



/!\ End of edit conflict


Simon and ComputeL GP scripts

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 ticket: http://trac.sagemath.org/sage_trac/ticket/6341.

  • Florian has code for Mestre's algorithm, make this into a patch
  • Florian has code for the covariant z_0, put that in the same patch
  • The two above has been put in a patch on #6341. Needs reviewing
  • Code for covariant z is not written, write that (optional), reference for the invariant: http://www.warwick.ac.uk/~masgaj/papers/redp1.pdf

  • Reduction of points for SL_2 is also needed. It is
    • easy for QQ, put that in the patch as well
    • very interesting for number fields: Hilbert fundamental domain, bad code that works surprisingly well (Marco), improve that (optional)

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.

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