SageMath GSoC 2018 Projects

We're happy to announce our list of Google Summer of Code projects for 2018! Thank you to everyone involved, all students, mentors and of course, Google! 


Sai Harsh Tondomker (David Coudert and Dima Pasechnik):

Addition of SPQR-tree to graph module

In this project, our goal is to extend the graph theory library in Sage by implementing functionality to find triconnected subgraphs, which will partition an undirected graph into 3-connected components and the construction of the corresponding SPQR-tree. These modules can later be used as pre-processing for several graph problems such as Hamiltonian Cycle, traveling salesman problem.



Meghana M Reddy (David Coudert and Dima Pasechnik):

Addition of SPQR-trees to the graph module of Sage Math

The aim of the project is to code the linear time algorithm for partitioning a graph into 3-connected components and constructing the corresponding SPQR-tree of the graph. Further, this algorithm can be used as a subroutine for several other graph problems such as recognition of chordless graphs, hamiltonian cycle etc.



Filip Ion (Johan Rosenkilde):

Databases and bounds of codes

The following proposal detail some possible improvements of the coding theory component of SageMath. We aim to build databases of precomputed bounds and optimal examples of linear codes for each choice of parameters below a maximum range.



Raghukul Raman (Travis Scrimshaw and Benjamin Hutz):

Rational Point on Varieties

This project aims at implementing basic algorithms for finding rational points on varieties. Classically algebraic variety is defined as the set of solutions of polynomial equations over a number field. A rational point of an algebraic variety is a solution of set of equations in the given field (rational field if not mentioned). Much of the number theory can be viewed as the study of rational point of algebraic varieties. Some of the great achievements of number theory amount to determining the rational points on particular curves. For example, Fermat’s last theorem is equivalent to the statement that for an integer n ≥ 3, the only rational point of the curve xn+yn=zn in P2 over Qare the obvious ones. Common variants of these question include determining the set of all points of V(K) of height up to some bound. The aim of this project is to implement some basic rational point finding algorithms (sieving modulo prime and enumeration) and extend these to product_projective_space scheme.



Dario Asprone (Dima Pasechnik)

Checking graph isomorphism using the Weisfeiler-Lehman algorithm

Currently SageMath checks for graph isomorphism through an internal package with a corresponding method, called isomorphic and contained in sage.groups.perm_gps.partn_ref.refinement_graphs. This method, in addition to being quite convoluted and without much documentation about its inner workings, was last updated in a significant manner in 2011.
The project aims at creating a new package which implements an efficient in practice heuristic method to check if two graphs are isomorphic, using one of the members of the Weisfeiler-Lehman (WL) algorithm hierarchy. An attempt was made in the past at the same task (but with a narrower scope, limited to only implementing the second order version of the WL algorithm), but the code was found to contain a bug and was never implemented/removed from the codebase (see Trac #10482).
To the best of my knowledge, this would be the first working open-source implementation of k-WL, for k > 1.

SageMath GSoC 2017 Projects

6 GSoC SageMath Projects

During the past couple of summers, SageMath successfully managed many Google Summer of Code projects. This year we are again happy to have six projects:

Implementing matroid classes and plotting improvements

(Zachary Gershkoff / Stefan van Zwam)

This project seeks to implement several common matroid classes in SageMath, along with algorithms for their display and relevant computations. The graphic matroid class in particular will be implemented with a representative graph with methods for Whitney switching and minor operations. This will be accompanied by improvements to the graph theory library, with methods relevant to matroids enabled to support multigraphs. Other modules for this project include improved plotting of rank 3 matroids to eliminate false colinearities, computation of a matroid's automorphism group using SageMath's group theory libraries, and faster minor testing based on an existing trac ticket.

Expanding the Functionality of Dynamical Systems

(Rebecca Lauren Miller / Paul Fili and Ben Hutz)

As a member of the sage-dynamics community, researchers have compiled a wishlist for algorithms and functionality they would like added. I would like to shorten the wish list for us.For my project I will be completing some desired additions to SAGE from the Sage Dynamics Wiki. I will implement Well’s Algorithm, strengthen the numerical precision in cannonical_height, as well as implement reduced_form for higher dimensions.

Improvement of Complex Dynamics in Sage

(Ben Barros / Adam Towsley and Ben Hutz)

There are three major things that I would like to implement to improve the functionality of Sage in the area Complex Dynamics. The details of the project are summarized in the following list:

• Complex Dynamics Graphical package: Integrate or implement a complex dynamics software such as Mandel into Sage. This will be done by creating an optional package for Sage. If there is enough demand, the package may become a standard package for Sage at some point.

• Spider Algorithm: The object of the Spider Algorithm is to construct polynomials with assigned combinatorics. For example, we may want to find a polynomial that has a periodic orbit of period 7. The Spider Algorithm provides a way for us to compute this polynomial efficiently. I plan to implement this algorithm into Sage.

• Coercion: If you have a map defined over Q, you should be able to take the image of a point over C (i.e. somewhere you have a well-defined embedding) without having to use the command "change_ring()". Something similar works for polynomials in Sage but it does not work for morphisms/schemes.

Linear-time Implementation of Modular Decomposition of Undirected and Directed Graphs

(Lokesh Jain / Dima Pasechnik)

This project is aimed at providing linear time implementation for modular decomposition of graphs and digraphs. Modular decomposition is decomposition of graph into modules. A module is a subset of vertices and it is a generalization of connected component in graph. Let us take for example a module X. For any vertex v ∉ X it is either connected or not connected to every vertex of X. Another property of module is that a module can be subset of another module. There are various algorithms which have been published for modular decomposition of graphs. The focus in this project is on linear time complexity algorithms which can be practically implemented. The project further aims to use the modules developed for modular decomposition to implement other functionality like skew partitions. Skew partition is partition of graph into two sets of vertices such that induced graph formed by one set is disconnected and induced graph formed by other set is complement of the first. Modular decomposition is a very important concept in Graph Theory and it has a number of use cases. For instance it has been an important tool for solving optimization and combinatorics problems.

Modular Decomposition of graphs and digraphs

(Maria Ioanna Spyrakoy / Dima Pasechnik)

Modular decomposition of (di)graphs is a generalization of the concept of the decomposition of (di)graphs into connected components. Its current implementation in Sage relies on badly broken abandoned C code, and badly needs to be replaced by something that works and is not too slow. However, the only open-source implementations of some of these procedures are either in Java or in Perl, and thus aren't really useful for Sage.

Note: A attentive reader might notice the similarity between those projects. They will be split regarding the type of graph and be coordinated to not overlap but to augment each other.

Visualizing constructs in cluster algebras and quiver representations

(Bryan Wang / Travis Scrimshaw)

I aim to implement visualizations of several key constructs in cluster algebras and quiver representations. The first is Auslander-Reiten quivers, for at least the A_n and D_n cases. The second is labelled endomorphism quivers and mutations within a cluster category, focusing on the A_n case. The third is posets of down-mutations for the A_n case. These features will be useful not only for research purposes, but also as nice examples to play around with and learn from. Aside from these features, I am interested in implementing features for the Quantum Cluster Algebras project.

All the best for this summer, thank you to Google for making this possible, and sorry to all those candidates who didn't make it ...

Sage Days 70 - Berkeley - November 2015

+Dennis Stein brought his cameras and tools to Sage Days 70: 

Sage Days 70 - Berkeley - November 2015 from Dennis Stein on Vimeo.

R's sapply in Numpy

One quick blog entry about sapply and numpy:

Usually, sapply is equal to list comprehensions in Python.
i.e. [f(x) for x in range(1, 10)] is sapply(1:10, f).

But: When you want to apply a function (mapping a number to a vector!) to a vector, you get a matrix. R's sapply does raise the rank of the output to two, while in Numpy you have to push the vector to a higher rank via the magical vector[:, np.newaxis].

In [1]: import numpy as np

In [2]: def f(x):
   ...:     return np.array([4,2,3,9.1,-1]) * x
   ...: 

In [3]: f(9)
Out[3]: array([ 36. ,  18. ,  27. ,  81.9,  -9. ])

In [4]: vals = np.linspace(-1,1,20)

In [5]: np.apply_along_axis(f, 1, vals[:, np.newaxis])
Out[5]: 
array([[-4.        , -2.        , -3.        , -9.1       ,  1.        ],
       [-3.57894737, -1.78947368, -2.68421053, -8.14210526,  0.89473684],
       [-3.15789474, -1.57894737, -2.36842105, -7.18421053,  0.78947368],
       [-2.73684211, -1.36842105, -2.05263158, -6.22631579,  0.68421053],
       [-2.31578947, -1.15789474, -1.73684211, -5.26842105,  0.57894737],
       [-1.89473684, -0.94736842, -1.42105263, -4.31052632,  0.47368421],
       [-1.47368421, -0.73684211, -1.10526316, -3.35263158,  0.36842105],
       [-1.05263158, -0.52631579, -0.78947368, -2.39473684,  0.26315789],
       [-0.63157895, -0.31578947, -0.47368421, -1.43684211,  0.15789474],
       [-0.21052632, -0.10526316, -0.15789474, -0.47894737,  0.05263158],
       [ 0.21052632,  0.10526316,  0.15789474,  0.47894737, -0.05263158],
       [ 0.63157895,  0.31578947,  0.47368421,  1.43684211, -0.15789474],
       [ 1.05263158,  0.52631579,  0.78947368,  2.39473684, -0.26315789],
       [ 1.47368421,  0.73684211,  1.10526316,  3.35263158, -0.36842105],
       [ 1.89473684,  0.94736842,  1.42105263,  4.31052632, -0.47368421],
       [ 2.31578947,  1.15789474,  1.73684211,  5.26842105, -0.57894737],
       [ 2.73684211,  1.36842105,  2.05263158,  6.22631579, -0.68421053],
       [ 3.15789474,  1.57894737,  2.36842105,  7.18421053, -0.78947368],
       [ 3.57894737,  1.78947368,  2.68421053,  8.14210526, -0.89473684],
       [ 4.        ,  2.        ,  3.        ,  9.1       , -1.        ]])

It also works happily for an additional argument weights, which will be defined in the variable w.

In [6]: def f(x, weights):
    return weights * x
   ...: 

In [7]: w = np.array([-2,-1,5,1.1])

In [8]: np.apply_along_axis(f, 1, vals[:, np.newaxis], w)
Out[8]: 
array([[ 2.        ,  1.        , -5.        , -1.1       ],
       [ 1.78947368,  0.89473684, -4.47368421, -0.98421053],
       [ 1.57894737,  0.78947368, -3.94736842, -0.86842105],
       [ 1.36842105,  0.68421053, -3.42105263, -0.75263158],
       [ 1.15789474,  0.57894737, -2.89473684, -0.63684211],
       [ 0.94736842,  0.47368421, -2.36842105, -0.52105263],
       [ 0.73684211,  0.36842105, -1.84210526, -0.40526316],
       [ 0.52631579,  0.26315789, -1.31578947, -0.28947368],
       [ 0.31578947,  0.15789474, -0.78947368, -0.17368421],
       [ 0.10526316,  0.05263158, -0.26315789, -0.05789474],
       [-0.10526316, -0.05263158,  0.26315789,  0.05789474],
       [-0.31578947, -0.15789474,  0.78947368,  0.17368421],
       [-0.52631579, -0.26315789,  1.31578947,  0.28947368],
       [-0.73684211, -0.36842105,  1.84210526,  0.40526316],
       [-0.94736842, -0.47368421,  2.36842105,  0.52105263],
       [-1.15789474, -0.57894737,  2.89473684,  0.63684211],
       [-1.36842105, -0.68421053,  3.42105263,  0.75263158],
       [-1.57894737, -0.78947368,  3.94736842,  0.86842105],
       [-1.78947368, -0.89473684,  4.47368421,  0.98421053],
       [-2.        , -1.        ,  5.        ,  1.1       ]])

Convert several IPython Notebooks to one huge PDF

The IPython Notebook is a neat interactive document. It mixes headings, formatted text (markdown), formulas, images/pictures and interactive code. This is very neat for creating well-documented code examples.

To make ordinary publishing possible, nbconvert converts this interactive json-based file format to ordinary static HTML or LaTeX. The nbviewer website is a well known example for such a repository of HTML-notebooks.

Converting to LaTeX is also very handy, because then you can compile them to static PDF files -- e.g. think of a proper report or article.

So far I know, each input document is converted to only one output document. For one of my projects, I wanted to merge a whole bunch of IPython Notebooks to one (very large) PDF document! To achieve this, I've looked into the various *.tplx template file and started to build on top of them two new templates: partial and master. As the names suggest, partial is the template for each partial document, and master is essentially empty, but combines all partial documents in an orderly fashion.

You can see this here: github:haraldschilly/python-fuer-mathematiker

In particular:

• partial.tplx: This removes all the preamble and heading stuff and sets the document class to the wonderful subfiles LaTeX class.
• master.tplx: This template contains the default header definitions (inherited from IPython's base template), adds some tweaks of my own (font family, margins, title, and subfiles master class) and an embedded Python script to magically gather all documents!

How it works: First, all partial IPython Notebook files are converted to LaTeX using the partial template. Then, the master.tplx contains a small embedded Python script, which iterates through all partial LaTeX files. They are named numerically as --chaptername. This script inserts all those subdocuments and if there is an  increments in the major-number, it inserts a \chapter{...} heading.

To orchestrate all this, a usual Makefile checks for dependencies and finally uses latexmk with the --shell-escape switch (which is necessary to run the embedded Python). Works like a charm!

I hope this is helpful for some of you.

Mein Email an den VAP

Habe soeben dies an vap1@aon.at gesendet:

Mit Entsetzen muss ich heute lesen, dass österreichweit eine Blokadeinfrastruktur für Netzzensur errichtet wird. Ihr Mitwirken an diesem Akt der Unmündigmachung aller Österreicher_innen ist eine Skandal. Legen Sie mir bitte dar, welche Gesetze beim bloßen Download exakt verletzt werden und in welcher Relation dies zu der angeprangerten Bundesbürger_innenbevormundung steht. Die alten Wirtschaftsmodelle haben ausgedient und Ihr VAP Verein ist eine reine Interessensvertreung für große, längst überholte internationale Konzerne und im Beamtenschimmel verfilzte österreichische Organisationen. Ich hoffe Sie bekommen in den nächsten Wochen und Monaten reichlich Gegenwind zu spüren. Willkommen im 21-ten Jahrhundert!

In Vollendung,
ein Bundesbürger

PS:

Als Wochenendlektüre empfehle ich den Barbara Streisand Effekt:
https://en.wikipedia.org/wiki/Streisand_effect

Netflix in Ubuntu - part 2347 of \infinity

Today, Netflix started in Austria. Well, I thought, give it a try. Too bad, it's really painful in my Linux box. So, if you also have Ubuntu 14.10:

1. Get Chrome Beta 38 or higher
2. Update libnss3 via running this in your terminal:
   
   for pkg in libnss3_3.17-1ubuntu1_amd64.deb libnss3-nssdb_3.17-1ubuntu1_all.deb libnss3-1d_3.17-1ubuntu1_amd64.deb
   do
      wget http://archive.ubuntu.com/ubuntu/pool/main/n/nss/${pkg}
   doneThen install it:
   
   $ sudo dpkg -i libnss*.deb
3. Install the User-Agent Switcher for Chrome
   In its options (right-click on the icon) you have to add a new entry (besides the "String", nothing else really matters):
   
   
   • Name: Netflix
   • String: Mozilla/5.0 (Windows NT 6.3; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/38.0.2114.2 Safari/537.36
   • Group: keep it empty
   • Indicator: FLX (for Net-Flix)
   
   After that, set it to be active on netflix.com automatically: On the left, in "Permanent Spoof List"...
4. Restart chrome, ... cross your fingers ... and enjoy.
5. Edit: you also have to set the profile properties in netflix to HTML5 (though, I think it still works without doing anything, because there is no silverlight anyways)