Size: 3637
Comment:
|
Size: 14183
Comment:
|
Deletions are marked like this. | Additions are marked like this. |
Line 3: | Line 3: |
Please feel free to add more | * [[http://trac.sagemath.org/sage_trac/query?status=closed&status=positive_review&order=priority&col=id&col=summary&col=status&col=type&col=priority&col=milestone&col=component&keywords=~sd35 | Here]] is an up-to-date list of finished tickets that were worked on at this Sage Days workshop. * [[http://trac.sagemath.org/sage_trac/query?status=needs_info&status=needs_review&status=needs_work&status=new&order=priority&col=id&col=summary&col=status&col=type&col=priority&col=milestone&col=component&keywords=~sd35 | Here]] is an up-to-date list of tickets that were worked on at this Sage Days workshop and that are still being worked on. |
Line 12: | Line 16: |
* Update MPFR to 3.1.0 - http://trac.sagemath.org/sage_trac/ticket/11666 (Mike Hansen) * Update MPFI to 1.5.0 - http://trac.sagemath.org/sage_trac/ticket/12171 (Mike Hansen) == Switch some of the mwrank code to use flint2 == |
* 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 == |
Line 22: | Line 39: |
* 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! |
|
Line 24: | Line 43: |
* People: Martin L., Simon K., Flint developers == Linear algebra mod p, for log_2 p = 64 == |
* 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. |
Line 31: | Line 68: |
'''Update (2011-12-20 11:10):''' Okay, project cancelled, none of the tricks I could think of make sense. |
|
Line 77: | Line 116: |
Gives a ratio of about 4.5. | 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. |
Line 81: | Line 120: |
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. | * 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 [[http://trac.sagemath.org/sage_trac/ticket/12177|#12177]] * [[http://trac.sagemath.org/sage_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 }}} |
Line 85: | Line 146: |
At !AsiaCrypt 2011 Chen and Nguyen [[http://www.springerlink.com/content/m036804m1m538722/ |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 [[http://www.springerlink.com/content/x3l7g80454x11116/ |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 prunning and/or to port it to Flint2? | * People: Martin A., Andy N. At !AsiaCrypt 2011 Chen and Nguyen [[http://www.springerlink.com/content/m036804m1m538722/ |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 [[http://www.springerlink.com/content/x3l7g80454x11116/ |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? |
Line 88: | Line 151: |
* People: Fredrik J., Andy N., David H. |
|
Line 94: | Line 159: |
== Modular forms code in Sage == * People: David L., John C., Jan V., Frithjof, Johan B., Maarten D., Martin R., Simon K. * review patches * [[http://trac.sagemath.org/sage_trac/ticket/5048|#5048]]: Johan B. has done this one. (reviewed positivly) * [[http://trac.sagemath.org/sage_trac/ticket/11601|#11601]]: depends on #5048; now rebased; Johan working on this. Done. (reviewed positively) * [[http://trac.sagemath.org/sage_trac/ticket/10546|#10546]]: depends on #11601; Jan V to take a look (reviewed positively) * [[http://trac.sagemath.org/sage_trac/ticket/12043|#12043]]: DL to work on this (needs work) * [[http://trac.sagemath.org/sage_trac/ticket/10658|#10658]]: Martin R and Frithjof will have a look at this (reviewed positively) * [[http://trac.sagemath.org/sage_trac/ticket/12124|#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 [[http://trac.sagemath.org/sage_trac/ticket/12132|#12132]]. * Implement the upper half plane: [[http://trac.sagemath.org/sage_trac/ticket/9439|#9439]] * Add a LLL for matrices over QQ and RR: [[http://trac.sagemath.org/sage_trac/ticket/12051|#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: * [[http://trac.sagemath.org/sage_trac/ticket/11235|#11235]] Make the ipython edit magic command edit the right file and show both files when doing "??" * [[http://trac.sagemath.org/sage_trac/ticket/11319|#11319]] Cannot create homomorphism from prime residue field to finite field * [[http://trac.sagemath.org/sage_trac/ticket/11417|#11417]] binomial of polynomial is not polynomial * [[http://trac.sagemath.org/sage_trac/ticket/11673|#11673]] is_unit not properly implemented for algebraic integers * [[http://trac.sagemath.org/sage_trac/ticket/11838|#11838]] Multivariate factorization over non-prime finite fields hangs * [[http://trac.sagemath.org/sage_trac/ticket/12156|#12156]] Pretty print LatexExpr directly * [[http://trac.sagemath.org/sage_trac/ticket/12176|#12176]] Compute Minkowski bound for relative number fields * [[http://trac.sagemath.org/sage_trac/ticket/12182|#12182]] Calculate the trace dual of an order in a number field * [[http://trac.sagemath.org/sage_trac/ticket/12183|#12183]] Absolute and relative norm functions for number field elements * [[http://trac.sagemath.org/sage_trac/ticket/12185|#12185]] Bug in norm for orders of relative number fields * [[http://trac.sagemath.org/sage_trac/ticket/12191|#12191]] is_squarefree for integer polynomials * [[http://trac.sagemath.org/sage_trac/ticket/12196|#12196]] Improve latex for quadratic fields * [[http://trac.sagemath.org/sage_trac/ticket/12210|#12210]] GF(p) constructor should check primality of p only once * [[http://trac.sagemath.org/sage_trac/ticket/12218|#12218]] Content of general polynomial * Patches needing review: * [[http://trac.sagemath.org/sage_trac/ticket/11930|#11930]] Disallow non-smooth hyperelliptic curves, and let hyperelliptic curves know they are not singular (needs review!) * Patches needing work or info: * [[http://trac.sagemath.org/sage_trac/ticket/4283|#4283]] A Speed-up Patch for NTL's ZZXFactoring.c (needs work) * [[http://trac.sagemath.org/sage_trac/ticket/12179|#12179]] Binomial of integer (mod n) returns integer (needs work) * [[http://trac.sagemath.org/sage_trac/ticket/12186|#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: * [[http://trac.sagemath.org/sage_trac/ticket/6341|#6341]] (needs work) contains Florian's code for * Mestre's algorithm * The covariant z_0 * SL2(ZZ)-reduction * [[http://trac.sagemath.org/sage_trac/ticket/12199|#12199]] (new) case of curves with automorphisms * [[http://trac.sagemath.org/sage_trac/ticket/12200|#12200]] (new) case of characteristic two (and three, and five) * [[http://trac.sagemath.org/sage_trac/ticket/12204|#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., Julian R. There is a Magma implementation based on John's number field implementation [[http://www.maths.nottingham.ac.uk/personal/cw/algorithms.html|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. '''[[http://trac.sagemath.org/sage_trac/ticket/11521|#11521]] needs review!''' The topic is also related with [[http://trac.sagemath.org/sage_trac/ticket/715|#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 [[http://trac.sagemath.org/sage_trac/ticket/12141|12141]]. == Things related to PARI/GP == * People: Jeroen D. * [[http://trac.sagemath.org/sage_trac/ticket/12203|#12203]]: Implement is_PariGpElement * [[http://trac.sagemath.org/sage_trac/ticket/12158|#12158]]: Segfault in PARI's err_init() during pari_init_opts(): '''closed (fixed)''' * [[http://trac.sagemath.org/sage_trac/ticket/9948|#9948]]: Conversion between p-adics and PARI/GP |
Projects
Here is an up-to-date list of finished tickets that were worked on at this Sage Days workshop.
Here is an up-to-date list of tickets that were worked on at this Sage Days workshop and that are still being worked on.
Contents
-
Projects
- 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
- --(Linear algebra mod p, for log_2 p = 64)--
- Linear algebra mod p^n, for log_2 p small-ish
- BKZ 2.0
- Improve polynomial factoring mod p in flint2
- 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
- Fix some memory leak that was found using elliptic curves
- Implement finite algebras
- Things related to PARI/GP
Put flint2 into Sage
- People: Bill H., Mike H., Fredrik J., Andy N., Sebastian P.
- Building flint2 in Sage
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)
Update MPFI to 1.5.0 - http://trac.sagemath.org/sage_trac/ticket/12171
Reinstall http://sagemath.org/packages/standard/libfplll-3.0.12.p1.spkg
- Install flint2 spkg (beware, this will break Sage)
- touch SAGE_ROOT/devel/sage/sage/combinat/partitions.*
- 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(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
#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 work)
#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.
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:
#11235 Make the ipython edit magic command edit the right file and show both files when doing "??"
#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
#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:
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., 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(): closed (fixed)
#9948: Conversion between p-adics and PARI/GP