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

The very first non-trivial patch I ever produced for Sage was about interfacing with NTL for dense linear algebra over (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 : 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 for and usually also for .

## Efficient linear algebra for

One can tell a similar story for for, say, small to medium sized primes . In Sage 4.7.2 it took **1.12* seconds to multiply two 1,000 x 1,000 matrices over (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 is as follows.

Implementation | Comments | |

M4RI | Fastest implementation or equal performance depending on platform | |

LinBox | Decent performance, but faster implementations are known in the literature. Also, Magma is a bit faster on my machine. | |

prime < | LinBox | Fastest implementation or equal performance depending on platform. |

for | M4RIE | Fastest |

for | 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 if is .