GSoC 2017 kickoff

287 views
Skip to first unread message

Harald Schilly

unread,
Jan 19, 2017, 1:05:19 PM1/19/17
to sage-...@googlegroups.com, sage-gso...@googlegroups.com
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

unread,
Jan 20, 2017, 5:03:52 AM1/20/17
to sage-...@googlegroups.com
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

unread,
Jan 20, 2017, 5:29:15 AM1/20/17
to sage-devel, mail...@atuin.dk
I would be very interested in working on this.

Peter Bruin

unread,
Jan 20, 2017, 12:05:19 PM1/20/17
to sage-...@googlegroups.com
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

unread,
Jan 20, 2017, 2:40:06 PM1/20/17
to sage-devel, sage-gso...@googlegroups.com
I am not sure I will have time to be a mentor this year, but I would like to propose porting rubi to sage:


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

unread,
Jan 21, 2017, 2:27:50 AM1/21/17
to sage-devel, sage-gso...@googlegroups.com
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

unread,
Jan 21, 2017, 9:51:43 AM1/21/17
to Jean-Pierre Flori, sage-devel
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

unread,
Feb 6, 2017, 7:42:49 AM2/6/17
to sage-...@googlegroups.com, sage-gso...@googlegroups.com
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

unread,
Feb 6, 2017, 8:23:08 AM2/6/17
to sage-...@googlegroups.com, sage-gso...@googlegroups.com
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

unread,
Feb 6, 2017, 12:33:10 PM2/6/17
to sage-devel
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

unread,
Feb 7, 2017, 10:33:22 AM2/7/17
to sage-devel
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

unread,
Feb 7, 2017, 10:57:51 AM2/7/17
to sage-devel
I added another one for quantum cluster algebras (based on a suggestion from Gregg Musiker).

Best,
Travis

Dima Pasechnik

unread,
Feb 7, 2017, 1:14:20 PM2/7/17
to sage-devel, sage-gso...@googlegroups.com
I've added a project on modular decomposition of graphs and digraphs.

How many more we would like to have?

mmarco

unread,
Feb 7, 2017, 5:13:40 PM2/7/17
to sage-devel, sage-gso...@googlegroups.com
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.
Rubi.ipynb
rule3.8.nb

Ralf Stephan

unread,
Feb 8, 2017, 2:11:05 AM2/8/17
to sage-devel, sage-gso...@googlegroups.com
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

unread,
Feb 8, 2017, 6:03:57 AM2/8/17
to sage-devel, sage-gso...@googlegroups.com
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

unread,
Feb 8, 2017, 7:20:20 AM2/8/17
to sage-devel, sage-gso...@googlegroups.com


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

unread,
Feb 8, 2017, 7:34:32 AM2/8/17
to sage-devel
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
Reply all
Reply to author
Forward
0 new messages