Differences between revisions 1 and 17 (spanning 16 versions)
Revision 1 as of 2009-06-20 15:18:39
Size: 348
Editor: was
Comment:
Revision 17 as of 2009-06-22 16:46:05
Size: 4293
Editor: was
Comment:
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
== Implement evaluation of elliptic curve isomorphism at a point ==

PEOPLE: William Stein

{{{
sage: E = EllipticCurve('37a'); F = E.quadratic_twist(-17)
sage: K.<a> = QuadraticField(-17); E = E.change_ring(K); F = F.change_ring(K)
sage: phi = E.isomorphism_to(F); phi(E.gens()[0])
Traceback (click to the left for traceback)
...
NotImplementedError: not implemented.
}}}
Line 6: Line 18:
PEOPLE: William Stein
Line 7: Line 21:

== Create elliptic curve classes for elliptic curve models in the Explicit-Formulas Database ==

PEOPLE: David Kohel

  In order to optimize and compare arithmetic, we should first implement alternative models and verify relative performance. The isomorphisms between different models should also be implemented, and classes for isogenies of these models developed, making use first of the new isogenies code, and eventually putting in place special optimized code for specific models.

See the EFD: http://www.hyperelliptic.org/EFD/

== Rewrite abelian groups (hard) ==

PEOPLE: William Stein

  It would be possible to use [[http://trac.sagemath.org/sage_trac/ticket/5882|trac 5882]] to rewrite abelian groups natively in Sage (not using GAP), in a way that is much more flexible than the current implementation. This could be useful for many number theory applications.

  This project is "hard", since many have tried and always failed.

  [[/abgrp|More Details]]

== Optimize/better document/generally improve graph theory library in Sage ==

PEOPLE: Robert Miller

  Ticket [[http://trac.sagemath.org/sage_trac/ticket/6085|#6085]] contains a lot of work so that a graph created by Graph(implementation='c_graph') is just as functional as a Sage graph. I will be sporadically working on improving documentation and optimizing graphs all week, and anyone interested is welcome to join.

== Cliquer SPKG for Sage ==

PEOPLE: Robert Miller, Nathann Cohen (remotely)

 * [[http://trac.sagemath.org/sage_trac/ticket/6355|#6355]]
  * [[http://trac.sagemath.org/sage_trac/ticket/5793|#5793]]
  * [[http://trac.sagemath.org/sage_trac/ticket/5669|#5669]]

== Take a look at the possibility of making GAP a dynamically loadable library ==

PEOPLE: Robert Miller, Martin Albrecht (hopefully)

== Python implementation of Ford-Fulkerson algorithm ==

PEOPLE: Robert Miller

I plan on at least copying the Python implementation on wikipedia, since now we have nothing at all for max flow problems. Hopefully then someone who really cares about it will try to use it, realize it is slow, start improving it, etc. etc. etc.

 * http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm

== Frobenius number and genus of numerical semigroups using toric Grobner bases ==

PEOPLE: Bjarke Hammersholt Roune

  I plan to code Frobenius number (largest gap) and genus (number of gaps) functions for numerical semigrups using two related algorithms based on toric ideals. These algorithms can handle random numerical semigroups generated by numbers with thousands of digits, as long as there are not too many minimal generators. I'm happy to explain either algorithm if you want to help or are just curious. The steps needed are these:

   * Find the best way to compute toric Grobner bases in Sage (4ti2?)
   * Improve the integration of the library Frobby for monomial ideal computations.
   * Code the algorithms (should be easy at this point)

  Help is welcome, especially for writing a Cython interface to Frobby.

== PolyBoRi and Singular ==

PEOPLE: Martin Albrecht

Both PolyBoRi's (Gröbner bases in GF(2)[x_i]/<x_i^2+x_i>) and Singular's interface need some (engineering) work & documentation.

== Elliptic curves isogenies -- greatly improve usability ==

PEOPLE: William Stein

Dan Shumow wrote new code for computing isogenies between elliptic curves, but it is still very rough around the edges. Fix it up. See e.g., http://trac.sagemath.org/sage_trac/ticket/6384

Sage Days 16 Project Idea Page

Implement evaluation of elliptic curve isomorphism at a point

PEOPLE: William Stein

sage: E = EllipticCurve('37a'); F = E.quadratic_twist(-17)
sage: K.<a> = QuadraticField(-17); E = E.change_ring(K); F = F.change_ring(K)
sage: phi = E.isomorphism_to(F); phi(E.gens()[0])
Traceback (click to the left for traceback)
...
NotImplementedError: not implemented.

Create a Cython class for points on elliptic curves and optimize basic arithmetic

PEOPLE: William Stein

  • Right now basic arithmetic on elliptic curves is way too slow. It could be sped up by moving the point class to Cython, and possibly by using better formulas for arithmetic, e.g., using projective coordinates.

Create elliptic curve classes for elliptic curve models in the Explicit-Formulas Database

PEOPLE: David Kohel

  • In order to optimize and compare arithmetic, we should first implement alternative models and verify relative performance. The isomorphisms between different models should also be implemented, and classes for isogenies of these models developed, making use first of the new isogenies code, and eventually putting in place special optimized code for specific models.

See the EFD: http://www.hyperelliptic.org/EFD/

Rewrite abelian groups (hard)

PEOPLE: William Stein

  • It would be possible to use trac 5882 to rewrite abelian groups natively in Sage (not using GAP), in a way that is much more flexible than the current implementation. This could be useful for many number theory applications. This project is "hard", since many have tried and always failed.

    More Details

Optimize/better document/generally improve graph theory library in Sage

PEOPLE: Robert Miller

  • Ticket #6085 contains a lot of work so that a graph created by Graph(implementation='c_graph') is just as functional as a Sage graph. I will be sporadically working on improving documentation and optimizing graphs all week, and anyone interested is welcome to join.

Cliquer SPKG for Sage

PEOPLE: Robert Miller, Nathann Cohen (remotely)

Take a look at the possibility of making GAP a dynamically loadable library

PEOPLE: Robert Miller, Martin Albrecht (hopefully)

Python implementation of Ford-Fulkerson algorithm

PEOPLE: Robert Miller

I plan on at least copying the Python implementation on wikipedia, since now we have nothing at all for max flow problems. Hopefully then someone who really cares about it will try to use it, realize it is slow, start improving it, etc. etc. etc.

Frobenius number and genus of numerical semigroups using toric Grobner bases

PEOPLE: Bjarke Hammersholt Roune

  • I plan to code Frobenius number (largest gap) and genus (number of gaps) functions for numerical semigrups using two related algorithms based on toric ideals. These algorithms can handle random numerical semigroups generated by numbers with thousands of digits, as long as there are not too many minimal generators. I'm happy to explain either algorithm if you want to help or are just curious. The steps needed are these:
    • Find the best way to compute toric Grobner bases in Sage (4ti2?)
    • Improve the integration of the library Frobby for monomial ideal computations.
    • Code the algorithms (should be easy at this point)
    Help is welcome, especially for writing a Cython interface to Frobby.

PolyBoRi and Singular

PEOPLE: Martin Albrecht

Both PolyBoRi's (Gröbner bases in GF(2)[x_i]/<x_i^2+x_i>) and Singular's interface need some (engineering) work & documentation.

Elliptic curves isogenies -- greatly improve usability

PEOPLE: William Stein

Dan Shumow wrote new code for computing isogenies between elliptic curves, but it is still very rough around the edges. Fix it up. See e.g., http://trac.sagemath.org/sage_trac/ticket/6384

days16/projects (last edited 2009-06-27 14:41:17 by BurcinErocal)