GSoC 2017 kickoff

[Harald Schilly]

Hello, this year's Google Summer of Code 2017 just started.

I assume we will try again to be part of it, and therefore I've
started the registration process.

The most important aspect is to have mentors and project proposals.
For that, I've started this year's wiki page as a copy of last year:

https://wiki.sagemath.org/GSoC/2017 (compare with 2016)

The deadline for the application is Feb. 9th and I'm again working on
this like in the past 5 years.

-- Harald

[Johan S. H. Rosenkilde]

Hi sage-devel,

Our current polynomial implementation has severe issues:

- Our speed for GF(2^e)[x] is abysmal.

- For other cases we are probably not linking to the currently fastest
libraries.

- We don't have multi-point evaluation or fast Lagrange interpolation,
even though the libraries we link to often have this.

- Bruno Grenet remarked at SD75 that there were issues and lots of
crufted code in the class structure handling generic/specific and
dense/sparse/etc. polynomials.

- Jeroen Demeyer remarked that the Cython code is from the prehistoric
era and has lots of cruft from back when Cython was a lot more
primitive than it is now.

- add more things yourself.

Considering how central polynomial arithmetic is in many parts of
algebra, I think this is bad, and it impedes gradual improvement (e.g. I
am at a loss on how to improve the GF(2^e)[x] thing which is my personal
main itch).

I would be interested in co-mentoring such a GSoC project for improving
this. But I lack understanding of, especially Cython and linking. I
would like to know if someone else would be a co-mentor with me on this,
or technical advisor on e.g. Cython issues.

Best,
Johan

--

[Jean-Pierre Flori]

I would be very interested in working on this.

[Peter Bruin]

Hello,

Johan S. H. Rosenkilde <mail...@atuin.dk> wrote:

> Our current polynomial implementation has severe issues:
>
> - Our speed for GF(2^e)[x] is abysmal.
>
> - For other cases we are probably not linking to the currently fastest
> libraries.
>
> - We don't have multi-point evaluation or fast Lagrange interpolation,
> even though the libraries we link to often have this.
>
> - Bruno Grenet remarked at SD75 that there were issues and lots of
> crufted code in the class structure handling generic/specific and
> dense/sparse/etc. polynomials.
>
> - Jeroen Demeyer remarked that the Cython code is from the prehistoric
> era and has lots of cruft from back when Cython was a lot more
> primitive than it is now.
>
> - add more things yourself.
>
> Considering how central polynomial arithmetic is in many parts of
> algebra, I think this is bad, and it impedes gradual improvement (e.g. I
> am at a loss on how to improve the GF(2^e)[x] thing which is my personal
> main itch).
>
> I would be interested in co-mentoring such a GSoC project for improving
> this. But I lack understanding of, especially Cython and linking. I
> would like to know if someone else would be a co-mentor with me on this,
> or technical advisor on e.g. Cython issues.

It would indeed be a big step forward to improve polynomial arithmetic.
A long time ago I wrote an implementation of power series using PARI:
https://trac.sagemath.org/ticket/15601
This is not merged yet, but could be useful to get an impression of the
sort and amount of work to be done for new polynomial implementations
(although the interfaces of e.g. NTL and FLINT are of course different).
Unfortunately I personally won't have a lot of free time to help with a
GSoC project...

Peter

[mmarco]

I am not sure I will have time to be a mentor this year, but I would like to propose porting rubi to sage:

http://www.apmaths.uwo.ca/~arich/

It is a series of rules (over 6000) to be applied to symbolic expressions in order to get their primitive. The results they produce are better than the Mathematica builtin integrator, they succeed in a bigger number of cases, and they also hapen to be faster. If we could include that in Sage that would be a killer feature.

Right now the rules are written in Mathematica language, and translating them by hand would be too much work for a person to do in a few months. So likely the best approach is to try and write a parser that could do it automatically. 

I have talked to one of the authors in person during a conference, and he really liked the idea of seeing it ported to a free system. In fact I thing that there have already been some discussion about this in maxima and sympy (maybe we could cooperate in this effort).

[Ralf Stephan]

On Friday, January 20, 2017 at 8:40:06 PM UTC+1, mmarco wrote:

I am not sure I will have time to be a mentor this year, but I would like to propose porting rubi to sage:

The main tasks would be:

1. implement missing symbolic functions (Meijer-G, Appell, etc.)

2. convert the ruleset to an efficient algorithm that minimizes pattern matchings

The initial implementation could be in Python. I can help with (or even

take over) #1 but I'm not available as mentor. As to #2 the rubi author

apparently stated that he would develop a decision tree in version 5.

One would have to contact the author to check his progress.

The beauty of the task is that any part of it would be useful, i.e., it can be

fully done incrementally. Part 1 Algebraic for example would need the symbolic

AppellF1 function because it can result from the integrals

integrate((a+b*x)^m * (c+d*x)^n * (e+f*x)^p, x)
integrate((a+b*x)^m * (c+d*x^2)^n, x)
integrate((a+b*x)^m * (c+d*x^p)^q, x)

Any other symbolic function needed for Part 1 already exists in Sage.

Incidentally, does anyone know how to efficiently compute AppellF1 numerically?

Regards,

[Johan S. H. Rosenkilde]

Jean-Pierre Flori writes:
>>
>> I would be very interested in working on this.

Cool :-) Let's discuss the project description off the mailing list.


Also, thanks Peter for your input. We should definitely take a closer
look at #15601.

Best,
Johan

[Harald Schilly]

Hello, in 3 days is the deadline regarding the project application.
I'm working on the application itself, but a list of suggested
projects is *vital* to getting approval. I saw a few ideas here, but
so far not a single proposal was added to

https://wiki.sagemath.org/GSoC/2017

Please compare it with the 2016 page, i.e. at minimum there should be

* title
* mentor(s) (with contact info)
* technical and theoretical scope
* short description

-- harald

[Johan S. H. Rosenkilde]

Hi Harald,

Thanks for yelling out. I've added the polynomial class project that
I mentioned on the list earlier. But 1 project is surely not enough...

Best,
Johan

Harald Schilly writes:

--

[Dima Pasechnik]

I can add (and volunteer to mentor) a project to develop an implementation of graph modular decomposition (which is very broken in Sage, and no 3rd party implementations are suitable for interfacing)

[Travis Scrimshaw]

I added two projects with the somewhat broad subject areas:

- Improve the representation theory in Sage
- Improve the root system code in Sage

[Travis Scrimshaw]

I added another one for quantum cluster algebras (based on a suggestion from Gregg Musiker).

Best,
Travis

[Dima Pasechnik]

I've added a project on modular decomposition of graphs and digraphs.

How many more we would like to have?

[mmarco]

I don't plan to have much time available to mentor, but I think the project of porting rubi to sage would be doable. Someone wants to step in as a co-mentor?

I have done some playing around with a few sample rules, and got a proof of concept. It doesn't really work, but it pretty much shows that the task is  doable.

I attach a .ipynb with my toy proof of concept.

[Ralf Stephan]

On Tuesday, February 7, 2017 at 11:13:40 PM UTC+1, mmarco wrote:

I don't plan to have much time available to mentor, but I think the project of porting rubi to sage would be doable. Someone wants to step in as a co-mentor?

No GSoC commitment from me but a support statement.

[David Coudert]

That's clearly something we need.
If the student is good and fast, (s)he can also try to implement the split-decomposition which is a generalization of modular decomposition that can be computed in linear time (roughly finds complete bipartite graph separators).

Also, we could consider adding efficient implementations of several graph-traversals like LexBFS.

David.

[Dima Pasechnik]

On Wednesday, February 8, 2017 at 11:03:57 AM UTC, David Coudert wrote:

That's clearly something we need.
If the student is good and fast, (s)he can also try to implement the split-decomposition which is a generalization of modular decomposition that can be computed in linear time (roughly finds complete bipartite graph separators).

Also, we could consider adding efficient implementations of several graph-traversals like LexBFS.

OK, I've added these too.

[Jakob Kroeker]

I have an idea for a project but no time this year for mentoring (maybe next one)

The idea boils down to develop a random testing framework to find (in some way minimal) failing examples (wrong answers or crashes)
using bots (like running patchbot to test sage).

So if someone is willing, able and capable to take over this project, just do it

Jakob