Sage & LMonade GSOC 2014

This year Sage and lmonade are mentoring organizations for the Google Summer of Code again. We have many exciting projects for students to work (from home) over the summer, get mentored by experts in the field and get paid by Google.

Sage projects

lmonade projects

Note that projects are not limited to the ideas presented on these pages. That is, if you have a nice project you’d like to propose, by all means do so! The application deadline for students is March 21st. These days they should be talking to potential mentors and forming an applications. If you know any student who might be interested or have access to any forum such students might read, please forward this announcement.

Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations

As you may know, today is the last day of the wokshop on Efficient Linear Algebra for Gröbner Basis Computations that Christian Eder, Burcin Eröcal, Alexander Dreyer and I organised.

I have to say that I am quite pleased with how the workshop played out. We planned the whole thing to be hands on: people were strongly encouraged to work on projects, i.e., to write code preferably together, in addition to attending talks. Those who attended a Sage Days workshop in the past, will know what workshop format I am referring to. Continue reading “Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations” →

Sage 4.8 is out

If you care about the stuff I care about (and why else would you read this blog?) you might get excited about a few changes in Sage.

Efficient linear algebra for $\mathbb{F}_{2^e}$

The very first non-trivial patch I ever produced for Sage was about interfacing with NTL for dense linear algebra over $\mathbb{F}_{2^e}$ (I was interested in algebraic attacks against AES at the time). Here’s William’s reply:

Your NTL patch worked perfectly for me first try. I tried more benchmarks (on Pentium-M 1.8Ghz).

[…]

This is pretty good; vastly better than what’s was in SAGE by default, and way better than PARI. Note that MAGMA is much faster though (nearly 8 times faster):

[…]

MAGMA uses (1) […] and (2) a totally different algorithm for computing the echelon form. […] As far as I know, the MAGMA method is not implemented anywhere in the open source world But I’d love to be wrong about that… or even remedy that.

Well, that was 2006. Fast forward to the year 2011 and we get the following timings for computing the reduced row echelon form of a 1,000 x 1,000 matrix over $\mathbb{F}_{256}$ : Sage 4.7.2 takes 36.53 seconds , NTL 5.4.2 takes 31.06 seconds and Magma 2.15 does it in 0.87 seconds. So essentially, the situation didn’t change at all for the better.

With Sage 4.8 this situation changes dramatically and we get that Sage performs this computation in 0.08 seconds, that’s 450 times faster than Sage 4.7.2. This is because M4RIE was merged in Sage 4.8. Hence, Sage is now (in some cases by far) fastest system to do linear algebra with dense matrices over $\mathbb{F}_{2^e}$ for $1 \leq e \leq 8$ and usually also for $9 \leq e \leq 10$ .

Efficient linear algebra for $\mathbb{F}_{p}$

One can tell a similar story for $\mathbb{F}_p$ for, say, small to medium sized primes $p$ . In Sage 4.7.2 it took 1.12* seconds to multiply two 1,000 x 1,000 matrices over $\mathbb{F}_{251}$ (although you always had the option to call LinBox explicitly which was way faster but took more memory). With Sage 4.8 the same computation takes *0.16 seconds. For comparison, Magma 2.15 takes 0.22 seconds. So here again Sage moved from poor performance to best in class performance between 4.7.2 and 4.8 simply by making proper use of available libraries.

Viable Alternative yet?

Overall, the story for dense linear algebra in Sage for small finite fields $\mathbb{F}_q$ is as follows.

$q$	Implementation	Comments
$2$	M4RI	Fastest implementation or equal performance depending on platform
$3,5,7 \dots$	LinBox	Decent performance, but faster implementations are known in the literature. Also, Magma is a bit faster on my machine.
prime < $2^{23}$	LinBox	Fastest implementation or equal performance depending on platform.
$2^e$ for $2 \leq e \leq 8$	M4RIE	Fastest
$p^e$ for $p>2$	Generic	Very poor performance, but some work is being done.

So, once we fix that last row Sage finally achieves “viable alternative” quality when it comes to dense linear algebra over $\mathbb{F}_{q}$ if $q$ is $q < 2^{16}$ .

Dense matrices mod n via FFLAS/FFPACK

During last weeks Sage Days 32 I worked on finishing a patch by Clément Pernet and Burcin Eröcal which switches Sage’s native matrices mod n (for $n<2^{23}$ ) to FFLAS/FFPACK. The purpose of this exercise was to make operations with dense matrices mod n both faster and more memory efficient (currently, Sage does a lot of copying around when calling any LinBox function). Well, we almost succeeded. Continue reading “Dense matrices mod n via FFLAS/FFPACK” →