Vote for adding M4RIE as a new standard package

27 views
Skip to first unread message

Simon King

unread,
Aug 20, 2011, 10:34:46 AM8/20/11
to sage-devel
Hi!

Martin Albrecht had opened #9562 and proposed to use M4RIE as default
for matrices over GF(2^e). If I understand correctly, the package
builds fine on all supported platforms (including Cygwin).

The ticket is almost getting a positive review from me, modulo some
minor issues with documentation.

On the ticket, David Kirkby reminded us that a new standard spkg
requires a vote on sage-devel, so, here we are...

I, for one, am particularly impressed by the performance. If I
understood correctly, it is not only VASTLY faster than the current
implementation in Sage - it even beats Magma. Perhaps Martin can make
a stronger case.

Here is an example:

With the current implementation, we have

sage: MS = MatrixSpace(GF(64,'a'),800,800)
sage: %time A = MS.random_element()
CPU times: user 1.10 s, sys: 0.01 s, total: 1.10 s
Wall time: 1.10 s
sage: B = MS.random_element()
sage: save((A,B),'testmat')
sage: %time C=A*B
CPU times: user 38.24 s, sys: 0.02 s, total: 38.26 s
Wall time: 38.38 s
sage: %time A.echelonize()
CPU times: user 21.55 s, sys: 0.00 s, total: 21.56 s
Wall time: 21.62 s

With M4RIE, we have
sage: MS = MatrixSpace(GF(64,'a'),800,800)
sage: %time A = MS.random_element()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
sage: B = MS.random_element()
sage: %time C=A*B
CPU times: user 0.12 s, sys: 0.00 s, total: 0.12 s
Wall time: 0.12 s
sage: %time A.echelonize()
CPU times: user 0.12 s, sys: 0.00 s, total: 0.12 s
Wall time: 0.13 s

I will certainly use M4RIE in my applications (where I need fast
matrices over finite not necessarily prime fields), and I vote for
including it as a standard package.

Best regards,
Simon

Simon King

unread,
Aug 20, 2011, 11:38:45 AM8/20/11
to sage-devel
PS:

I forgot to ask another question. Provided that we decide to make it a
standard package: Should the new module for matrices over GF(2^e) be
included in the reference manual?

Without any exception, all methods are either cdef resp. underscore
(hence, will not be in the reference manual anyway) or are overriding
a method inherited from a super-class that is documented in the
reference manual. Hence, including it in the manual would not teach
the user a new functionality.

Therefore I think it is not needed to have it in the reference
manual.

Cheers,
Simon

Dima Pasechnik

unread,
Aug 20, 2011, 11:45:56 AM8/20/11
to sage-...@googlegroups.com
I am all for it, but shouldn't  it become an optional package first?

Dima 

leif

unread,
Aug 20, 2011, 11:50:14 AM8/20/11
to sage-devel
On 20 Aug., 16:34, Simon King <simon.k...@uni-jena.de> wrote:
> Martin Albrecht had opened #9562 and proposed to use M4RIE as default
> for matrices over GF(2^e). If I understand correctly, the package
> builds fine on all supported platforms (including Cygwin).
>
> The ticket is almost getting a positive review from me, modulo some
> minor issues with documentation.
>
> On the ticket, David Kirkby reminded us that a new standard spkg
> requires a vote on sage-devel, so, here we are...
>
> I, for one, am particularly impressed by the performance. If I
> understood correctly, it is not only VASTLY faster than the current
> implementation in Sage - it even beats Magma. Perhaps Martin can make
> a stronger case.
>
> I will certainly use M4RIE in my applications (where I need fast
> matrices over finite not necessarily prime fields), and I vote for
> including it as a standard package.


FWIW, the current libm4rie-20110715.spkg is 360 KB, while the cleaned-
up matplotlib-1.0.1.p0.spkg will shrink the Sage tarball by 7 MB
again, so I won't object to including it as a standard spkg.

IIRC, adding a standard spkg also requires someone in charge of its
maintenance for at least two years; maybe ask Martin...? ;-)


-leif

Martin Albrecht

unread,
Aug 20, 2011, 1:36:37 PM8/20/11
to sage-...@googlegroups.com
On Saturday 20 August 2011, Simon King wrote:
> Hi!
>
> Martin Albrecht had opened #9562 and proposed to use M4RIE as default
> for matrices over GF(2^e). If I understand correctly, the package
> builds fine on all supported platforms (including Cygwin).
>
> The ticket is almost getting a positive review from me, modulo some
> minor issues with documentation.
>
> On the ticket, David Kirkby reminded us that a new standard spkg
> requires a vote on sage-devel, so, here we are...

Hi,

we did have some sort of vote before

http://groups.google.com/group/sage-
devel/browse_thread/thread/1794b8985d788004/

which left me with the impression that it was accepted. But of course I am
biased to read it that way.



> I, for one, am particularly impressed by the performance. If I
> understood correctly, it is not only VASTLY faster than the current
> implementation in Sage - it even beats Magma. Perhaps Martin can make
> a stronger case.

Here are some timings:

http://martinralbrecht.files.wordpress.com/2011/03/20110330_-_m4ri_-
_nancy1.pdf

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

Martin Albrecht

unread,
Aug 20, 2011, 1:38:03 PM8/20/11
to sage-...@googlegroups.com
> IIRC, adding a standard spkg also requires someone in charge of its
> maintenance for at least two years; maybe ask Martin...? ;-)

This is new to me but it makes sense. Of course, I will look after maintaining
this library's SPKG.

Simon King

unread,
Aug 20, 2011, 1:50:28 PM8/20/11
to sage-devel
Hi Martin,

On 20 Aug., 19:36, Martin Albrecht <martinralbre...@googlemail.com>
wrote:
> we did have some sort of vote before
>
> http://groups.google.com/group/sage-devel/browse_thread/thread/1794b8985d788004/
>
> which left me with the impression that it was accepted.

I was not aware of that thread (I think you didn't mention it on the
ticket).

And I hope you don't mind that I asked here: I thought that the wish
to add it as a standard package was implicit in your opening the
ticket. And I did not know about the two-year-rule either; will the 13
months since opening the ticket be taken into account :-?

Cheers,
Simon

Martin Albrecht

unread,
Aug 20, 2011, 1:55:55 PM8/20/11
to sage-...@googlegroups.com
> And I hope you don't mind that I asked here: I thought that the wish
> to add it as a standard package was implicit in your opening the
> ticket.

I don't understand the question. Yep, I wanted it to become standard when I
opened it and I still would like that to happen.

William Stein

unread,
Aug 20, 2011, 3:56:18 PM8/20/11
to sage-...@googlegroups.com
On Sat, Aug 20, 2011 at 10:55 AM, Martin Albrecht
<martinr...@googlemail.com> wrote:
>> And I hope you don't mind that I asked here: I thought that the wish
>> to add it as a standard package was implicit in your opening the
>> ticket.
>
> I don't understand the question. Yep, I wanted it to become standard when I
> opened it and I still would like that to happen.

My impression is that this is *not* a totally new spkg, but simply
some additional code of a similar nature being included in an existing
spkg. If so, no formal vote is required for this, just positive
review of the ticket + release manager agreeing.

The ticket itself (http://trac.sagemath.org/sage_trac/ticket/9562) is
confusing, since in the description it points to a new spkg, but the
rest of the ticket refers to simply updating an existing spkg. It
appears that the new spkg is:

http://sage.math.washington.edu/home/malb/spkgs/libm4ri-20110701.alpha.spkg

This package is midway through the comments, and isn't mentioned in
the ticket description (as I write this).

-- William

Simon King

unread,
Aug 20, 2011, 4:54:02 PM8/20/11
to sage-devel
Hi William, hi Martin,

On 20 Aug., 21:56, William Stein <wst...@gmail.com> wrote:
> My impression is that this is *not* a totally new spkg, but simply
> some additional code of a similar nature being included in an existing
> spkg.    If so, no formal vote is required for this, just positive
> review of the ticket + release manager agreeing.
>
> The ticket itself (http://trac.sagemath.org/sage_trac/ticket/9562) is
> confusing, since in the description it points to a new spkg, but the
> rest of the ticket refers to simply updating an existing spkg.

I just checked the diffs for the ticket description. It seems that,
until 6 or 7 weeks ago, it was attempted to fit M4RIE into the new
version of the M4RI spkg (the missing "E" means that it is for
matrices over GF(2), not GF(2^e)). In that sense, it is not completely
new.

But apparently, Martin then thought it would be better to have two
separate spkgs: The update of M4RI was subsequently tracked on #11574,
and M4RIE became a separate spkg. Martin, correct me if I
misunderstood.

>   It
> appears that the new spkg is:
>
>      http://sage.math.washington.edu/home/malb/spkgs/libm4ri-20110701.alph...

No. The final spkg (the one that I was reviewing, anyway) is
https://bitbucket.org/malb/m4ri/downloads/libm4rie-20110715.spkg and
has been introduced to the ticket 6 weeks ago (in the diff between
version 51 and 55 of the ticket).

The spkg you mention has been briefly discussed in one post 7 weeks
ago.

Cheers,
Simon

Martin Albrecht

unread,
Aug 20, 2011, 5:02:56 PM8/20/11
to sage-...@googlegroups.com
On Saturday 20 August 2011, Simon King wrote:
> Hi William, hi Martin,
>
> On 20 Aug., 21:56, William Stein <wst...@gmail.com> wrote:
> > My impression is that this is *not* a totally new spkg, but simply
> > some additional code of a similar nature being included in an existing
> > spkg. If so, no formal vote is required for this, just positive
> > review of the ticket + release manager agreeing.
> >
> > The ticket itself (http://trac.sagemath.org/sage_trac/ticket/9562) is
> > confusing, since in the description it points to a new spkg, but the
> > rest of the ticket refers to simply updating an existing spkg.
>
> I just checked the diffs for the ticket description. It seems that,
> until 6 or 7 weeks ago, it was attempted to fit M4RIE into the new
> version of the M4RI spkg (the missing "E" means that it is for
> matrices over GF(2), not GF(2^e)). In that sense, it is not completely
> new.
>
> But apparently, Martin then thought it would be better to have two
> separate spkgs: The update of M4RI was subsequently tracked on #11574,
> and M4RIE became a separate spkg. Martin, correct me if I
> misunderstood.

Hi, yes that's essentially correct. I started out with just updating the M4RI
but since then others convinced me M4RIE should be an independent SPKG. Hence
I split the M4RI SPKG into two.

Martin Albrecht

unread,
Aug 20, 2011, 5:09:28 PM8/20/11
to sage-...@googlegroups.com
One more thing: let's just have a formal vote now and not bent the rules. If
there's sufficient interest in this then it will survive an additional vote.

Here's the description again:

M4RIE is a library for dense linear algebra over GF(2^e). It is heavily based
on M4RI and is written by me. It is about one year old now (it was started at
a Sage Days at RISC) and many things will be improved in the future. However,
even in its current state it is much much faster than what we have in Sage now
(1000 - 10000 times sometimes) and often much faster than what Magma has to
offer (up to 10 times).

The library is written in C (+ some C++ for finite fields), comes under the
GPLv2+ and builds & passes tests on PPC, x86, x86_64, ia64, arm, sparc under
Linux, Solaris (Sparc), OSX and Cygwin (last time I checked). It is actively
maintained by a Sage developer: me.

So:
[] yes include it as standard
[] yes but have it as optional SPKG first
[] I don't care
[] no don't include

Jason Grout

unread,
Aug 20, 2011, 5:16:31 PM8/20/11
to sage-...@googlegroups.com

[X] yes include it as standard

[ ] yes but have it as optional SPKG first
[ ] I don't care
[ ] no don't include

I agree in principle, though I haven't reviewed any of the spkg.

Jason

Harald Schilly

unread,
Aug 20, 2011, 5:29:26 PM8/20/11
to sage-...@googlegroups.com
+1 from me for standard package.

H

Rob Beezer

unread,
Aug 20, 2011, 5:48:14 PM8/20/11
to sage-devel

> So:
> [X] yes include it as standard

David Joyner

unread,
Aug 20, 2011, 5:49:27 PM8/20/11
to sage-...@googlegroups.com
On Sat, Aug 20, 2011 at 5:48 PM, Rob Beezer <goo...@beezer.cotse.net> wrote:
>
>> So:
>> [X] yes include it as standard

agreed, +1

>> [] yes but have it as optional SPKG first
>> [] I don't care
>> [] no don't include
>

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

Alex Ghitza

unread,
Aug 20, 2011, 6:00:24 PM8/20/11
to sage-...@googlegroups.com
> [X] yes include it as standard

> [] yes but have it as optional SPKG first
> [] I don't care
> [] no don't include

Best,
Alex

--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- http://aghitza.org

Bill Hart

unread,
Aug 21, 2011, 5:42:48 AM8/21/11
to sage-devel

On Aug 20, 10:09 pm, Martin Albrecht <martinralbre...@googlemail.com>
wrote:
> One more thing: let's just have a formal vote now and not bent the rules.

It's important to have rules so that we have something to bend. But if
you insist:

> So:
> [X] yes, c'mon why isn't it included already
> [] yes but write a paper about it first
> [] just passing through, ignore me
> [] what!? are you kidding! no way!
> [] what's a M4RIE
>

Bill.
Reply all
Reply to author
Forward
0 new messages