Add M4RIE to Sage #9562

malb · 2010-07-21T10:41:53Z

M4RIE is a library for linear algebra over small extension of GF(2). It is still in an early stage but already offers performance comparable to Magma for many inputs and is more than 1000 times faster than what we have in Sage right now.

Upstream: http://bitbucket.org/malb/m4rie/

Sage Days 24 coding sprint: http://wiki.sagemath.org/days24/projects/gf2e

Install http://sage.math.washington.edu/home/malb/spkgs/libm4rie-20111004.spkg
Apply attachment: m4rie_for_sage.patch
Apply attachment: m4rie_spkg.patch to Sage root repository

There was a vote on sage-devel, recommending to add this as a standard spkg.

Depends on #11757
Depends on #4260

CC: @sagetrac-mvngu @simon-king-jena

Component: packages: standard

Keywords: m4ri, sd32

Author: Martin Albrecht

Reviewer: Paul Zimmermann, Simon King

Merged: sage-4.8.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/9562

malb · 2010-07-21T10:43:56Z

comment:2

The SPKG is here:

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

malb · 2010-07-21T10:45:48Z

comment:3

The attached patch depends on #9475

malb · 2010-07-21T10:50:03Z

comment:4

The package compiles on t2. sage-check fails because libstdc++ cannot be found (I believe this is due to a problem in the old Sage I have on t2). I cannot apply my patch against this old version of Sage either.

mwhansen · 2010-07-21T12:24:02Z

comment:5

This builds a static library only on Cygwin, but segfaults on both of the tests.

malb · 2010-07-21T12:43:37Z

comment:6

Mike, is there a Sage I can copy on winxp1?

malb · 2010-07-21T13:20:58Z

comment:7

sage -t  devel/sage/sage/modular/modsym/space.py # 1 doctests failed
sage -t  devel/sage/sage/misc/sagedoc.py # 3 doctests failed
sage -t  devel/sage/sage/crypto/mq/mpolynomialsystem.py # 19 doctests failed
sage -t  devel/sage/sage/crypto/mq/sr.py # 7 doctests failed
sage -t  devel/sage/sage/modular/modsym/modsym.py # 1 doctests failed
sage -t  devel/sage/sage/rings/polynomial/pbori.pyx # 2 doctests failed
sage -t  devel/sage/sage/crypto/block_cipher/miniaes.py # 72 doctests failed

sagetrac-drkirkby · 2010-07-21T14:40:14Z

comment:8

Replying to @malb:

The package compiles on t2. sage-check fails because libstdc++ cannot be found (I believe this is due to a problem in the old Sage I have on t2). I cannot apply my patch against this old version of Sage either.

There's a Sage 4.5.1 package in /usr/local.

malb · 2010-07-21T15:33:47Z

comment:9

After unpacking that I get

     21 from numpy.lib import triu
---> 22 from numpy.linalg import lapack_lite
     23 from numpy.core.defmatrix import matrix_power
     24 

ImportError: ld.so.1: python: fatal: libgfortran.so.3: open failed: No such file or directory
Error importing ipy_profile_sage - perhaps you should run %upgrade?
WARNING: Loading of ipy_profile_sage failed.

Any ideas?

malb · 2010-07-21T20:49:41Z

comment:10

The updated patch fixes all doctest failures.

PS: CCing Minh since I'm touching his code in a potentially non-trivial way/

sagetrac-drkirkby · 2010-07-21T23:09:22Z

comment:11

It's not passing the tests properly on 64-bit OpenSolaris, and I doubt anywhere where SAGE64 needs to be set to yes. The -m64 flag is not getting passed when running the tests, so whilst it builds a 64-bit library, it looks like it tries to create 32-bit objects and link to that 64-bit library.

I have not investigated this in any detail, but they were my initial observations. I would try building on 't2' with SAGE64 set to yes. Not all of Sage will build 64-bit without some hacks, but it should be fairly easy to get enough of Sage built to build this library.

Successfully installed libm4ri-20100730
Running the test suite.
Testing the M4RI library
make -j12  test_elimination test_multiplication
make[1]: Entering directory `/export/home/drkirkby/sage-4.5/spkg/build/libm4ri-20100730/m4rie'
make[1]: warning: -jN forced in submake: disabling jobserver mode.
g++ -DHAVE_CONFIG_H -I. -I./src   -I/export/home/drkirkby/sage-4.5/local/include -m64  -g -O2 -MT test_elimination.o -MD -MP -MF .deps/test_elimination.Tpo -c -o test_elimination.o `test -f 'tests/test_elimination.cc' || echo './'`tests/test_elimination.cc
g++ -DHAVE_CONFIG_H -I. -I./src   -I/export/home/drkirkby/sage-4.5/local/include -m64  -g -O2 -MT test_multiplication.o -MD -MP -MF .deps/test_multiplication.Tpo -c -o test_multiplication.o `test -f 'tests/test_multiplication.cc' || echo './'`tests/test_multiplication.cc
mv -f .deps/test_elimination.Tpo .deps/test_elimination.Po
/bin/sh ./libtool --tag=CXX   --mode=link g++  -g -O2 -lm4rie -lm4ri -lgivaro -lntl -lgmpxx -lgmp -lm -lstdc++  -o test_elimination test_elimination.o  
mv -f .deps/test_multiplication.Tpo .deps/test_multiplication.Po
/bin/sh ./libtool --tag=CXX   --mode=link g++  -g -O2 -lm4rie -lm4ri -lgivaro -lntl -lgmpxx -lgmp -lm -lstdc++  -o test_multiplication test_multiplication.o  
libtool: link: g++ -g -O2 -o .libs/test_elimination test_elimination.o  /export/home/drkirkby/sage-4.5/spkg/build/libm4ri-20100730/m4rie/.libs/libm4rie.so -L/export/home/drkirkby/sage-4.5/local/lib /export/home/drkirkby/sage-4.5/local/lib/libm4ri.so /export/home/drkirkby/sage-4.5/local/lib/libgivaro.so -L/export/home/drkirkby/sage-4.5/local//lib -lntl /export/home/drkirkby/sage-4.5/local/lib/libgmpxx.so /export/home/drkirkby/sage-4.5/local/lib/libgmp.so /usr/local/gcc-4.4.4-multilib/lib/amd64/libstdc++.so -lm -Wl,-R -Wl,/export/home/drkirkby/sage-4.5/local/lib -Wl,-R -Wl,/usr/local/gcc-4.4.4-multilib/lib/amd64
libtool: link: g++ -g -O2 -o .libs/test_multiplication test_multiplication.o  /export/home/drkirkby/sage-4.5/spkg/build/libm4ri-20100730/m4rie/.libs/libm4rie.so -L/export/home/drkirkby/sage-4.5/local/lib /export/home/drkirkby/sage-4.5/local/lib/libm4ri.so /export/home/drkirkby/sage-4.5/local/lib/libgivaro.so -L/export/home/drkirkby/sage-4.5/local//lib -lntl /export/home/drkirkby/sage-4.5/local/lib/libgmpxx.so /export/home/drkirkby/sage-4.5/local/lib/libgmp.so /usr/local/gcc-4.4.4-multilib/lib/amd64/libstdc++.so -lm -Wl,-R -Wl,/export/home/drkirkby/sage-4.5/local/lib -Wl,-R -Wl,/usr/local/gcc-4.4.4-multilib/lib/amd64
ldld::  fatal: filefatal :test_multiplication.o :file  wrong test_elimination.o: wrong ELF class:ELF ELFCLASS64
ld: fatal:  file processing errors.class No:  output ELFCLASS64written 
to .libs/test_multiplication
ld: fatal: file processing errors. No output written to .libs/test_elimination
collect2: ld returned 1 exit status
collect2: ld returned 1 exit status
make[1]: *** [test_multiplication] Error 1
make[1]: *** Waiting for unfinished jobs....
make[1]: *** [test_elimination] Error 1
make[1]: Leaving directory `/export/home/drkirkby/sage-4.5/spkg/build/libm4ri-20100730/m4rie'
make: *** [check-am] Error 2
Error testing M4RI
*************************************
Error testing package ** libm4ri-20100730 **
*************************************
sage: An error occurred while testing libm4ri-20100730

malb · 2010-07-21T23:39:13Z

comment:12

I updated the SPKG linked above

Building shared libraries on Cygwin now
Fixed the crashes in spkg-check in Cygwin (this was actually a real bug)
Fixed flags for SAGE64

mwhansen · 2010-07-22T00:08:07Z

comment:13

Everything works on my Cygwin install.

sagetrac-drkirkby · 2010-07-22T00:33:55Z

comment:14

It passed all self-tests on 64-bit OpenSolaris (x64) and 64-bit Solaris 10 (SPARC). Since neither platform has a stable version of Sage yet, running the doctests is pointless.

A few questions:

Has there been an agreement to add this library? If so, can you provide a link to it.
Why is it not in another package, rather than added to the libm4ri package?
Do the self tests pass on Linux?
Do the doctests pass on Linux?
Do the self-tests pass on 32-bit SPARC? (Note my point above about there being a 4.5.1 in /usr/local on t2)
Do the doc tests pass on 32-bit SPARC?
Do the self-tests pass on OS X?
Do the doctests pass on OS X?

malb · 2010-07-22T01:16:42Z

comment:15

Replying to @sagetrac-drkirkby:

A few questions:

Has there been an agreement to add this library? If so, can you provide a link to it.

No decision on [sage-devel] has happened yet. However, the Sage developers here at Sage Days 24 seem to be in favour of adding it.

Why is it not in another package, rather than added to the libm4ri package?

It makes maintaining the thing easier for all sides: I'm the maintainer of both libraries for both upstream and the SPKGs. It isn't even decided yet whether the two libraries might get merged in the future. Finally, William asked me to not add a new SPKG but to add the M4RIe extension to the M4RI package.

Do the self tests pass on Linux?

Yes.

Do the doctests pass on Linux?

Yes.

Do the self-tests pass on 32-bit SPARC? (Note my point above about there being a 4.5.1 in /usr/local on t2)

Note my point above about not being able to use it.

Do the doc tests pass on 32-bit SPARC?

No clue.

Do the self-tests pass on OS X?

Yes.

Do the doctests pass on OS X?

Yes.

sagetrac-drkirkby · 2010-07-22T07:00:29Z

comment:16

Replying to @malb:

Replying to @sagetrac-drkirkby:

A few questions:

Has there been an agreement to add this library? If so, can you provide a link to it.

No decision on [sage-devel] has happened yet. However, the Sage developers here at Sage Days 24 seem to be in favour of adding it.

If the packages does get positive review, there should be a note to the release manager(s) not to merge it until there has been an agreement. Though in this case, it looks like getting a vote seems a formality.

Why is it not in another package, rather than added to the libm4ri package?

It makes maintaining the thing easier for all sides: I'm the maintainer of both libraries for both upstream and the SPKGs. It isn't even decided yet whether the two libraries might get merged in the future. Finally, William asked me to not add a new SPKG but to add the M4RIe extension to the M4RI package.

One obvious disadvantage of that approach is that since one library relies on the other, the first could be built in parallel with some other packages. That could potentially slow parallel builds.

Do the self tests pass on Linux?

Yes.

Do the doctests pass on Linux?

Yes.

Do the self-tests pass on 32-bit SPARC? (Note my point above about there being a 4.5.1 in /usr/local on t2)

Note my point above about not being able to use it.

Your point above says that's probably because you have an old version.

But I said above, there is the latest version on there - (/usr/local/sage-4.5.1-Solaris_10_SPARC-sun4u-SunOS.tar.gz is a pre-built copy of the latest version of Sage on 't2'). If that does not work, let me know - I'd be very surprised if it does not. Otherwise, you could just build Sage from source.

Do the doc tests pass on 32-bit SPARC?

No clue.

See point above.

Dave

malb · 2010-07-22T17:09:11Z

comment:17

Dave, the testuite fails:

/bin/bash ./libtool --tag=CXX   --mode=link g++  -g -O2 -lm4rie -lm4ri -lgivaro -lntl -lgmpxx -lgmp -lm -lstdc++  -o test_elimination test_elimination.o  
libtool: link: warning: library `/home/malb/t2/sage-4.5.1-Solaris_10_SPARC-sun4u-SunOS/local/lib/libstdc++.la' was moved.
libtool: link: cannot find the library `/usr/local/gcc-4.4.3/lib/libstdc++.la' or unhandled argument `/usr/local/gcc-4.4.3/lib/libstdc++.la'
make[1]: *** [test_elimination] Error 1
make[1]: Leaving directory `/home/malb/t2/sage-4.5.1-Solaris_10_SPARC-sun4u-SunOS/spkg/build/libm4ri-20100730/m4rie'

Any idea why it wouldn't find libstdc++ on t2?

malb · 2010-07-22T21:50:03Z

comment:19

These lines:

libtool: link: warning: library `/home/malb/t2/sage-4.5.1-Solaris_10_SPARC-sun4u-SunOS/local/lib/libstdc++.la' was moved.
libtool: link: cannot find the library `/usr/local/gcc-4.4.3/lib/libstdc++.la' or unhandled argument `/usr/local/gcc-4.4.3/lib/libstdc++.la'

make me think it's the Sage binary that is broken? Why is there be a libstdc++ in the Sage tarball ?

sagetrac-drkirkby · 2010-07-22T22:30:37Z

comment:20

Replying to @malb:

These lines:

libtool: link: warning: library `/home/malb/t2/sage-4.5.1-Solaris_10_SPARC-sun4u-SunOS/local/lib/libstdc++.la' was moved.
libtool: link: cannot find the library `/usr/local/gcc-4.4.3/lib/libstdc++.la' or unhandled argument `/usr/local/gcc-4.4.3/lib/libstdc++.la'

make me think it's the Sage binary that is broken? Why is there be a libstdc++ in the Sage tarball ?

The reason it is there is that the version of gcc shipped with Solaris is 3.4.3, so there are no recent gcc libraries. The compiler is not built with Fortran support, so there is no libgfortran at all. One needs recent run-time libraries, with fortran support, so I added them to the Sage binary.

It may be that deleting (making a copy first) of those .la files will solve the problem. Otherwise, editing them to point at the location of the libraries in $SAGE_LOCAL/lib will almost certainly solve it.

If that does not work, just build Sage from source. It does not take too long if you build packages in parallel.

Dave

malb · 2010-08-10T13:50:27Z

comment:21

malb@t2:~/t2/sage-4.5.1$ ./sage -t devel/sage/sage/matrix/matrix_mod2_dense.pyx 

sage -t  "devel/sage/sage/matrix/matrix_mod2_dense.pyx"     

         [92.7 s]

 ----------------------------------------------------------------------

All tests passed!

Total time for all tests: 92.8 seconds

malb@t2:~/t2/sage-4.5.1$ ./sage -t devel/sage/sage/matrix/matrix_mod2e_dense.pyx 

sage -t  "devel/sage/sage/matrix/matrix_mod2e_dense.pyx"    

         [50.0 s]

----------------------------------------------------------------------

All tests passed!

Total time for all tests: 50.0 seconds

After finally building Sage t2 I can confirm that doctests pass there too

simon-king-jena · 2011-10-28T05:25:19Z

comment:125

Replying to @malb:

okay, rebased.

Thank you! The new patch applies cleanly.

simon-king-jena · 2011-10-28T05:25:19Z

Changed work issues from Rebase wrt #4260 to none

simon-king-jena · 2011-10-28T13:18:35Z

comment:126

It seems to me that all previous complaints are addressed in the new spkg and patches.

In particular, if one has opened the spkg, starts a sage shell and does ./spkg-install, then ./spkg-check works, with all tests. passing.

hg status in the spkg is fine, and SPKG.txt looks fine as well (except a typo in the last line, should be "split from", not "split form" - but please leave that error, since the Gods don't like perfection among the mortals :)

Moreover, sage -coverage sage/matrix/matrix_mod2e_dense.pyx is OK.

All doc tests pass as well, and I think the original problems with t2 had been dealt with.

Thus, I hope all participants agree that it is a positive review!

nexttime · 2011-10-28T13:29:30Z

comment:127

Replying to @simon-king-jena:

Thus, I hope all participants agree that it is a positive review!

Sollte ich dein Urteil infrage stellen weil du uns für sterblich hältst?

jdemeyer · 2011-11-15T08:55:13Z

Merged: sage-4.8.alpha2

jdemeyer · 2011-11-20T10:24:29Z

Changed merged from sage-4.8.alpha2 to none

jdemeyer · 2011-11-20T10:24:29Z

comment:131

Reopened because of issues with #4260.

jdemeyer · 2011-12-01T08:12:30Z

Merged: sage-4.8.alpha3

malb added this to the sage-5.0 milestone Jul 21, 2010

malb added c: packages: standard labels Jul 21, 2010

This comment has been minimized.

Sign in to view

malb added the s: needs work label Jul 21, 2010

malb added s: needs review and removed s: needs work labels Jul 21, 2010

malb added s: needs work and removed s: needs review labels Jul 22, 2010

malb removed the s: needs work label Aug 10, 2010

simon-king-jena added s: positive review and removed s: needs review labels Oct 28, 2011

nexttime mannequin modified the milestones: sage-5.0, sage-4.8 Oct 28, 2011

jdemeyer removed this from the sage-4.8 milestone Nov 3, 2011

jdemeyer added the pending label Nov 3, 2011

jdemeyer removed the s: positive review label Nov 15, 2011

jdemeyer closed this as completed Nov 15, 2011

jdemeyer reopened this Nov 20, 2011

jdemeyer added s: needs review and removed s: needs review labels Nov 20, 2011

jdemeyer removed the s: positive review label Dec 1, 2011

jdemeyer closed this as completed Dec 1, 2011

rwst removed the pending label Apr 19, 2015

nexttime mannequin added this to the sage-4.8 milestone Apr 19, 2015

This was referenced Aug 15, 2011

Speed up parent creation for multiplication of square matrices #8096

Closed

fix variable substitution in PolyBoRi + finding M4RI #9717

Closed

This was referenced Nov 23, 2017

Serious regression caused by #9138 #11900

Closed

Use MeatAxe as an optional back end for dense matrices over GF(p^n), p odd, n>1, p^n<255 #12103

Closed

Prime slicing for matrix multiplication #12177

Open

loefflerd mannequin mentioned this issue Jan 3, 2012

M4RIE test suite fails due to missing dependencies #12245

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add M4RIE to Sage #9562

Add M4RIE to Sage #9562

malb commented Jul 21, 2010

This comment has been minimized.

malb commented Jul 21, 2010

malb commented Jul 21, 2010

malb commented Jul 21, 2010

mwhansen commented Jul 21, 2010

malb commented Jul 21, 2010

malb commented Jul 21, 2010

sagetrac-drkirkby mannequin commented Jul 21, 2010

malb commented Jul 21, 2010

malb commented Jul 21, 2010

sagetrac-drkirkby mannequin commented Jul 21, 2010

malb commented Jul 21, 2010

mwhansen commented Jul 22, 2010

sagetrac-drkirkby mannequin commented Jul 22, 2010

malb commented Jul 22, 2010

sagetrac-drkirkby mannequin commented Jul 22, 2010

malb commented Jul 22, 2010

malb commented Jul 22, 2010

sagetrac-drkirkby mannequin commented Jul 22, 2010

malb commented Aug 10, 2010

simon-king-jena commented Oct 28, 2011

simon-king-jena commented Oct 28, 2011

simon-king-jena commented Oct 28, 2011

nexttime mannequin commented Oct 28, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 20, 2011

jdemeyer commented Nov 20, 2011

jdemeyer commented Dec 1, 2011

Add M4RIE to Sage #9562

Add M4RIE to Sage #9562

Comments

malb commented Jul 21, 2010

This comment has been minimized.

malb commented Jul 21, 2010

malb commented Jul 21, 2010

malb commented Jul 21, 2010

mwhansen commented Jul 21, 2010

malb commented Jul 21, 2010

malb commented Jul 21, 2010

sagetrac-drkirkby mannequin commented Jul 21, 2010

malb commented Jul 21, 2010

malb commented Jul 21, 2010

sagetrac-drkirkby mannequin commented Jul 21, 2010

malb commented Jul 21, 2010

mwhansen commented Jul 22, 2010

sagetrac-drkirkby mannequin commented Jul 22, 2010

malb commented Jul 22, 2010

sagetrac-drkirkby mannequin commented Jul 22, 2010

malb commented Jul 22, 2010

malb commented Jul 22, 2010

sagetrac-drkirkby mannequin commented Jul 22, 2010

malb commented Aug 10, 2010

simon-king-jena commented Oct 28, 2011

simon-king-jena commented Oct 28, 2011

simon-king-jena commented Oct 28, 2011

nexttime mannequin commented Oct 28, 2011

jdemeyer commented Nov 15, 2011

jdemeyer commented Nov 20, 2011

jdemeyer commented Nov 20, 2011

jdemeyer commented Dec 1, 2011