Vote for adding M4RIE as a new standard package
Simon King
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
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
leif
> 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.
>
> matrices over finite not necessarily prime fields), and I vote for
> including it as a standard package.
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
> 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
> 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
On 20 Aug., 19:36, Martin Albrecht <martinralbre...@googlemail.com>
wrote:
>
> http://groups.google.com/group/sage-devel/browse_thread/thread/1794b8985d788004/
>
> which left me with the impression that it was accepted.
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
> 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
<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
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.
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:
>
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
>
> 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
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
[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
Rob Beezer
> So:
> [X] yes include it as standard
David Joyner
>
>> 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
> [] 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
On Aug 20, 10:09 pm, Martin Albrecht <martinralbre...@googlemail.com>
wrote:
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.