Report on global function fields in Sage

[Kwankyu Lee]

Dear Sage developer community,

As of Sage 8.8.beta4, the global function field code of the ticket #22982 has finally landed all in Sage. Following the tradition of giving a report when a major piece of new functionality is added to Sage, I will now briefly recall what we achieved and thank the people who contributed to it.

During my sabbatical year spanning from 2016 to 2017, I wrote the initial code for computations with global function fields. This was what I had wanted to do all the time since I realized Magma is not a suitable platform for distributing my research work in algorithmic coding theory. So I decided to devote the sabbatical year for the mission. I thank Maria Bras-Amoros for hosting me during the year and for putting up with me, as a side effect,  neglecting the duty of collaborating with her for mathematical research.   

In 2017, I created the ticket #22982 and pushed the whole code. The code was just sitting there for long time waiting for a reviewer, until Johan came up and gave advices on what I should do if I wanted the monstrously big code ever get reviewed. I thank Johan for the valuable advices.

Following Johan's advice, I split the code into pieces and created several child tickets. Then finally a little more than a year ago, Travis showed up and started reviewing the tickets. During this process, he gave lots of useful comments on the code and elevated the quality of the code substantially. He is a great reviewer. I thank him very much!

And now here is the global function field machinery in your Sage. What is to do with it?

1. It is very, but not terribly, slow compared with Magma. One may want to improve the speed.

2. One may want to extend the code for function fields over other fields than finite fields. I myself do not have a plan to do this.

3. I am writing code for computations with integral curves over finite fields using the global function field machinery.

4. I wrote code (this is what I dreamed of since I first heard of Sage in 2006)  for my decoding algorithm for AG codes using the global function field machinery. I am supposed to give a short talk on this topic at SIAM 2019 in July.

This is it. Thank you for your attention!

Kwankyu

[Simon King]

Dear Kwankyu,

thank you for your contribution and your report!

On 2019-05-10, Kwankyu Lee <ekwa...@gmail.com> wrote:
> 1. It is very, but not terribly, slow compared with Magma. One may want to
> improve the speed.

Is there a ticket for it, which also points out what examples are slow and
how it compares with Magma? I cannot give a promise at this point, but
generally I like to try and tweak code.

Best regards,
Simon

[Kwankyu Lee]

On Friday, May 10, 2019 at 4:04:15 PM UTC+9, Simon King wrote:

On 2019-05-10, Kwankyu Lee <ekwa...@gmail.com> wrote:
> 1. It is very, but not terribly, slow compared with Magma. One may want to
> improve the speed.

Is there a ticket for it, which also points out what examples are slow and
how it compares with Magma? I cannot give a promise at this point, but
generally I like to try and tweak code.

Hi Simon, 

I meant the general performance. So any computation is slower than with Magma :-) For example, on my desktop,

-----------------------------

sage: k.<a> = GF(16)

sage: K.<x> = FunctionField(k); _.<Y> = K[]

sage: L.<y> = K.extension(Y^4 + Y - x^5)

sage: time L.genus() 

CPU times: user 1.33 s, sys: 79 ms, total: 1.41 s

Wall time: 1.35 s

6

-----------------------------

versus

-----------------------------

> K<x> := FunctionField(GF(16));

> R<t> := PolynomialRing(K);

> L<y> := ext<K|t^4 + t - x^5>;

> time Genus(L);

6

Time: 0.010

-----------------------------

There is no ticket. It seems bad to create a ticket before you have a specific goal and a means to achieve it. 

I suspect that the overall poor performance is mainly due to slow linear algebra over polynomial rings (over finite fields). For example, I observed determinant computation is generally slow and for some cases terribly slow. At the base, there is hermite normal form computation. Any speed increase in the computation would improve the overall performance of the global function field machinery.

One may target specific methods. Of course, I did try to optimize each method as much as I could. But others may come up with better idea or even faster algorithm.

[Simon King]

Hi Kwankyu,

On 2019-05-10, Kwankyu Lee <ekwa...@gmail.com> wrote:
> There is no ticket. It seems bad to create a ticket before you have a
> specific goal and a means to achieve it.

Why? You have specific examples. That should be enough for a ticket,
IMHO. If while working on the ticket it turns out that the slowness has
several distinct reasons, one can make it a meta-ticket and create
several smaller tickets, each addressing one issue.

>
> I suspect that the overall poor performance is mainly due to slow linear
> algebra over polynomial rings (over finite fields). For example, I observed
> determinant computation is generally slow and for some cases terribly slow.

That's something one could start with...

Best regards,
Simon