Sage: Ticket #12103: Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255`
https://trac.sagemath.org/ticket/12103
<p>
Sage has (or will soon have) fairly good implementations of dense matrices over <code>GF(2)</code>, over <code>GF(2^e)</code> (<a class="closed ticket" href="https://trac.sagemath.org/ticket/9562" title="enhancement: Add M4RIE to Sage (closed: fixed)">#9562</a>) and over <code>GF(p)</code> (p prime, <a class="closed ticket" href="https://trac.sagemath.org/ticket/4260" title="enhancement: use LinBox as native matrix representation for dense matrices over GF(p) (closed: fixed)">#4260</a>). However, it uses generic code for dense matrices over <code>GF(p^n)</code>, p odd, n>1, <code>p^n<255</code>.
</p>
<p>
I suggest to use a major modification of <code>MeatAxe Release 2.2.4</code> instead of the basic implementation. More on the modifications and the reason for choosing an old release is explained in the comments.
</p>
<p>
This is awfully slow:
</p>
<pre class="wiki">sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 6.36 s, sys: 0.02 s, total: 6.39 s
Wall time: 6.41 s
sage: type(A)
<type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
sage: B = MS.random_element()
sage: %time A*B # using 6.3% of my computer's memory
CPU times: user 744.20 s, sys: 1.18 s, total: 745.38 s
Wall time: 747.69 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
sage: %time ~A # using 10.4% of my computer's memory
CPU times: user 1096.74 s, sys: 1.30 s, total: 1098.05 s
Wall time: 1101.24 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
sage: %time A.echelon_form() # using 10.4% of my computer's memory
CPU times: user 378.62 s, sys: 0.33 s, total: 378.95 s
Wall time: 380.06 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
</pre><p>
With the optional spkg and the patch, one gets a clear improvement.
</p>
<pre class="wiki">sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 0.32 s, sys: 0.00 s, total: 0.32 s
Wall time: 0.33 s
sage: type(A)
<type 'sage.matrix.matrix_modpn_dense.Matrix_modpn_dense'>
sage: B = MS.random_element()
# The following uses Strassen-Winograd multiplication
sage: %time A*B # using 3.5% of my computer's memory
CPU times: user 7.68 s, sys: 0.01 s, total: 7.69 s
Wall time: 7.72 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
# The following is school book multiplication;
# that's more or less the original meataxe speed:
sage: %time A._multiply_classical(B) # using 3.6% of my computer's memory
CPU times: user 11.68 s, sys: 0.02 s, total: 11.70 s
Wall time: 11.73 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
# Strassen is not implemented for inversion and echelon form.
sage: %time ~A # using 3.8% of my computer's memory
CPU times: user 23.55 s, sys: 0.00 s, total: 23.55 s
Wall time: 23.62 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
sage: %time A.echelon_form() #using 3.9% of my computer's memory
CPU times: user 11.73 s, sys: 0.01 s, total: 11.74 s
Wall time: 11.78 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
</pre><p>
I think the component is "linear algebra", even though it is about an optional package.
</p>
<p>
<strong><span class="underline">How to install stuff</span></strong>
</p>
<ul><li>Apply the dependencies
</li><li>Install <a class="ext-link" href="http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg"><span class="icon"></span>the optional libmeataxe spkg</a>
</li><li>Apply either <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12103/" title="Attachments of Ticket #12103">attachment</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12103/" title="Download"></a> or <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12103/" title="Attachments of Ticket #12103">attachment</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12103/" title="Download"></a>, depending on whether or not you have <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> applied.
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12103
Trac 1.1.6SimonKingWed, 30 Nov 2011 13:28:11 GMTstatus, description changed
https://trac.sagemath.org/ticket/12103#comment:1
https://trac.sagemath.org/ticket/12103#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=1">diff</a>)
</li>
</ul>
<p>
Here is more on <code>libmeataxe-1.0.spkg</code>.
</p>
<p>
I started with Release 2.2.4 of the Aachen <code>C MeatAxe</code>. This is partially because I first came in touch with <code>MeatAxe</code> by old code of David Green, who was using the 2.2.3 release. <code>MeatAxe 2.2.4</code> was released under GPL2+, which should be fine. There are more recent releases. However, according to Michael Ringe, while the interface changed substantially, the linear algebra is more or less the same.
</p>
<p>
The spkg contains the unmodified sources in the folder <code>src/</code>, which is not under version control. The file <code>patches/libmeataxe.patch</code> provides my modification. Of course, if one installs the package, the patch will automatically be applied.
Here is a summary of my changes:
</p>
<ul><li>Normally, <code>MeatAxe</code> provides some executables that operate on matrices stored in files. I strip it down, such that the executables are not built and only a C library remains (this is <a class="ext-link" href="http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg"><span class="icon"></span>libmeataxe-1.0.spkg</a>). I wrap the C library using Cython (this is <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12103/trac12103_meataxe.patch" title="Attachment 'trac12103_meataxe.patch' in Ticket #12103">trac12103_meataxe.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12103/trac12103_meataxe.patch" title="Download"></a>)
</li><li><code>MeatAxe</code> uses school book multiplication. I added Strassen-Winograd multiplication, using a schedule that minimizes memory consumption. See <code>src/src/window.c</code>.
</li><li>The environment variable <code>MTXLIB</code> was supposed to tell <code>MeatAxe</code> where to find multiplication tables. However, this never worked for me. I fix it, so that now multiplication tables in <code>$SAGE_ROOT/local</code> are used, that are created when the package is installed.
</li><li>A simpler version of the package has been part of our group cohomology spkg. Bad experiences on Solaris made me change three names: I changed
<ul><li><code>T_STRING</code> into <code>T_STRINGS</code>,
</li><li>matextract into _matextract,
</li><li>matid into <code>MTXmatid</code>.
</li></ul></li></ul><blockquote>
<p>
Please don't ask me why the Solaris linker was mistaking these symbols with symbols in completely different Sage packages, but as a matter of fact it did.
</p>
</blockquote>
<p>
The aim of this ticket is to make the modified <code>MeatAxe</code> an optional back end for dense matrices over <code>GF(p^n)</code>, p>2 prime, n>1, <code>p^n<255</code>. Currently, one needs to install an spkg <em>and</em> a patch to the Sage library.
</p>
<p>
I would prefer to have it all in one, such that <code>sage -i libmeataxe-1.0.spkg</code> would automatically patch the Sage library. Question to Sage experts: Is that possible?
</p>
<p>
Anyway, I think it can be reviewed...
</p>
TicketSimonKingThu, 01 Dec 2011 11:23:02 GMTattachment set
https://trac.sagemath.org/ticket/12103
https://trac.sagemath.org/ticket/12103
<ul>
<li><strong>attachment</strong>
set to <em>trac12103_meataxe.patch</em>
</li>
</ul>
<p>
Use <code>MeatAxe</code> as back end for linear algebra over some finite fields.
</p>
TicketSimonKingThu, 01 Dec 2011 11:23:36 GMTattachment set
https://trac.sagemath.org/ticket/12103
https://trac.sagemath.org/ticket/12103
<ul>
<li><strong>attachment</strong>
set to <em>trac12103_meataxe_rel11900.patch</em>
</li>
</ul>
<p>
Use <code>MeatAxe</code> as back end for linear algebra over some finite fields. Relative to <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>
</p>
TicketSimonKingThu, 01 Dec 2011 11:25:11 GMT
https://trac.sagemath.org/ticket/12103#comment:2
https://trac.sagemath.org/ticket/12103#comment:2
<p>
I have updated both patches, because I wanted to add one method: <code>matrix_from_rows</code>. One could rely on the generic implementation, but in some application I need this to be fast:
</p>
<pre class="wiki"> sage: MS = MatrixSpace(GF(5^3,'y'),3,2)
sage: A = MS(range(6))
sage: A
[0 1]
[2 3]
[4 0]
sage: A.matrix_from_rows([2,1])
[4 0]
[2 3]
sage: A.matrix_from_rows([1,1])
[2 3]
[2 3]
</pre>
TicketSimonKingSat, 03 Mar 2012 14:02:57 GMTattachment set
https://trac.sagemath.org/ticket/12103
https://trac.sagemath.org/ticket/12103
<ul>
<li><strong>attachment</strong>
set to <em>trac12103_meataxe_docfix.patch</em>
</li>
</ul>
<p>
Fix one doctest (coping with a changed class name)
</p>
TicketSimonKingSat, 03 Mar 2012 14:06:11 GMTdescription changed
https://trac.sagemath.org/ticket/12103#comment:3
https://trac.sagemath.org/ticket/12103#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=3">diff</a>)
</li>
</ul>
<p>
Apparently there has been a name change <code>MatrixSpace_generic</code> to <code>MatrixSpace</code>. The result is one doctest failure in my original patch. I am not sure where that name change happened (perhaps it is in one of my patches that aren't in vanilla Sage yet). Therefore I added a second patch, that may or may not be necessary.
</p>
<p>
Apply trac12103_meataxe_rel11900.patch trac12103_meataxe_docfix.patch
</p>
TicketmalbSat, 03 Mar 2012 15:26:02 GMT
https://trac.sagemath.org/ticket/12103#comment:4
https://trac.sagemath.org/ticket/12103#comment:4
<p>
The patch applies neither cleanly to 4.8 nor 5.0.beta6. The issue 4.8 is small and easy to fix, 5.0.beta6 are a bit more failures.
</p>
TicketmalbSat, 03 Mar 2012 15:27:21 GMT
https://trac.sagemath.org/ticket/12103#comment:5
https://trac.sagemath.org/ticket/12103#comment:5
<p>
as of now module_list.py will try to build matrix_modpn_dense regardless of whether <a class="missing wiki">MeatAxe?</a> is installed, but it should only build it if <a class="missing wiki">MeatAxe?</a> is installed.
</p>
TicketSimonKingSat, 03 Mar 2012 16:12:35 GMT
https://trac.sagemath.org/ticket/12103#comment:6
https://trac.sagemath.org/ticket/12103#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:4" title="Comment 4">malb</a>:
</p>
<blockquote class="citation">
<p>
The patch applies neither cleanly to 4.8 nor 5.0.beta6. The issue 4.8 is small and easy to fix, 5.0.beta6 are a bit more failures.
</p>
</blockquote>
<p>
I get
</p>
<pre class="wiki">(sage subshell) mpc721:sage king$ hg qpush
applying trac12103_meataxe_rel11900.patch
patching file sage/modules/quotient_module.py
Hunk #12 succeeded at 297 with fuzz 1 (offset 10 lines).
Hunk #13 succeeded at 322 with fuzz 1 (offset 14 lines).
now at: trac12103_meataxe_rel11900.patch
SAGE_ROOT=/home/king/SAGE/sage-5.0.beta6
</pre><p>
So, I can not confirm that the first to-be-applied patch is really problematic (ok, fuzz 1 might be fixed at some point, but I don't get actual errors).
</p>
<p>
How can I test in module_list.py whether or not <code>MeatAxe</code> is installed? I suppose the patch to the sage library should not be applied by the installation script of the spkg.
</p>
TicketSimonKingSat, 03 Mar 2012 16:13:55 GMT
https://trac.sagemath.org/ticket/12103#comment:7
https://trac.sagemath.org/ticket/12103#comment:7
<p>
PS: Martin, did you really try to apply trac12103_meataxe_rel11900.patch? Namely, the previous patch (that is not relative to <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>) should be disregarded, as <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> is already merged.
</p>
TicketmalbSat, 03 Mar 2012 16:16:53 GMT
https://trac.sagemath.org/ticket/12103#comment:8
https://trac.sagemath.org/ticket/12103#comment:8
<p>
Ah, crap, 11900 was it.
</p>
<p>
RE: module_list.py I commented on it here: <a class="ext-link" href="https://bitbucket.org/malb/sagemath/pull-request/1/12103-meataxe-wrapper#comment-3510"><span class="icon"></span>https://bitbucket.org/malb/sagemath/pull-request/1/12103-meataxe-wrapper#comment-3510</a>
</p>
<p>
PS: Did you get my e-mail that I sent to simon.king<span class="underline">_uni-jena.de?
</span></p>
TicketSimonKingSat, 03 Mar 2012 16:20:34 GMTdescription changed
https://trac.sagemath.org/ticket/12103#comment:9
https://trac.sagemath.org/ticket/12103#comment:9
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=9">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:8" title="Comment 8">malb</a>:
</p>
<blockquote class="citation">
<p>
Ah, crap, 11900 was it.
</p>
</blockquote>
<p>
OK, I changed the instructions in the ticket description accordingly.
</p>
<blockquote class="citation">
<p>
RE: module_list.py I commented on it here: <a class="ext-link" href="https://bitbucket.org/malb/sagemath/pull-request/1/12103-meataxe-wrapper#comment-3510"><span class="icon"></span>https://bitbucket.org/malb/sagemath/pull-request/1/12103-meataxe-wrapper#comment-3510</a>
</p>
<p>
PS: Did you get my e-mail that I sent to simon.king<span class="underline">_uni-jena.de?
</span></p>
</blockquote>
<p>
Yes, but I didn't look at bitbucket yet, and I suppose I will not find the time to start and learn the new development before Monday.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/12103#comment:10
https://trac.sagemath.org/ticket/12103#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/12103#comment:11
https://trac.sagemath.org/ticket/12103#comment:11
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketrwsMon, 31 Mar 2014 07:53:54 GMTstatus changed
https://trac.sagemath.org/ticket/12103#comment:12
https://trac.sagemath.org/ticket/12103#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/12103#comment:13
https://trac.sagemath.org/ticket/12103#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/12103#comment:14
https://trac.sagemath.org/ticket/12103#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketSimonKingThu, 10 Sep 2015 16:18:57 GMT
https://trac.sagemath.org/ticket/12103#comment:15
https://trac.sagemath.org/ticket/12103#comment:15
<p>
I think this ticket should be revived. But the aim should be to have a library version of the *latest* MeatAxe upstream sources. And of course it should be a new-style package.
</p>
TicketSimonKingSat, 12 Sep 2015 11:24:47 GMTdescription changed
https://trac.sagemath.org/ticket/12103#comment:16
https://trac.sagemath.org/ticket/12103#comment:16
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=16">diff</a>)
</li>
</ul>
TicketSimonKingSat, 12 Sep 2015 11:35:10 GMTcc changed
https://trac.sagemath.org/ticket/12103#comment:17
https://trac.sagemath.org/ticket/12103#comment:17
<ul>
<li><strong>cc</strong>
<em>jdemeyer</em> <em>vbraun</em> added; <em>mringe@…</em> <em>david.green@…</em> removed
</li>
</ul>
<p>
The first step will probably be the creation of a new-style package for MeatAxe 2.4.24 (which I take as an exercise for learning new-style packaging).
</p>
<p>
The README file says:
</p>
<pre class="wiki">================================================================================
INSTALLATION (for Unix systems)
================================================================================
1) Copy Makefile.conf.dist to Makefile.conf. Edit Makefile.conf
and fill in the necessary parameters.
2) To compile all programs an run the test suite, enter
make check
You will probably need gmake (GNU make) to build the MeatAxe.
3) If there were no errors, run
make install
to install the executables in their final location (as selected
in the makefile).
</pre><p>
I wonder if we should follow that procedure. After all, <code>Makefile.conf.dist</code> just defines a couple of variables that determine the compiler, the flags, the location of the binaries, the location of the library and the implementation (for fields of order up to 255 or for larger fields).
</p>
<p>
What do people think?
</p>
<ol><li>a) Should we patch Makefile, by removing the line <code>include Makefile.conf</code>, and define all the variables MTXLIB, MTXBIN etc. from Makefile.conf as environment variables?
</li></ol><p>
or
</p>
<ol><li>b) Should we keep Makefile, create an empty Makefile.conf, and do the rest with environment variables?
</li></ol><p>
or
</p>
<ol start="2"><li>Should spkg-install first create a fully grown Makefile.conf?
</li></ol>
TicketvbraunSat, 12 Sep 2015 12:00:26 GMT
https://trac.sagemath.org/ticket/12103#comment:18
https://trac.sagemath.org/ticket/12103#comment:18
<p>
If all you have to do is <code>touch Makefile.conf</code> then I'd go for that.
</p>
TicketSimonKingSat, 12 Sep 2015 12:02:55 GMTcomponent changed
https://trac.sagemath.org/ticket/12103#comment:19
https://trac.sagemath.org/ticket/12103#comment:19
<ul>
<li><strong>component</strong>
changed from <em>linear algebra</em> to <em>packages: experimental</em>
</li>
</ul>
TicketSimonKingSat, 12 Sep 2015 12:46:01 GMT
https://trac.sagemath.org/ticket/12103#comment:20
https://trac.sagemath.org/ticket/12103#comment:20
<p>
I am slightly puzzled.
</p>
<p>
There is a variable ZZZ used in Makefile. But when I do
</p>
<pre class="wiki">ZZZ=0
$MAKE
</pre><p>
then apparently Makefile doesn't know about ZZZ. What do I need to do to define ZZZ so that Makefile knows about it?
</p>
TicketvbraunSat, 12 Sep 2015 12:57:49 GMT
https://trac.sagemath.org/ticket/12103#comment:21
https://trac.sagemath.org/ticket/12103#comment:21
<p>
Unless you <code>export ZZZ</code> it is not passed to subprocesses. Alternatively, you might want to use <code>$MAKE ZZZ=0</code>.
</p>
TicketSimonKingSat, 12 Sep 2015 14:30:41 GMT
https://trac.sagemath.org/ticket/12103#comment:22
https://trac.sagemath.org/ticket/12103#comment:22
<p>
Thanks, "export" did the trick.
</p>
<p>
However, I am afraid that some of the reasons for massively patching MeatAxe 2.2.4 are still present in version 2.4.24:
</p>
<ul><li>The environment variables MTXLIB and MTXBIN are ignored during build. I.e., the library is put into ./tmp/, the binaries are put into ./bin/
</li></ul><blockquote>
<p>
Suggested solution: Let spkg-install move the created binaries and libmtx.a to the desired location
</p>
</blockquote>
<ul><li><code>make clean</code> doesn't work, as it also goes into the directory test/ and calls <code>make clean</code> there---but there is no test/Makefile.
</li></ul><blockquote>
<p>
Not relevant here, as the build directory is deleted anyway.
</p>
</blockquote>
<ul><li><code>make check</code> rebuilds everything in ./tmp/ and ./bin/ before testing. Hence, the test suite actually does NOT test what is in $SAGE_ROOT/local/lib and $SAGE_ROOT/local/bin.
</li></ul><p>
Question on <code>make check</code>: Would it be OK to let spkg-install ALWAYS do <code>make check</code>? Or should that be solely the job of spkg-check (with the drawback that then spkg-check would rebuild meataxe)?
</p>
TicketSimonKingSat, 12 Sep 2015 14:32:59 GMT
https://trac.sagemath.org/ticket/12103#comment:23
https://trac.sagemath.org/ticket/12103#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:22" title="Comment 22">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Question on <code>make check</code>: Would it be OK to let spkg-install ALWAYS do <code>make check</code>? Or should that be solely the job of spkg-check (with the drawback that then spkg-check would rebuild meataxe)?
</p>
</blockquote>
<p>
Or should spkg-install test whether SAGE_CHECK=yes, and choose between <code>make</code> and <code>make check</code> accordingly?
</p>
TicketSimonKingSat, 12 Sep 2015 14:34:58 GMT
https://trac.sagemath.org/ticket/12103#comment:24
https://trac.sagemath.org/ticket/12103#comment:24
<p>
Do I understand correctly that for automatically downloading the sources from upstream, I should create spkg-src similarly to what I find in build/pkg/singular/spkg-src?
</p>
TicketSimonKingSat, 12 Sep 2015 14:51:15 GMT
https://trac.sagemath.org/ticket/12103#comment:25
https://trac.sagemath.org/ticket/12103#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:22" title="Comment 22">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
However, I am afraid that some of the reasons for massively patching MeatAxe 2.2.4 are still present in version 2.4.24:
</p>
</blockquote>
<p>
But one aspect has improved: MeatAxe used to rely on certain tables that were put (and when needed also created) in the current directory. And I had to patch the c-sources so that MeatAxe would be able to find the tables in a fixed directory. Now I cannot see any of these tables.
</p>
TicketjhpalmieriSat, 12 Sep 2015 15:22:31 GMT
https://trac.sagemath.org/ticket/12103#comment:26
https://trac.sagemath.org/ticket/12103#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:22" title="Comment 22">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Question on <code>make check</code>: Would it be OK to let spkg-install ALWAYS do <code>make check</code>? Or should that be solely the job of spkg-check (with the drawback that then spkg-check would rebuild meataxe)?
</p>
</blockquote>
<p>
In my opinion, if <code>make check</code> doesn't add too much time (a minute?) to the build, then you can always do it, but if it's more than that, it should be done only in <code>spkg-check</code>.
</p>
TicketvbraunSat, 12 Sep 2015 15:45:24 GMT
https://trac.sagemath.org/ticket/12103#comment:27
https://trac.sagemath.org/ticket/12103#comment:27
<p>
You don't need spkg-src, its just a bandaid to modify tarballs (don't do it if you can avoid it)
</p>
TicketSimonKingSat, 12 Sep 2015 16:06:45 GMTbranch set
https://trac.sagemath.org/ticket/12103#comment:28
https://trac.sagemath.org/ticket/12103#comment:28
<ul>
<li><strong>branch</strong>
set to <em>u/SimonKing/meataxe</em>
</li>
</ul>
TicketSimonKingSat, 12 Sep 2015 16:12:02 GMTdescription changed; commit set
https://trac.sagemath.org/ticket/12103#comment:29
https://trac.sagemath.org/ticket/12103#comment:29
<ul>
<li><strong>commit</strong>
set to <em>e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=29">diff</a>)
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d"><span class="icon"></span>e732f0e</a></td><td><code>An optional MeatAxe package</code>
</td></tr></table>
TicketSimonKingSat, 12 Sep 2015 16:15:01 GMT
https://trac.sagemath.org/ticket/12103#comment:30
https://trac.sagemath.org/ticket/12103#comment:30
<p>
Question on how to continue:
</p>
<p>
My aim is to provide a Cython wrapper, so, I need to copy meataxe.h to some include location.
</p>
<p>
But how to deal with the Cython wrapper? Apparently it would be in the Sage library, but apparently it will not compile if meataxe is not installed.
</p>
<p>
So, should the package install the cython code into the Sage library? Or is it possible to have code permanently in the Sage library that is only compiled if a certain package is installed, and otherwise is left untouched?
</p>
TicketSimonKingSat, 12 Sep 2015 16:16:10 GMT
https://trac.sagemath.org/ticket/12103#comment:31
https://trac.sagemath.org/ticket/12103#comment:31
<p>
PS: Note that MeatAxe has a nice documentation, and as usual it is installed if SAGE_SPKG_INSTALL_DOCS=yes.
</p>
TicketSimonKingSun, 13 Sep 2015 08:54:27 GMT
https://trac.sagemath.org/ticket/12103#comment:32
https://trac.sagemath.org/ticket/12103#comment:32
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:25" title="Comment 25">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
But one aspect has improved: MeatAxe used to rely on certain tables that were put (and when needed also created) in the current directory. And I had to patch the c-sources so that MeatAxe would be able to find the tables in a fixed directory. Now I cannot see any of these tables.
</p>
</blockquote>
<p>
I am afraid I stand corrected. Meanwhile I have a Cython wrapper on my laptop, and when I create a matrix over GF(2), then a file p002.zzz (defining multiplication table) is created in the current directory.
</p>
<p>
That's a very nasty property of MeatAxe. What shall we do about it?
</p>
<p>
Shall we leave it like that?
</p>
<p>
Shall I try to port my patch from 2.2.4 to 2.4.24 and ensure that all multiplication tables should be created in SAGE_ROOT/local/lib/meataxe/?
</p>
TicketSimonKingSun, 13 Sep 2015 09:09:36 GMT
https://trac.sagemath.org/ticket/12103#comment:33
https://trac.sagemath.org/ticket/12103#comment:33
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:32" title="Comment 32">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Shall I try to port my patch from 2.2.4 to 2.4.24 and ensure that all multiplication tables should be created in SAGE_ROOT/local/lib/meataxe/?
</p>
</blockquote>
<p>
If "yes": Where shall the tables be placed? In SAGE_LOCAL/share/meataxe/ perhaps?
</p>
TicketSimonKingSun, 13 Sep 2015 09:39:46 GMT
https://trac.sagemath.org/ticket/12103#comment:34
https://trac.sagemath.org/ticket/12103#comment:34
<p>
From the MeatAxe sources:
</p>
<pre class="wiki">/**
** MeatAxe Library Directory.
** This variable contains the name of the MeatAxe library directory.
** Arithmetic table files are searched in this directory. The value of
** MtxLibDir can be set on the command line with the "-L" option. Otherwise,
** the value of the environment variable MTXLIB is used. If neither "-L" nor
** MTXLIB are defined, the default directory, which was selected when
** building the MeatAxe, is used.
** @see MtxBinDir
**/
</pre><p>
So, apparently the multiplication tables are supposed to be in MTXLIB. But that has NEVER worked for me.
</p>
<p>
Or rather, it could be that MTXLIB has to be an environment variable at running time. Would it be acceptable that a module <code>sage.matrix.meataxe</code> sets an environment variable for MeatAxe? I'll test if that works.
</p>
TicketSimonKingSun, 13 Sep 2015 09:40:27 GMT
https://trac.sagemath.org/ticket/12103#comment:35
https://trac.sagemath.org/ticket/12103#comment:35
<p>
PS: It says "Otherwise, the value of the environment variable MTXLIB is used."
That definitely does not work.
</p>
TicketSimonKingSun, 13 Sep 2015 10:00:01 GMT
https://trac.sagemath.org/ticket/12103#comment:36
https://trac.sagemath.org/ticket/12103#comment:36
<p>
Setting the environment variable at running time doesn't work either. That's a bug that has always been present in MeatAxe. So, I guess I need to patch the sources.
</p>
TicketSimonKingSun, 13 Sep 2015 10:08:49 GMT
https://trac.sagemath.org/ticket/12103#comment:37
https://trac.sagemath.org/ticket/12103#comment:37
<p>
Internally, MeatAxe stores MTXLIB in <a class="missing wiki">MtxLibDir?</a>. But directly defining <a class="missing wiki">MtxLibDir?</a> at run time didn't help. Sigh.
</p>
TicketgitSun, 13 Sep 2015 15:12:44 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:38
https://trac.sagemath.org/ticket/12103#comment:38
<ul>
<li><strong>commit</strong>
changed from <em>e732f0ee8fa0dc631f9cffd62b4dd1f6f2c10c2d</em> to <em>6c324700abeb37c3e32ebf36c7cf9027c8e70588</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=71c9b94528958c9d91ac0ebc71c921979e896542"><span class="icon"></span>71c9b94</a></td><td><code>Install meataxe header; no separate meataxe folder in SAGE_LOCAL/lib/</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0320de92d30e5f603bdfedaf4a7a262eee93ac70"><span class="icon"></span>0320de9</a></td><td><code>Declare that meataxe is an optional package</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e0ca6d08d291becd2e2950ff5e4807f2ce56a578"><span class="icon"></span>e0ca6d0</a></td><td><code>Use -fPIC for creating libmtx.a</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6e6cdd84fc3a830af0e68fbb3c419a9b54d955ff"><span class="icon"></span>6e6cdd8</a></td><td><code>Choose a location for multiplication tables</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6c324700abeb37c3e32ebf36c7cf9027c8e70588"><span class="icon"></span>6c32470</a></td><td><code>Patch MeatAxe so that MTXLIB is used to store library files</code>
</td></tr></table>
TicketjhpalmieriSun, 13 Sep 2015 15:21:50 GMT
https://trac.sagemath.org/ticket/12103#comment:39
https://trac.sagemath.org/ticket/12103#comment:39
<p>
You shouldn't assume that the Sage directory is writeable. So the multiplication tables should be stored in <code>SAGE_TMP</code> or (if you want to keep them) in some other subdirectory of <code>DOT_SAGE</code>, probably <code>DOT_SAGE/meataxe-2.4.24/</code>.
</p>
TicketSimonKingSun, 13 Sep 2015 15:22:48 GMT
https://trac.sagemath.org/ticket/12103#comment:40
https://trac.sagemath.org/ticket/12103#comment:40
<p>
Recent changes:
</p>
<ul><li>Since we want to wrap the code, it is needed to make the meataxe header available.
</li><li>I found that packages are supposed to give a file called "type". I declare there that the package is supposed to be optional.
</li><li>Since we move libmtx.a from a temporary location to somewhere in SAGE_LOCAL, it is needed to use "-fPIC".
</li><li>The multiplication tables shouldn't pollute the user's current directory. I propose to store them in SAGE_SHARE/meataxe/.
</li><li>MeatAxe has IO-functions that accept an argument saying that the file is a library file---but in the IO-functions, it is always first looked into the current directory, and the library location is only considered if the current directory didn't work.
</li><li>In at least one function, the IO-argument for "library files" is used wrongly. So, after fixing the IO-function, the wrong argument needed to be fixed, too.
</li></ul><p>
In meataxe/patches is a patch that fixes these two upstream bugs.
</p>
<p>
Current status:
</p>
<ul><li>The package builds fine.
</li><li>When running the testsuite, I sometimes see a wrong checksum, but when I repeat the testsuite, everything is fine. I guess upstream's checksum function is fragile. Not sure if I'm going to fix that.
</li><li>With the Cython wrapper on my laptop, I can create MeatAxe matrices in a Sage session, and the current directory is not polluted by multiplication tables.
</li></ul><p>
TODO:
</p>
<ul><li>Finish the Cython wrapper.
</li></ul>
TicketSimonKingSun, 13 Sep 2015 15:23:46 GMT
https://trac.sagemath.org/ticket/12103#comment:41
https://trac.sagemath.org/ticket/12103#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:39" title="Comment 39">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
You shouldn't assume that the Sage directory is writeable. So the multiplication tables should be stored in <code>SAGE_TMP</code> or (if you want to keep them) in some other subdirectory of <code>DOT_SAGE</code>, probably <code>DOT_SAGE/meataxe-2.4.24/</code>.
</p>
</blockquote>
<p>
Right, that could be a problem. The tables should indeed be permanent. So, <code>DOT_SAGE/meataxe</code> (without version number) it is.
</p>
TicketgitSun, 13 Sep 2015 15:27:36 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:42
https://trac.sagemath.org/ticket/12103#comment:42
<ul>
<li><strong>commit</strong>
changed from <em>6c324700abeb37c3e32ebf36c7cf9027c8e70588</em> to <em>d9675fbca6cf8647548f6f37522d2c388812669d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d9675fbca6cf8647548f6f37522d2c388812669d"><span class="icon"></span>d9675fb</a></td><td><code>Use DOT_SAGE, not SAGE_LOCAL, for storing multiplication tables</code>
</td></tr></table>
TicketjhpalmieriSun, 13 Sep 2015 15:38:14 GMT
https://trac.sagemath.org/ticket/12103#comment:43
https://trac.sagemath.org/ticket/12103#comment:43
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:41" title="Comment 41">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:39" title="Comment 39">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
You shouldn't assume that the Sage directory is writeable. So the multiplication tables should be stored in <code>SAGE_TMP</code> or (if you want to keep them) in some other subdirectory of <code>DOT_SAGE</code>, probably <code>DOT_SAGE/meataxe-2.4.24/</code>.
</p>
</blockquote>
<p>
Right, that could be a problem. The tables should indeed be permanent. So, <code>DOT_SAGE/meataxe</code> (without version number) it is.
</p>
</blockquote>
<p>
As long as you're pretty confident that the tables will be compatible with future versions. (We ran into this problem with <code>IPython</code> and <code>matplotlib</code>, which is why their directories in <code>DOT_SAGE</code> include the version number.)
</p>
TicketSimonKingSun, 13 Sep 2015 15:42:44 GMT
https://trac.sagemath.org/ticket/12103#comment:44
https://trac.sagemath.org/ticket/12103#comment:44
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:43" title="Comment 43">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
As long as you're pretty confident that the tables will be compatible with future versions. (We ran into this problem with <code>IPython</code> and <code>matplotlib</code>, which is why their directories in <code>DOT_SAGE</code> include the version number.)
</p>
</blockquote>
<p>
The format hasn't changed since version 2.2.3, and the current version already is 4 years old. So, I don't think there will be changes any time soon.
</p>
<p>
Moreover, if we really need to change it, we can create all multiplication tables (we have bounded field size) in a fraction of a second during package installation.
</p>
TicketSimonKingSun, 13 Sep 2015 15:44:29 GMT
https://trac.sagemath.org/ticket/12103#comment:45
https://trac.sagemath.org/ticket/12103#comment:45
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:44" title="Comment 44">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Moreover, if we really need to change it, we can create all multiplication tables (we have bounded field size) in a fraction of a second during package installation.
</p>
</blockquote>
<p>
Aaahm, if we use SAGE_SHARE.
</p>
<p>
Anyway, if things really go bad in future meataxe versions, it should be possible to patch it so that invalid old multiplication tables are automatically removed when accidentally opening them.
</p>
TicketSimonKingSun, 13 Sep 2015 18:26:36 GMTdescription changed
https://trac.sagemath.org/ticket/12103#comment:46
https://trac.sagemath.org/ticket/12103#comment:46
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=46">diff</a>)
</li>
</ul>
TicketgitFri, 18 Sep 2015 08:39:29 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:47
https://trac.sagemath.org/ticket/12103#comment:47
<ul>
<li><strong>commit</strong>
changed from <em>d9675fbca6cf8647548f6f37522d2c388812669d</em> to <em>20a16e18db945d6e123f457a44ee5835427a1351</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=20a16e18db945d6e123f457a44ee5835427a1351"><span class="icon"></span>20a16e1</a></td><td><code>Implement and use Strassen-Winograd matrix multiplication in MeatAxe</code>
</td></tr></table>
TicketSimonKingFri, 18 Sep 2015 10:41:49 GMT
https://trac.sagemath.org/ticket/12103#comment:48
https://trac.sagemath.org/ticket/12103#comment:48
<p>
In the recent commit, patches <code>StrassenWinogradImplementation.patch</code> and <code>StrassenWinogradUsage.patch</code> are provided.
</p>
<p>
There, I implement the Winograd-Strassen multiplication algorithm in MeatAxe. I optimized the cutoff parameter using a Cython wrapper that I didn't post yet (needs doctests and needs to wrap echelonisation).
</p>
<p>
I tested on matrices of different sizes and different fields. First of all, the school book multiplication in MeatAxe is vastly faster than the current matrix multiplication in Sage for all non-prime finite fields of odd characteristic (of course with field order < 256).
</p>
<p>
Moreover, it turns out that the Winograd-Strassen implementation is not only asymptotically fast, but even on small examples (200x200) is as fast as MeatAxe's school book multiplication. So, I think it makes sense to use it not only in my Cython wrapper but also in the MeatAxe functions/executables, which is done in <code>StrassenWinogradUsage.patch</code>.
</p>
<p>
The fact that MeatAxe's test suite still works is an indicative that my Winograd-Strassen implementation ok.
</p>
<p>
Of course it will be even clearer in the Cython wrapper that will be subject of the next commit. Then, I'll show timings.
</p>
TicketjdemeyerFri, 18 Sep 2015 11:09:55 GMT
https://trac.sagemath.org/ticket/12103#comment:49
https://trac.sagemath.org/ticket/12103#comment:49
<p>
The tarball is badly made: there should be top-level directory like <code>meataxe-2.4.24</code> with everything contained in that directory.
</p>
<p>
Also, we no longer list maintainers in <code>SPKG.txt</code> (<a class="closed ticket" href="https://trac.sagemath.org/ticket/19238" title="enhancement: Remove the "SPKG Maintainers" section in packages and doc (closed: fixed)">#19238</a>)
</p>
TicketjdemeyerFri, 18 Sep 2015 11:11:59 GMT
https://trac.sagemath.org/ticket/12103#comment:50
https://trac.sagemath.org/ticket/12103#comment:50
<p>
Patches need to be documented (preferably in the patch itself). In particular: where do the patches come from?
</p>
TicketSimonKingFri, 18 Sep 2015 11:17:37 GMT
https://trac.sagemath.org/ticket/12103#comment:51
https://trac.sagemath.org/ticket/12103#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:49" title="Comment 49">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
The tarball is badly made:
</p>
</blockquote>
<p>
Complain to upstream. The tarball is directly from their website. I'm not going to fix that.
</p>
TicketSimonKingFri, 18 Sep 2015 11:30:00 GMT
https://trac.sagemath.org/ticket/12103#comment:52
https://trac.sagemath.org/ticket/12103#comment:52
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:50" title="Comment 50">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Patches need to be documented (preferably in the patch itself).
</p>
</blockquote>
<p>
Right, I did so (if I recall correctly) for the first patch concerning IO-fixes, but failed for the other two.
</p>
<blockquote class="citation">
<p>
In particular: where do the patches come from?
</p>
</blockquote>
<p>
My name suffices?
</p>
TicketSimonKingFri, 18 Sep 2015 11:31:50 GMT
https://trac.sagemath.org/ticket/12103#comment:53
https://trac.sagemath.org/ticket/12103#comment:53
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:51" title="Comment 51">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:49" title="Comment 49">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
The tarball is badly made:
</p>
</blockquote>
<p>
Complain to upstream. The tarball is directly from their website. I'm not going to fix that.
</p>
</blockquote>
<p>
Or would it be ok to repack the upstream tarball? I thought the purpose of the new-style packages is to use clean upstream sources?
</p>
TicketSimonKingFri, 18 Sep 2015 11:40:49 GMT
https://trac.sagemath.org/ticket/12103#comment:54
https://trac.sagemath.org/ticket/12103#comment:54
<p>
I guess nobody except myself uses the branch. Hence, I will rebase and force-push the changes requested by Jeroen, unless someone tells me not to.
</p>
TicketjdemeyerFri, 18 Sep 2015 11:50:09 GMT
https://trac.sagemath.org/ticket/12103#comment:55
https://trac.sagemath.org/ticket/12103#comment:55
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:53" title="Comment 53">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Or would it be ok to repack the upstream tarball?
</p>
</blockquote>
<p>
Yes. In this case, it is clearly needed.
</p>
<p>
I am going to complain to upstream by the way.
</p>
TicketjdemeyerFri, 18 Sep 2015 11:55:26 GMT
https://trac.sagemath.org/ticket/12103#comment:56
https://trac.sagemath.org/ticket/12103#comment:56
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:52" title="Comment 52">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
My name suffices?
</p>
</blockquote>
<p>
Yes, it should somehow be clear that you wrote the patch, that it's not an official patch from upstream. Have the patches been submitted upstream? They should be!
</p>
TicketjdemeyerFri, 18 Sep 2015 11:58:26 GMT
https://trac.sagemath.org/ticket/12103#comment:57
https://trac.sagemath.org/ticket/12103#comment:57
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:54" title="Comment 54">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Hence, I will rebase and force-push the changes requested by Jeroen, unless someone tells me not to.
</p>
</blockquote>
<p>
Go ahead. If you're rebasing, you might as well squash everything in one commit (with the <code>f</code> option in <code>git rebase -i</code>)
</p>
TicketSimonKingFri, 18 Sep 2015 12:02:53 GMT
https://trac.sagemath.org/ticket/12103#comment:58
https://trac.sagemath.org/ticket/12103#comment:58
<p>
After replacing the old tarball by a new one called <code>meataxe-2.4.24.p0.tar.gz</code>, I did <code>./sage -fix-pkg-checksums</code>. However, it did not produce a new <code>checksum.ini</code> in <code>build/pkgs/meataxe/</code>.
</p>
<p>
What can I do now?
</p>
TicketSimonKingFri, 18 Sep 2015 12:05:32 GMT
https://trac.sagemath.org/ticket/12103#comment:59
https://trac.sagemath.org/ticket/12103#comment:59
<p>
Aha. Apparently it was needed to call it <code>meataxe-2.4.24.tar.gz</code> without .p0.
</p>
TicketgitFri, 18 Sep 2015 12:32:26 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:60
https://trac.sagemath.org/ticket/12103#comment:60
<ul>
<li><strong>commit</strong>
changed from <em>20a16e18db945d6e123f457a44ee5835427a1351</em> to <em>a722d4e9b8208f900c7850e8ddf8adda2e297550</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=dea8e06007fdc724da42c4fd34edb3e5e76f3e87"><span class="icon"></span>dea8e06</a></td><td><code>An optional MeatAxe package</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a722d4e9b8208f900c7850e8ddf8adda2e297550"><span class="icon"></span>a722d4e</a></td><td><code>Implement and use Strassen-Winograd matrix multiplication in MeatAxe</code>
</td></tr></table>
TicketSimonKingFri, 18 Sep 2015 12:34:08 GMTattachment set
https://trac.sagemath.org/ticket/12103
https://trac.sagemath.org/ticket/12103
<ul>
<li><strong>attachment</strong>
set to <em>meataxe-2.4.24.tar.gz</em>
</li>
</ul>
<p>
Repackaged upstream sources
</p>
TicketSimonKingFri, 18 Sep 2015 12:35:12 GMTdescription changed
https://trac.sagemath.org/ticket/12103#comment:61
https://trac.sagemath.org/ticket/12103#comment:61
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12103?action=diff&version=61">diff</a>)
</li>
</ul>
TicketSimonKingFri, 18 Sep 2015 12:40:37 GMT
https://trac.sagemath.org/ticket/12103#comment:62
https://trac.sagemath.org/ticket/12103#comment:62
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:57" title="Comment 57">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Go ahead. If you're rebasing, you might as well squash everything in one commit (with the <code>f</code> option in <code>git rebase -i</code>)
</p>
</blockquote>
<p>
Done. I kept two commits of largely different purpose. The first makes MeatAxe build and install its tables into <code>DOT_SAGE</code>. The second commit implements and uses Winograd-Strassen multiplication in MeatAxe.
</p>
<p>
The self-tests (by <code>sage -f -c meataxe</code>) should pass. I don't know why they are a little flaky. Perhaps a race condition? Anyway, I think that's an upstream problem. Most of the time, the self-tests just pass fine.
</p>
<p>
The third commit will be cython wrapper for MeatAxe with which I can demonstrate that things work correct and very fast. And then I have to deal with doctests.
</p>
TicketjdemeyerFri, 18 Sep 2015 12:45:38 GMTdependencies deleted
https://trac.sagemath.org/ticket/12103#comment:63
https://trac.sagemath.org/ticket/12103#comment:63
<ul>
<li><strong>dependencies</strong>
<em>#9562 #4260</em> deleted
</li>
</ul>
TicketSimonKingFri, 18 Sep 2015 12:49:21 GMTdependencies set
https://trac.sagemath.org/ticket/12103#comment:64
https://trac.sagemath.org/ticket/12103#comment:64
<ul>
<li><strong>dependencies</strong>
set to <em>#9562 #4260</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:56" title="Comment 56">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:52" title="Comment 52">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
My name suffices?
</p>
</blockquote>
<p>
Yes, it should somehow be clear that you wrote the patch, that it's not an official patch from upstream. Have the patches been submitted upstream? They should be!
</p>
</blockquote>
<p>
Long time ago, I have submitted a Winograd-Strassen patch for version 2.2.4 to upstream. But too much has changed since version 2.2.4, the old patches are useless.
</p>
<p>
But for sure it makes sense to submit the new three patches to upstream. Even the first one is useful. I wonder why upstream keeps telling that multiplication tables are stored in <code>MTX_LIB</code> when in the last 10 years they have always been installed in the current directory.
</p>
TicketgitFri, 18 Sep 2015 12:59:43 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:65
https://trac.sagemath.org/ticket/12103#comment:65
<ul>
<li><strong>commit</strong>
changed from <em>a722d4e9b8208f900c7850e8ddf8adda2e297550</em> to <em>539b1349359004b78712a67d2739cce9ce0227da</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=539b1349359004b78712a67d2739cce9ce0227da"><span class="icon"></span>539b134</a></td><td><code>A very basic MeatAxe Cython wrapper</code>
</td></tr></table>
TicketjdemeyerFri, 18 Sep 2015 13:06:47 GMT
https://trac.sagemath.org/ticket/12103#comment:66
https://trac.sagemath.org/ticket/12103#comment:66
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:64" title="Comment 64">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Long time ago, I have submitted a Winograd-Strassen patch for version 2.2.4 to upstream. But too much has changed since version 2.2.4, the old patches are useless.
</p>
</blockquote>
<p>
I don't understand. In this ticket, you are adding patches to a package which you claim yourself are useless???
</p>
TicketSimonKingFri, 18 Sep 2015 13:07:50 GMT
https://trac.sagemath.org/ticket/12103#comment:67
https://trac.sagemath.org/ticket/12103#comment:67
<p>
The last commit really isn't finished yet (most tests and much documentation is missing). But for now it is enough to demonstrate the progress compared with the current Sage beta.
</p>
<p>
Please make sure that you use <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12103/meataxe-2.4.24.tar.gz" title="Attachment 'meataxe-2.4.24.tar.gz' in Ticket #12103">attachment:meataxe-2.4.24.tar.gz</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12103/meataxe-2.4.24.tar.gz" title="Download"></a>, not the source tarball from the upstream download page.
</p>
<p>
In the latest development version, we have
</p>
<pre class="wiki">sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 6.71 s, sys: 20 ms, total: 6.73 s
Wall time: 6.79 s
sage: type(A)
<type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
sage: B = MS.random_element()
sage: %time A*B
CPU times: user 23min 49s, sys: 490 ms, total: 23min 50s
Wall time: 23min 55s # using 7.5% of my computer's memory
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the '.str()' method to see the entries)
sage: %time ~A
CPU times: user 23min 42s, sys: 842 ms, total: 23min 43s
Wall time: 23min 47s # using 11.3% of my computer's memory
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the '.str()' method to see the entries)
</pre><p>
23 minutes for a single multiplication or inversion of a not so big matrix over a small field!!
</p>
<p>
You see why I see the need of a different backend?
</p>
<p>
Here is the same example when the optional meataxe package (and its wrapper) is used:
</p>
<pre class="wiki">sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 320 ms, sys: 5 ms, total: 325 ms
Wall time: 351 ms
sage: type(A)
<type 'sage.matrix.matrix_modpn_dense.Matrix_modpn_dense'>
sage: B = MS.random_element()
sage: %time A*B # using 4.8% of my computer's memory
CPU times: user 14.4 s, sys: 1 ms, total: 14.4 s
Wall time: 14.4 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the '.str()' method to see the entries)
sage: %time ~A # using 5.9% of my computer's memory
CPU times: user 32.7 s, sys: 69 ms, total: 32.8 s
Wall time: 33.2 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3 (use the '.str()' method to see the entries)
sage: %time _*A == A*_ == 1
CPU times: user 28.7 s, sys: 60 ms, total: 28.8 s
Wall time: 29 s
True
</pre><p>
The last example indicates that the (Strassen) multiplication is vastly faster than what we have now in Sage.
</p>
<p>
Admittedly, the patched MeatAxe is still a lot slower than linbox for prime fields or M4RIE for characteristic 2. That's why I only suggest to use it for non-prime fields of odd characteristic.
</p>
<p>
By the way, MeatAxe is supposed to have a different kernel for fields of size > 255. But strangely, the respective source file is not in the upstream source tarball.
</p>
TicketjdemeyerFri, 18 Sep 2015 13:09:14 GMT
https://trac.sagemath.org/ticket/12103#comment:68
https://trac.sagemath.org/ticket/12103#comment:68
<p>
The meataxe part of <code>src/sage/matrix/matrix_modpn_dense.pxd</code> should probably be moved to <code>src/sage/libs/meataxe.pxd</code> or <code>src/sage/libs/meataxe/multiple_files_here.pxd</code>
</p>
<p>
Also, can you use the standard heading template from <a class="ext-link" href="http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files"><span class="icon"></span>http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files</a>
</p>
TicketSimonKingFri, 18 Sep 2015 13:09:32 GMT
https://trac.sagemath.org/ticket/12103#comment:69
https://trac.sagemath.org/ticket/12103#comment:69
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:66" title="Comment 66">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:64" title="Comment 64">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Long time ago, I have submitted a Winograd-Strassen patch for version 2.2.4 to upstream. But too much has changed since version 2.2.4, the old patches are useless.
</p>
</blockquote>
<p>
I don't understand. In this ticket, you are adding patches to a package which you claim yourself are useless???
</p>
</blockquote>
<p>
The patches FOR THE OLD VERSION 2.2.4 that I send to upstream a couple of years ago are useless FOR THE CURRENT VERSION 2.4.24. All function and struct names in MeatAxe have changed between version 2.2.4 and 2.4.24.
</p>
TicketjdemeyerFri, 18 Sep 2015 13:11:23 GMT
https://trac.sagemath.org/ticket/12103#comment:70
https://trac.sagemath.org/ticket/12103#comment:70
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:69" title="Comment 69">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
The patches FOR THE OLD VERSION 2.2.4 that I send to upstream a couple of years ago are useless FOR THE CURRENT VERSION 2.4.24. All function and struct names in MeatAxe have changed between version 2.2.4 and 2.4.24.
</p>
</blockquote>
<p>
OK, but does it make sense to send the <em>new</em> patches to upstream again?
</p>
TicketSimonKingFri, 18 Sep 2015 13:13:04 GMT
https://trac.sagemath.org/ticket/12103#comment:71
https://trac.sagemath.org/ticket/12103#comment:71
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:68" title="Comment 68">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
<code>src/sage/matrix/matrix_modpn_dense.pxd</code> should probably be moved to <code>src/sage/libs/meataxe.pxd</code> or <code>src/sage/libs/meataxe/multiple_files_here.pxd</code>
</p>
</blockquote>
<p>
I don't think that meataxe.pxd is a good name. It is a dense implementation for matrices over <code>GF(p^n)</code>, and thus it is <code>matrix_modpn_dense.pxd</code>. This is totally analogous to <code>matrix_mod2e_dense.pxd</code>; or do you suggest to rename the latter by <code>m4rie.pxd</code>?
</p>
<blockquote class="citation">
<p>
Also, can you use the standard heading template from <a class="ext-link" href="http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files"><span class="icon"></span>http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files</a>
</p>
</blockquote>
<p>
I think I have copied the heading from some existing pxd files. But I can change it.
</p>
TicketjdemeyerFri, 18 Sep 2015 13:13:30 GMT
https://trac.sagemath.org/ticket/12103#comment:72
https://trac.sagemath.org/ticket/12103#comment:72
<p>
If I understand things correctly, the <code>modpn</code> in the filename refers to a finite field of size <code>p^n</code>, right? That's a very confusing name, can you use <code>matrix_gfpn_dense.pyx</code> or something?
</p>
TicketSimonKingFri, 18 Sep 2015 13:14:12 GMT
https://trac.sagemath.org/ticket/12103#comment:73
https://trac.sagemath.org/ticket/12103#comment:73
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:70" title="Comment 70">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:69" title="Comment 69">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
The patches FOR THE OLD VERSION 2.2.4 that I send to upstream a couple of years ago are useless FOR THE CURRENT VERSION 2.4.24. All function and struct names in MeatAxe have changed between version 2.2.4 and 2.4.24.
</p>
</blockquote>
<p>
OK, but does it make sense to send the <em>new</em> patches to upstream again?
</p>
</blockquote>
<p>
As I said in <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:64" title="Comment 64">comment:64</a>: "But for sure it makes sense to submit the new three patches to upstream."
</p>
TicketjdemeyerFri, 18 Sep 2015 13:16:10 GMT
https://trac.sagemath.org/ticket/12103#comment:74
https://trac.sagemath.org/ticket/12103#comment:74
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:71" title="Comment 71">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
This is totally analogous to <code>matrix_mod2e_dense.pxd</code>; or do you suggest to rename the latter by <code>m4rie.pxd</code>?
</p>
</blockquote>
<p>
That file actually exists: <code>src/sage/libs/m4rie.pxd</code>
</p>
<p>
It's cimported by <code>matrix_mod2e_dense.pxd</code>, which is what you should do for meataxe also: separate the Sage matrix stuff from the meataxe library stuff.
</p>
TicketjdemeyerFri, 18 Sep 2015 13:16:39 GMTdependencies deleted
https://trac.sagemath.org/ticket/12103#comment:75
https://trac.sagemath.org/ticket/12103#comment:75
<ul>
<li><strong>dependencies</strong>
<em>#9562 #4260</em> deleted
</li>
</ul>
TicketSimonKingFri, 18 Sep 2015 13:17:36 GMTdependencies set
https://trac.sagemath.org/ticket/12103#comment:76
https://trac.sagemath.org/ticket/12103#comment:76
<ul>
<li><strong>dependencies</strong>
set to <em>#9562 #4260</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:72" title="Comment 72">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
If I understand things correctly, the <code>modpn</code> in the filename refers to a finite field of size <code>p^n</code>, right? That's a very confusing name, can you use <code>matrix_gfpn_dense.pyx</code> or something?
</p>
</blockquote>
<p>
Do you suggest to rename Martin Albrecht's <code>matrix_mod2e_dense.pyx</code> to <code>matrix_gf2e_dense.pyx</code>? By the way, IIRC that's where I got the heading from.
</p>
<p>
I think we should be consistent with the existing naming scheme. We currently have <code>matrix_modn_dense</code>, <code>matrix_mod2_dense</code>, <code>matrix_mod2e_dense</code>, and the obvious continuation of that scheme is <code>matrix_modpn_dense</code>.
</p>
TicketSimonKingFri, 18 Sep 2015 13:19:37 GMT
https://trac.sagemath.org/ticket/12103#comment:77
https://trac.sagemath.org/ticket/12103#comment:77
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:74" title="Comment 74">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:71" title="Comment 71">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
This is totally analogous to <code>matrix_mod2e_dense.pxd</code>; or do you suggest to rename the latter by <code>m4rie.pxd</code>?
</p>
</blockquote>
<p>
That file actually exists: <code>src/sage/libs/m4rie.pxd</code>
</p>
</blockquote>
<p>
Aha! Now I understand.
</p>
<p>
OK, that makes more sense. Have a <code>src/sage/libs/meataxe.pxd</code> without a corresponding <code>.pyx</code> file, and do the rest in <code>src/sage/matrix/matrix_modpn_dense.p??</code>, which imports from <code>sage.libs.meataxe</code>.
</p>
TicketjdemeyerFri, 18 Sep 2015 13:24:10 GMT
https://trac.sagemath.org/ticket/12103#comment:78
https://trac.sagemath.org/ticket/12103#comment:78
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:76" title="Comment 76">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Do you suggest to rename Martin Albrecht's <code>matrix_mod2e_dense.pyx</code> to <code>matrix_gf2e_dense.pyx</code>?
</p>
</blockquote>
<p>
Yes!! It's a very confusing name.
</p>
TicketjdemeyerFri, 18 Sep 2015 13:25:17 GMTdependencies deleted
https://trac.sagemath.org/ticket/12103#comment:79
https://trac.sagemath.org/ticket/12103#comment:79
<ul>
<li><strong>dependencies</strong>
<em>#9562 #4260</em> deleted
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:77" title="Comment 77">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Have a <code>src/sage/libs/meataxe.pxd</code> without a corresponding <code>.pyx</code> file, and do the rest in <code>src/sage/matrix/matrix_modpn_dense.p??</code>, which imports from <code>sage.libs.meataxe</code>.
</p>
</blockquote>
<p>
Yes, exactly. It's good practice to separate the library (which has nothing to do with Sage) from the Sage interface.
</p>
TicketgitFri, 18 Sep 2015 13:30:10 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:80
https://trac.sagemath.org/ticket/12103#comment:80
<ul>
<li><strong>commit</strong>
changed from <em>539b1349359004b78712a67d2739cce9ce0227da</em> to <em>a8f18474d1b95afb024a53c36ca59b311519e88d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a8f18474d1b95afb024a53c36ca59b311519e88d"><span class="icon"></span>a8f1847</a></td><td><code>A very basic MeatAxe Cython wrapper</code>
</td></tr></table>
TicketgitFri, 18 Sep 2015 13:31:58 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:81
https://trac.sagemath.org/ticket/12103#comment:81
<ul>
<li><strong>commit</strong>
changed from <em>a8f18474d1b95afb024a53c36ca59b311519e88d</em> to <em>da665d9f683dc4ac77df6270e18f8f494d9118ac</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=da665d9f683dc4ac77df6270e18f8f494d9118ac"><span class="icon"></span>da665d9</a></td><td><code>A very basic MeatAxe Cython wrapper</code>
</td></tr></table>
TicketgitFri, 18 Sep 2015 13:38:55 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:82
https://trac.sagemath.org/ticket/12103#comment:82
<ul>
<li><strong>commit</strong>
changed from <em>da665d9f683dc4ac77df6270e18f8f494d9118ac</em> to <em>106aeef1f449f7db3a617e986d2e697865ee34ac</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=106aeef1f449f7db3a617e986d2e697865ee34ac"><span class="icon"></span>106aeef</a></td><td><code>A very basic MeatAxe Cython wrapper</code>
</td></tr></table>
TicketSimonKingFri, 18 Sep 2015 13:40:40 GMT
https://trac.sagemath.org/ticket/12103#comment:83
https://trac.sagemath.org/ticket/12103#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:78" title="Comment 78">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:76" title="Comment 76">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Do you suggest to rename Martin Albrecht's <code>matrix_mod2e_dense.pyx</code> to <code>matrix_gf2e_dense.pyx</code>?
</p>
</blockquote>
<p>
Yes!! It's a very confusing name.
</p>
</blockquote>
<p>
OK, if you are so determined, then I better change my module and class name, which is done in the previous (forced) commit.
</p>
<p>
I think I will now let it rest for a few hours, and then I'll tell how I found the default cutoff for Winograd-Strassen multiplication.
</p>
TicketSimonKingFri, 18 Sep 2015 19:48:33 GMT
https://trac.sagemath.org/ticket/12103#comment:84
https://trac.sagemath.org/ticket/12103#comment:84
<p>
I tested that classical multiplication yields the same result as Strassen multiplication, for various fields (GF(q) for q=4,8,9,25,27,32,125,243). No problem. Then I tested GF(2)---and got different results. Sigh. I don't know what's wrong with 2, but I need to debug it.
</p>
TicketjdemeyerSat, 19 Sep 2015 09:57:25 GMT
https://trac.sagemath.org/ticket/12103#comment:85
https://trac.sagemath.org/ticket/12103#comment:85
<p>
In <code>meataxe.pxd</code>, I assume that <code>ctypedef struct FILE</code> refers to the <code><stdio.h></code> type <code>FILE</code>? In that case, it's better to use
</p>
<pre class="wiki">from libc.stdio cimport FILE
</pre><p>
(or even remove that line altogether, since you don't actually use <code>FILE</code>)
</p>
TicketjdemeyerSat, 19 Sep 2015 10:05:40 GMT
https://trac.sagemath.org/ticket/12103#comment:86
https://trac.sagemath.org/ticket/12103#comment:86
<p>
In <code>spkg-install</code>, why this?
</p>
<pre class="wiki">PATCHES=../patches
for patch in "$PATCHES"/*.patch; do
</pre><p>
It's not wrong, but usually one simply does
</p>
<pre class="wiki">for patch in ../patches/*.patch; do
</pre>
TicketSimonKingSat, 19 Sep 2015 10:12:04 GMT
https://trac.sagemath.org/ticket/12103#comment:87
https://trac.sagemath.org/ticket/12103#comment:87
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:85" title="Comment 85">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
In <code>meataxe.pxd</code>, I assume that <code>ctypedef struct FILE</code> refers to the <code><stdio.h></code> type <code>FILE</code>? In that case, it's better to use
</p>
<pre class="wiki">from libc.stdio cimport FILE
</pre><p>
(or even remove that line altogether, since you don't actually use <code>FILE</code>)
</p>
</blockquote>
<p>
I refer to whatever MeatAxe refers to. But you are right, I don't use it. Similarly I don't use <code>Ulong</code>, <code>Ushort</code> etc. I left them in for completeness.
</p>
TicketSimonKingSat, 19 Sep 2015 10:13:04 GMT
https://trac.sagemath.org/ticket/12103#comment:88
https://trac.sagemath.org/ticket/12103#comment:88
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:86" title="Comment 86">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
In <code>spkg-install</code>, why this?
</p>
<pre class="wiki">PATCHES=../patches
for patch in "$PATCHES"/*.patch; do
</pre><p>
It's not wrong, but usually one simply does
</p>
<pre class="wiki">for patch in ../patches/*.patch; do
</pre></blockquote>
<p>
I guess I copied it from somewhere. But "somewhere" probably means a package in which the "patches" folder is referred to repeatedly.
</p>
TicketSimonKingSat, 19 Sep 2015 10:17:58 GMT
https://trac.sagemath.org/ticket/12103#comment:89
https://trac.sagemath.org/ticket/12103#comment:89
<p>
Meanwhile I know that the wrong results of Strassen multiplication in field order 2 come from the function <code>FfAddMapRowWindow</code>, which in fact has a special case for the field of order 2. This function is a modification of the MeatAxe function <code>FfMapRow</code>. So, I have to find out where my modifications went wrong.
</p>
TicketjdemeyerSat, 19 Sep 2015 10:20:03 GMT
https://trac.sagemath.org/ticket/12103#comment:90
https://trac.sagemath.org/ticket/12103#comment:90
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:87" title="Comment 87">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I refer to whatever MeatAxe refers to.
</p>
</blockquote>
<p>
I don't understand what you mean with "refers to".
</p>
<p>
I hope that meataxe does not redefine <code>FILE</code> (otherwise it's more broken than I thought).
</p>
<blockquote class="citation">
<p>
Similarly I don't use <code>Ulong</code>, <code>Ushort</code> etc.
</p>
</blockquote>
<p>
This is different, since these are meataxe-specific.
</p>
TicketSimonKingSat, 19 Sep 2015 10:27:15 GMT
https://trac.sagemath.org/ticket/12103#comment:91
https://trac.sagemath.org/ticket/12103#comment:91
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:90" title="Comment 90">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:87" title="Comment 87">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I refer to whatever MeatAxe refers to.
</p>
</blockquote>
<p>
I don't understand what you mean with "refers to".
</p>
</blockquote>
<p>
Hm. Now I am puzzled myself. I thought for a few minutes that I found it in meataxe.h of version 2.2.4, and when I ported my wrapper to version 2.4.24 I didn't check if it is still there. But now I checked: FILE is *not* defined in meataxe.h, neither in the old nor the new version.
</p>
<blockquote class="citation">
<p>
I hope that meataxe does not redefine <code>FILE</code> (otherwise it's more broken than I thought).
</p>
</blockquote>
<p>
It doesn't. It does <code>#include <stdio.h></code> both in the old and the new version.
</p>
TicketjdemeyerSat, 19 Sep 2015 10:29:00 GMT
https://trac.sagemath.org/ticket/12103#comment:92
https://trac.sagemath.org/ticket/12103#comment:92
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:91" title="Comment 91">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
It doesn't. It does <code>#include <stdio.h></code> both in the old and the new version.
</p>
</blockquote>
<p>
Excellent! Then there is certainly no reason to define <code>FILE</code> the way you did in <code>meataxe.pxd</code>.
</p>
TicketSimonKingSat, 19 Sep 2015 10:50:08 GMT
https://trac.sagemath.org/ticket/12103#comment:93
https://trac.sagemath.org/ticket/12103#comment:93
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:89" title="Comment 89">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Meanwhile I know that the wrong results of Strassen multiplication in field order 2 come from the function <code>FfAddMapRowWindow</code>, which in fact has a special case for the field of order 2. This function is a modification of the MeatAxe function <code>FfMapRow</code>.
</p>
</blockquote>
<p>
Got it! There is a pointer that is moved through the matrix by which we are multiplying. In case of order two, if an addition of a row happens then the pointer is moved to the next item after the current row of the matrix.
</p>
<p>
In <code>FfMapRow</code>, this position automatically is the first item of the next row of the matrix. In <code>FfAddMapRowWindow</code>, the matrix is in fact just a window of a larger matrix, and this position generally is outside of the window. Hence, I have to manually move the pointer to the first position of the next line of the window.
</p>
TicketgitSat, 19 Sep 2015 11:54:00 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:94
https://trac.sagemath.org/ticket/12103#comment:94
<ul>
<li><strong>commit</strong>
changed from <em>106aeef1f449f7db3a617e986d2e697865ee34ac</em> to <em>c1d5026ade5e1bb454401a34a734c91c15cbf75f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=de61563652d6b9a0229cf0f73d2e2090ad5e7f7e"><span class="icon"></span>de61563</a></td><td><code>An optional MeatAxe package</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f4873f771770edf57c3fffcc1ae778de4facb72a"><span class="icon"></span>f4873f7</a></td><td><code>Implement and use Strassen-Winograd matrix multiplication in MeatAxe</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c1d5026ade5e1bb454401a34a734c91c15cbf75f"><span class="icon"></span>c1d5026</a></td><td><code>A very basic MeatAxe Cython wrapper</code>
</td></tr></table>
TicketSimonKingSat, 19 Sep 2015 12:48:38 GMT
https://trac.sagemath.org/ticket/12103#comment:95
https://trac.sagemath.org/ticket/12103#comment:95
<p>
I force-pushed the new version.
</p>
<p>
Changes: The bug is fixed, and FILE and PATCHES are removed.
</p>
<p>
Now for timings and the quest for a good (default) cutoff.
</p>
<p>
When using Winograd-Strassen, one needs to define a matrix size such that divide-and-conquer is applied if and only if all resulting blocks have at least that size.
</p>
<p>
Meataxe packs matrix coefficients densely. I.e, if you have a field of size 3, then it will pack 5 matrix coefficients into one byte (<code>2^5<256</code>).
</p>
<p>
Each meataxe matrix is stored in a block of memory, row by row. Internally, meataxe uses "long" operations in some functions. That's why each row uses a byte size that is a multiple of sizeof(long), using up to sizeof(long)-1 trailing zero bytes ("padding bytes").
</p>
<p>
Winograd-Strassen operates on matrix windows. It is rather obvious that the window shouldn't end in the middle of a byte, i.e., the number of columns of a window should be a multiple of the "number of coefficients per byte".
</p>
<p>
In my old patches for version 2.2.4, in fact I used "byte" as unit. But in the new patches for version 2.4.24, I adopt meataxe's convention that row length should be divisible by sizeof(long). So, in my Winograd-Strassen implementation, the number of columns of matrix windows is a multiple of "sizeof(long)*(number of coefficients)".
</p>
<p>
Consequently, the cutoff parameter in meataxe is given in the unit "sizeof(long)" (in my current cython wrapper the unit is byte, but that's likely to change).
</p>
<p>
With the following function used in a Sage session, I have determined the optimal cutoff parameter for different field sizes and different matrix dimensions. Also I have tested for what matrix dimensions the school book algorithm is faster than the Winograd-Strassen algorithm, and I checked that both algorithms yield the same result.
</p>
<div class="wiki-code"><div class="code"><pre><span class="kn">from</span> <span class="nn">sage.matrix.matrix_gfpn_dense</span> <span class="kn">import</span> Matrix_gfpn_dense
<span class="k">def</span> <span class="nf">find_cutoff</span><span class="p">(</span>q<span class="p">,</span> D<span class="p">):</span>
<span class="k">print</span> <span class="s">"GF({})"</span><span class="o">.</span>format<span class="p">(</span>q<span class="p">)</span>
<span class="k">for</span> n <span class="ow">in</span> <span class="p">[</span><span class="mi">100</span><span class="p">,</span><span class="mi">500</span><span class="p">,</span><span class="mi">1000</span><span class="p">,</span><span class="mi">2000</span><span class="p">]:</span>
<span class="k">print</span> <span class="s">" n = {}:"</span><span class="o">.</span>format<span class="p">(</span>n<span class="p">),</span>
MS <span class="o">=</span> MatrixSpace<span class="p">(</span>GF<span class="p">(</span>q<span class="p">,</span><span class="s">'x'</span><span class="p">),</span> n<span class="p">)</span>
MS<span class="o">.</span>_MatrixSpace__matrix_class <span class="o">=</span> Matrix_gfpn_dense
M <span class="o">=</span> MS<span class="o">.</span>random_element<span class="p">()</span>
t <span class="o">=</span> cputime<span class="p">()</span>
N <span class="o">=</span> M<span class="o">.</span>_multiply_classical<span class="p">(</span>M<span class="p">)</span>
D<span class="p">[</span>q<span class="p">,</span>n<span class="p">]</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
D<span class="p">[</span>q<span class="p">,</span>n<span class="p">]</span><span class="o">.</span>add<span class="p">((</span>cputime<span class="p">(</span>t<span class="p">),</span><span class="mi">0</span><span class="p">))</span>
<span class="k">for</span> c <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">9</span><span class="p">):</span>
<span class="k">print</span> c<span class="o">*</span><span class="mi">8</span><span class="p">,</span>
sys<span class="o">.</span>stdout<span class="o">.</span>flush<span class="p">()</span>
t <span class="o">=</span> cputime<span class="p">()</span>
N1 <span class="o">=</span> M<span class="o">.</span>_multiply_strassen<span class="p">(</span>M<span class="p">,</span> c<span class="o">*</span><span class="mi">8</span><span class="p">)</span>
D<span class="p">[</span>q<span class="p">,</span>n<span class="p">]</span><span class="o">.</span>add<span class="p">((</span>cputime<span class="p">(</span>t<span class="p">),</span> c<span class="p">))</span>
<span class="k">assert</span> N1<span class="o">==</span>N
<span class="k">print</span>
<span class="k">print</span> <span class="s">"->"</span><span class="p">,</span><span class="nb">sorted</span><span class="p">(</span><span class="nb">list</span><span class="p">((</span>D<span class="p">[</span>q<span class="p">,</span>n<span class="p">])))[:</span><span class="mi">5</span><span class="p">]</span>
</pre></div></div><p>
The result was
</p>
<pre class="wiki">sage: D = {}
sage: for q in [2,3,8,9,25,27,32,49,81,125,243]: find_cutoff(q, D)
GF(2)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0, 0), (0.0, 1), (0.0, 2), (0.0, 3), (0.0, 4)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.002999999999985903, 5), (0.002999999999985903, 6), (0.002999999999985903, 7), (0.0030000000000427463, 4), (0.0030000000000427463, 8)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(0.019000000000005457, 0), (0.01999999999998181, 8), (0.02199999999999136, 4), (0.02199999999999136, 5), (0.02199999999999136, 7)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(0.12000000000000455, 0), (0.14599999999995816, 8), (0.1560000000000059, 4), (0.15699999999998226, 5), (0.15699999999998226, 6)]
GF(3)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0, 0), (0.0, 4), (0.0, 7), (0.0009999999999763531, 2), (0.0009999999999763531, 3)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.04899999999997817, 0), (0.05000000000001137, 7), (0.05099999999998772, 8), (0.051999999999964075, 5), (0.05299999999999727, 4)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(0.3509999999999991, 4), (0.3509999999999991, 5), (0.3509999999999991, 6), (0.36199999999996635, 8), (0.36299999999999955, 7)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(2.4659999999999513, 6), (2.4669999999999845, 4), (2.4669999999999845, 5), (2.5469999999999686, 7), (2.548000000000002, 8)]
GF(8)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0009999999999763531, 3), (0.0009999999999763531, 6), (0.0009999999999763531, 8), (0.0010000000000331966, 1), (0.0019999999999527063, 0)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.1169999999999618, 3), (0.117999999999995, 2), (0.1209999999999809, 5), (0.12100000000003774, 4), (0.12100000000003774, 6)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(0.9129999999999541, 7), (0.9130000000000109, 4), (0.9130000000000109, 6), (0.9139999999999873, 5), (0.9519999999999982, 3)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(6.291999999999973, 7), (6.29200000000003, 4), (6.293000000000006, 5), (6.293000000000006, 6), (6.569000000000017, 2)]
GF(9)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0009999999999763531, 7), (0.0010000000000331966, 2), (0.0010000000000331966, 4), (0.0019999999999527063, 0), (0.0019999999999527063, 3)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.12299999999999045, 3), (0.1239999999999668, 7), (0.12400000000002365, 2), (0.125, 4), (0.125, 5)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(0.9429999999999836, 4), (0.9429999999999836, 6), (0.9430000000000405, 7), (0.9440000000000168, 5), (0.9830000000000041, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(6.517999999999972, 6), (6.522999999999968, 7), (6.524000000000001, 5), (6.5330000000000155, 4), (6.793999999999983, 8)]
GF(25)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.002999999999985903, 0), (0.002999999999985903, 2), (0.002999999999985903, 3), (0.002999999999985903, 4), (0.002999999999985903, 6)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.28300000000001546, 4), (0.2839999999999918, 6), (0.2839999999999918, 7), (0.2840000000001055, 5), (0.2949999999999591, 8)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(1.9640000000000555, 7), (1.9650000000000318, 6), (1.9669999999999845, 4), (1.969000000000051, 5), (2.044999999999959, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(13.799999999999955, 4), (13.805000000000064, 6), (13.807000000000016, 7), (13.81499999999994, 5), (14.360000000000014, 8)]
GF(27)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0029999999999290594, 0), (0.0029999999999290594, 4), (0.0029999999999290594, 6), (0.0030000000000427463, 2), (0.0030000000000427463, 3)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.28099999999994907, 5), (0.28099999999994907, 7), (0.28100000000006276, 4), (0.28100000000006276, 6), (0.29300000000000637, 8)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(1.9509999999999081, 4), (1.9510000000000218, 6), (1.9510000000000218, 7), (1.9520000000001119, 5), (2.033999999999878, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(13.709999999999923, 6), (13.718000000000075, 7), (13.731999999999971, 5), (13.764999999999873, 4), (14.337999999999965, 8)]
GF(32)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0029999999999290594, 2), (0.0029999999999290594, 5), (0.0029999999999290594, 7), (0.0030000000000427463, 0), (0.0030000000000427463, 3)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.2700000000000955, 7), (0.27099999999995816, 4), (0.27099999999995816, 6), (0.2720000000000482, 5), (0.2799999999999727, 2)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(1.8730000000000473, 4), (1.893000000000029, 5), (1.8960000000000719, 7), (1.8980000000000246, 6), (1.9220000000000255, 2)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(13.370999999999981, 4), (13.513000000000034, 5), (13.535999999999945, 2), (13.625, 3), (13.687000000000012, 7)]
GF(49)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0029999999999290594, 4), (0.0029999999999290594, 7), (0.0030000000000427463, 0), (0.0030000000000427463, 2), (0.0030000000000427463, 3)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.28300000000001546, 4), (0.2860000000000582, 6), (0.2869999999999209, 5), (0.28700000000003456, 7), (0.2939999999999827, 8)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(1.9269999999999072, 6), (1.9300000000000637, 7), (1.9329999999999927, 5), (1.9470000000000027, 4), (2.038000000000011, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(13.607000000000198, 6), (13.632000000000062, 7), (13.685999999999922, 5), (13.788999999999987, 4), (14.29099999999994, 2)]
GF(81)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0029999999999290594, 2), (0.0029999999999290594, 4), (0.0029999999999290594, 5), (0.0029999999999290594, 7), (0.0029999999999290594, 8)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.2819999999999254, 4), (0.2819999999999254, 7), (0.2840000000001055, 6), (0.28899999999998727, 5), (0.29500000000007276, 2)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(1.9349999999999454, 6), (1.9409999999998035, 7), (1.9610000000000127, 4), (1.9629999999999654, 5), (2.0399999999999636, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(13.505999999999858, 7), (13.623000000000047, 5), (13.644000000000233, 6), (13.719000000000278, 4), (14.055000000000064, 8)]
GF(125)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0029999999999290594, 0), (0.0029999999999290594, 2), (0.0029999999999290594, 4), (0.0029999999999290594, 5), (0.0029999999999290594, 7)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.29599999999982174, 5), (0.2960000000000491, 4), (0.2960000000000491, 6), (0.2960000000000491, 7), (0.3009999999999309, 8)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(2.0429999999998927, 5), (2.04300000000012, 7), (2.0449999999998454, 4), (2.0450000000000728, 6), (2.0960000000000036, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(14.353999999999814, 7), (14.366000000000213, 5), (14.383000000000266, 4), (14.414999999999964, 6), (14.596000000000004, 8)]
GF(243)
n = 100: 8 16 24 32 40 48 56 64
-> [(0.0029999999999290594, 4), (0.0029999999999290594, 6), (0.003000000000156433, 0), (0.003000000000156433, 2), (0.003000000000156433, 8)]
n = 500: 8 16 24 32 40 48 56 64
-> [(0.3369999999999891, 5), (0.3369999999999891, 7), (0.33799999999996544, 4), (0.3380000000001928, 6), (0.34799999999995634, 8)]
n = 1000: 8 16 24 32 40 48 56 64
-> [(2.336999999999989, 4), (2.336999999999989, 6), (2.336999999999989, 7), (2.341999999999871, 5), (2.4020000000000437, 8)]
n = 2000: 8 16 24 32 40 48 56 64
-> [(17.700999999999794, 4), (17.958000000000084, 5), (17.998000000000047, 7), (18.02800000000002, 2), (18.03599999999983, 6)]
</pre><p>
<strong><span class="underline">Evaluation of these timings</span></strong>
</p>
<ul><li>My Winograd-Strassen implementation gives the same result as meataxe's school book implementation. <strong>--> Hooray</strong>
</li><li>There is not a single case (not even for small matrices) where meataxe's school book implementation is significantly faster than Winograd-Strassen <strong>--> Winograd-Strassen should be the default algorithm in matrix_gfpn_dense</strong>
</li><li>It seems that a cutoff between 4 and 7 in the unit "sizeof(long)" are about the same, and are generally better than other cutoffs.
</li></ul><p>
The last statement is backed up by another study, where I consider 3601x3601-matrices over different fields, varying the cutoff parameter. I got these timings for multiplication:
</p>
<pre class="wiki">cutoff 1 2 3 4 5 6 7 8
GF(4): 15.5 s 12.2 s 12.3 s 11 s 11 s 11 s 11 s 11.5 s
GF(9): 41.3 s 33.7 s 33.5 s 31.6 s 31.5 s 31.5 s 31.5 s 34 s
GF(16): 26.4 s 21.1 s 21 s 19.9 s 19.9 s 19.9 s 19.9 s 21.4 s
GF(25): 1min 34s 1min 12s 1min 12s 1min 8s 1min 8s 1min 8s 1min 8s 1min 12s
GF(32): 1min 27s 1min 6s 1min 6s 1min 4s 1min 4s 1min 4s 1min 4s 1min 10s
GF(243): 1min 55s 1min 27s 1min 27s 1min 18s 1min 18s 1min 18s 1min 19s 1min 24s
</pre><p>
Now, the real question is: What is the meaning of "4"? My guess is that "4" is "sizeof(long)/2", so that the default cutoff parameter now is "sizeof(long)/2". But I could be mistaken. Perhaps on a 32-bit machine, cutoff 4 is better than cutoff "2==sizeof(long)/2", and on a 128-bit machine, cutoff 4 is better than cutoff "8=sizeof(long)/2"? Or perhaps it all depends on L1/L2 cache size?
</p>
<p>
<strong><span class="underline">Request to the reviewer</span></strong>
</p>
<ul><li>Do you have access to machines of different architecture (32-bit, 128-bit, different cache sizes)? Could you try to use the function above to find the optimal cutoff parameters?
</li><li>Meataxe uses an environment variable ASM_MMX in the file kernel-0.c. It means that in some functions it uses assembler code in characteristic two. By copying I use it as well, in <code>FfAddMapRowWindow</code> mentioned above. In some comment, it says that "this assumes Intel with 4 bytes per long, but MMX implies Intel anyway."
</li></ul><blockquote>
<p>
My questions:
</p>
</blockquote>
<ul><li>Is ASM_MMX some kind of standard variable?
</li><li>Can you test the package on a machine where ASM_MMX is used?
</li></ul><blockquote>
<p>
Note that I do have Intel, but my longs are 8 bytes, not 4.
</p>
</blockquote>
TicketSimonKingSat, 19 Sep 2015 13:06:17 GMT
https://trac.sagemath.org/ticket/12103#comment:96
https://trac.sagemath.org/ticket/12103#comment:96
<p>
Just to see if I can improve the code a bit, I did
</p>
<pre class="wiki">sage: M = MatrixSpace(GF(125,'x'),2000).random_element()
sage: %crun N = M*M
PROFILE: interrupts/evictions/bytes = 1466/1183/718104
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/linux-va3e.site/18759/tmp_efM3tZ.perf.
Total: 1466 samples
0 0.0% 0.0% 1466 100.0% MatMulStrassen
0 0.0% 0.0% 1466 100.0% PyEval_EvalCode
0 0.0% 0.0% 1466 100.0% PyEval_EvalCodeEx
0 0.0% 0.0% 1466 100.0% PyEval_EvalFrameEx
0 0.0% 0.0% 1466 100.0% PyNumber_Multiply
0 0.0% 0.0% 1466 100.0% PyObject_Call
0 0.0% 0.0% 1466 100.0% PyRun_FileExFlags
0 0.0% 0.0% 1466 100.0% PyRun_SimpleFileExFlags
0 0.0% 0.0% 1466 100.0% PyRun_StringFlags
0 0.0% 0.0% 1466 100.0% Py_Main
0 0.0% 0.0% 1466 100.0% StrassenStep
0 0.0% 0.0% 1466 100.0% __libc_start_main
0 0.0% 0.0% 1466 100.0% __pyx_f_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense__matrix_times_matrix_
0 0.0% 0.0% 1466 100.0% __pyx_f_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense__multiply_strassen
0 0.0% 0.0% 1466 100.0% __pyx_pf_4sage_9structure_7element_6Matrix_2__mul__ (inline)
0 0.0% 0.0% 1466 100.0% __pyx_pw_4sage_9structure_7element_6Matrix_3__mul__
0 0.0% 0.0% 1466 100.0% _start
0 0.0% 0.0% 1466 100.0% binary_op1 (inline)
0 0.0% 0.0% 1466 100.0% call_function (inline)
0 0.0% 0.0% 1466 100.0% exec_statement (inline)
0 0.0% 0.0% 1466 100.0% ext_do_call (inline)
0 0.0% 0.0% 1466 100.0% fast_function (inline)
0 0.0% 0.0% 1466 100.0% function_call
0 0.0% 0.0% 1466 100.0% run_mod (inline)
2 0.1% 0.1% 1382 94.3% WindowAddMul
1368 93.3% 93.5% 1368 93.3% FfAddMapRowWindow
0 0.0% 93.5% 46 3.1% WindowDif
2 0.1% 93.6% 31 2.1% WindowSum
30 2.0% 95.6% 30 2.0% FfSetNoc
23 1.6% 97.2% 23 1.6% FfAddRowPartial
23 1.6% 98.8% 23 1.6% FfSubRowPartial
8 0.5% 99.3% 8 0.5% FfSubRowPartialReverse
0 0.0% 99.3% 4 0.3% WindowClear
4 0.3% 99.6% 4 0.3% __GI_memset
0 0.0% 99.6% 3 0.2% FfAlloc
0 0.0% 99.6% 3 0.2% MatAlloc
0 0.0% 99.6% 3 0.2% WindowAlloc
2 0.1% 99.7% 2 0.1% FfStepPtr
0 0.0% 99.7% 2 0.1% SysMalloc
1 0.1% 99.8% 2 0.1% __GI___libc_malloc
0 0.0% 99.8% 1 0.1% FfAddRow
0 0.0% 99.8% 1 0.1% FfGetPtr
1 0.1% 99.9% 1 0.1% FfMulRow
1 0.1% 99.9% 1 0.1% __memcpy_sse2_unaligned
0 0.0% 99.9% 1 0.1% _int_malloc
1 0.1% 100.0% 1 0.1% malloc_consolidate
sage: %crun N = M._multiply_classical(M)
PROFILE: interrupts/evictions/bytes = 2242/24/17464
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/linux-va3e.site/18759/tmp_R9Qzph.perf.
Total: 2242 samples
0 0.0% 0.0% 2242 100.0% PyEval_EvalCode
0 0.0% 0.0% 2242 100.0% PyEval_EvalCodeEx
0 0.0% 0.0% 2242 100.0% PyEval_EvalFrameEx
0 0.0% 0.0% 2242 100.0% PyObject_Call
0 0.0% 0.0% 2242 100.0% PyRun_FileExFlags
0 0.0% 0.0% 2242 100.0% PyRun_SimpleFileExFlags
0 0.0% 0.0% 2242 100.0% PyRun_StringFlags
0 0.0% 0.0% 2242 100.0% Py_Main
0 0.0% 0.0% 2242 100.0% __libc_start_main
0 0.0% 0.0% 2242 100.0% __pyx_f_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense__multiply_classical
0 0.0% 0.0% 2242 100.0% __pyx_pf_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense_32_multiply_classical (inline)
0 0.0% 0.0% 2242 100.0% __pyx_pw_4sage_6matrix_17matrix_gfpn_dense_17Matrix_gfpn_dense_33_multiply_classical
0 0.0% 0.0% 2242 100.0% _start
0 0.0% 0.0% 2242 100.0% call_function (inline)
0 0.0% 0.0% 2242 100.0% exec_statement (inline)
0 0.0% 0.0% 2242 100.0% ext_do_call (inline)
0 0.0% 0.0% 2242 100.0% fast_function (inline)
0 0.0% 0.0% 2242 100.0% function_call
0 0.0% 0.0% 2242 100.0% run_mod (inline)
2241 100.0% 100.0% 2241 100.0% FfMapRow
0 0.0% 100.0% 2241 100.0% MatMul
0 0.0% 100.0% 1 0.0% FfAlloc
1 0.0% 100.0% 1 0.0% FfMulRow
0 0.0% 100.0% 1 0.0% MatAlloc
0 0.0% 100.0% 1 0.0% MatDup
</pre><p>
So, if I want to optimise something then I should have a look at <code>FfMapRow/FfAddMapRowWindow</code>.
</p>
TicketSimonKingSat, 19 Sep 2015 19:03:05 GMT
https://trac.sagemath.org/ticket/12103#comment:97
https://trac.sagemath.org/ticket/12103#comment:97
<p>
I tried some tweaks, but it didn't result in a clear improvement. So, I'll now focus on wrapping echelon computation and then on the doctests.
</p>
TicketjdemeyerSat, 19 Sep 2015 19:06:33 GMT
https://trac.sagemath.org/ticket/12103#comment:98
https://trac.sagemath.org/ticket/12103#comment:98
<p>
It would be convenient if you would base this ticket on <a class="closed ticket" href="https://trac.sagemath.org/ticket/19240" title="defect: Rename matrix_mod2e_dense to matrix_gf2e_dense (closed: fixed)">#19240</a> (and review that), because there will be conflicts.
</p>
TicketSimonKingSun, 20 Sep 2015 07:46:51 GMTdependencies set
https://trac.sagemath.org/ticket/12103#comment:99
https://trac.sagemath.org/ticket/12103#comment:99
<ul>
<li><strong>dependencies</strong>
set to <em>#19240</em>
</li>
</ul>
TicketgitSun, 20 Sep 2015 07:56:30 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:100
https://trac.sagemath.org/ticket/12103#comment:100
<ul>
<li><strong>commit</strong>
changed from <em>c1d5026ade5e1bb454401a34a734c91c15cbf75f</em> to <em>9e2a8c6027a1034ec21ea52dd2881965c05292d3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1e6264db7d78ff3304f59a1f7744e5452c0ca946"><span class="icon"></span>1e6264d</a></td><td><code>Rename matrix_mod2e_dense to matrix_gf2e_dense</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=26f359e6e8011f7547b044a680de3af992a2dfda"><span class="icon"></span>26f359e</a></td><td><code>Fix unpickling old Matrix_mod2e_dense instances</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=32b2cb18fb11502661084810914ac9ba6e4a1336"><span class="icon"></span>32b2cb1</a></td><td><code>Fix docstring by making it a raw string</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1e47929f96da76765a17545e356a96d2f153e26a"><span class="icon"></span>1e47929</a></td><td><code>Change old into new style raise statement</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8e72fb522a00f1faf7b489ed1411cb1520e930f2"><span class="icon"></span>8e72fb5</a></td><td><code>An optional MeatAxe package</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c7d75fbf5f72e435dab9af5f5fc2e7cb253b9ba3"><span class="icon"></span>c7d75fb</a></td><td><code>Implement and use Strassen-Winograd matrix multiplication in MeatAxe</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9e2a8c6027a1034ec21ea52dd2881965c05292d3"><span class="icon"></span>9e2a8c6</a></td><td><code>A very basic MeatAxe Cython wrapper</code>
</td></tr></table>
TicketSimonKingSun, 20 Sep 2015 08:11:19 GMT
https://trac.sagemath.org/ticket/12103#comment:101
https://trac.sagemath.org/ticket/12103#comment:101
<p>
I don't know why "git trac push 12103 --force" does not return, although apparently it has succeeded and all commits have arrived on trac. Anyway, I have rebased the branch on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/19240" title="defect: Rename matrix_mod2e_dense to matrix_gf2e_dense (closed: fixed)">#19240</a>.
</p>
TicketSimonKingSun, 20 Sep 2015 08:44:11 GMT
https://trac.sagemath.org/ticket/12103#comment:102
https://trac.sagemath.org/ticket/12103#comment:102
<p>
By the way, I asked upstream about the "big" kernel (for field orders larger than 255) and got the reply that they had it in version 2.2.4, but removed in the most recent versions because apparently nobody has used it. So, if I want to use it, then I have to port the "big" kernel from 2.2.4 to 2.4.24 myself.
</p>
<p>
Very probably I will not do it. For my applications, field orders up to 255 are enough.
</p>
TicketSimonKingSun, 20 Sep 2015 09:47:59 GMT
https://trac.sagemath.org/ticket/12103#comment:103
https://trac.sagemath.org/ticket/12103#comment:103
<p>
In order to have a fully-fledged matrix implementation, I will have a look at sage.matrix.matrix_generic_dense to see what methods need to be implemented.
</p>
TicketgitMon, 21 Sep 2015 00:07:22 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:104
https://trac.sagemath.org/ticket/12103#comment:104
<ul>
<li><strong>commit</strong>
changed from <em>9e2a8c6027a1034ec21ea52dd2881965c05292d3</em> to <em>4bdd285cd6320851aa4ed7aee8fb820960005692</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4bdd285cd6320851aa4ed7aee8fb820960005692"><span class="icon"></span>4bdd285</a></td><td><code>A full wrapper for MeatAxe matrices</code>
</td></tr></table>
TicketSimonKingMon, 21 Sep 2015 00:17:36 GMT
https://trac.sagemath.org/ticket/12103#comment:105
https://trac.sagemath.org/ticket/12103#comment:105
<p>
The implementation of <code>_matrix_times_matrix_</code> is now inherited from <code>sage.matrix.matrix0</code>, i.e., instead of overriding it I created a method <code>_strassen_default_cutoff</code> that returns 0 (which means that Strassen-Winograd is used for all matrices).
</p>
<p>
Also, I have wrapped the computation of echelon form. Meataxe only computes a semi-echelon form. Thus, I need to work a little harder to get the reduced row echelon form. Again, it is a lot faster than what currently is in Sage for nonprime finite fields of odd order.
</p>
TicketgitMon, 21 Sep 2015 10:18:42 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:106
https://trac.sagemath.org/ticket/12103#comment:106
<ul>
<li><strong>commit</strong>
changed from <em>4bdd285cd6320851aa4ed7aee8fb820960005692</em> to <em>b237c5f4a500f313e573728d4a9b55cca902a255</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b237c5f4a500f313e573728d4a9b55cca902a255"><span class="icon"></span>b237c5f</a></td><td><code>Improve echelon computation in MeatAxe</code>
</td></tr></table>
TicketSimonKingMon, 21 Sep 2015 10:52:49 GMT
https://trac.sagemath.org/ticket/12103#comment:107
https://trac.sagemath.org/ticket/12103#comment:107
<p>
In Gaussian elimination, one adds a scalar multiple of one row to another row. In fact, one knows that pivot of the row to add, i.e., in fact one only needs to add a *part* of the row (namely the part after the pivot). However, MeatAxe did always add the complete rows, including the leading zeroes.
</p>
<p>
That's obviously a waste of time, and thus I added another patch to MeatAxe in my recent commit.
</p>
<p>
With the patch:
</p>
<pre class="wiki">sage: M = MatrixSpace(GF(25,'x'),5000).random_element(density=0.001)
sage: %time N = M.echelon_form()
CPU times: user 1min 9s, sys: 156 ms, total: 1min 9s
Wall time: 1min 9s
</pre><p>
Without the patch, it is 1min 31s. I guess that's something.
</p>
<p>
I am unsure if I will implement echelon computation à la Strassen. If I do, it is essential to be able to add *parts* of a row, because one operates on matrix windows and not on matrices.
</p>
TicketjdemeyerMon, 21 Sep 2015 13:03:58 GMT
https://trac.sagemath.org/ticket/12103#comment:108
https://trac.sagemath.org/ticket/12103#comment:108
<p>
Following up on your sage-devel post, you should add a file <code>build/pkgs/meataxe/dependencies</code> containing
</p>
<pre class="wiki"># no dependencies
</pre><p>
In that case, you need to create <code>$SAGE_LOCAL/include</code> to avoid
</p>
<pre class="wiki">cp: cannot create regular file '/usr/local/src/sage-config/local/include/': Not a directory
Error copying MeatAxe header.
</pre>
TicketSimonKingMon, 21 Sep 2015 13:29:24 GMT
https://trac.sagemath.org/ticket/12103#comment:109
https://trac.sagemath.org/ticket/12103#comment:109
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:108" title="Comment 108">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Following up on your sage-devel post, you should add a file <code>build/pkgs/meataxe/dependencies</code> containing
</p>
<pre class="wiki"># no dependencies
</pre></blockquote>
<p>
Thank you! Doing it now.
</p>
<blockquote class="citation">
<p>
In that case, you need to create <code>$SAGE_LOCAL/include</code> to avoid
</p>
<pre class="wiki">cp: cannot create regular file '/usr/local/src/sage-config/local/include/': Not a directory
Error copying MeatAxe header.
</pre></blockquote>
<p>
Pardon? is $SAGE_LOCAL/include not a standard Sage folder? Or do you mean that I need to do <code>mkdir -p "$SAGE_LOCAL/include"</code> because the local/include folder is only created during installation of Sage, making sage a dependency?
</p>
TicketSimonKingMon, 21 Sep 2015 13:36:24 GMT
https://trac.sagemath.org/ticket/12103#comment:110
https://trac.sagemath.org/ticket/12103#comment:110
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:109" title="Comment 109">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:108" title="Comment 108">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Following up on your sage-devel post, you should add a file <code>build/pkgs/meataxe/dependencies</code> containing
</p>
<pre class="wiki"># no dependencies
</pre></blockquote>
<p>
Thank you! Doing it now.
</p>
</blockquote>
<p>
Didn't help (edit: ... against the three occurrences of <code>make -j2 configure</code>. It did help against <code>sage -b</code>).
</p>
TicketjdemeyerMon, 21 Sep 2015 13:50:24 GMT
https://trac.sagemath.org/ticket/12103#comment:111
https://trac.sagemath.org/ticket/12103#comment:111
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:109" title="Comment 109">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Or do you mean that I need to do <code>mkdir -p "$SAGE_LOCAL/include"</code> because the local/include folder is only created during installation of Sage
</p>
</blockquote>
<p>
Yes, exactly.
</p>
TicketgitMon, 21 Sep 2015 13:59:26 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:112
https://trac.sagemath.org/ticket/12103#comment:112
<ul>
<li><strong>commit</strong>
changed from <em>b237c5f4a500f313e573728d4a9b55cca902a255</em> to <em>db6b7fe1f49c5412a5331b7eaa3c9584fcf0d636</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=db6b7fe1f49c5412a5331b7eaa3c9584fcf0d636"><span class="icon"></span>db6b7fe</a></td><td><code>Improve echelon computation in MeatAxe, and fix some compiler warnings</code>
</td></tr></table>
TicketgitMon, 21 Sep 2015 14:03:07 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:113
https://trac.sagemath.org/ticket/12103#comment:113
<ul>
<li><strong>commit</strong>
changed from <em>db6b7fe1f49c5412a5331b7eaa3c9584fcf0d636</em> to <em>191477e697d5fb02c0e6bf7f8b80850e1092d4f6</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=191477e697d5fb02c0e6bf7f8b80850e1092d4f6"><span class="icon"></span>191477e</a></td><td><code>Improve echelon computation in MeatAxe, and fix some compiler warnings</code>
</td></tr></table>
TicketSimonKingMon, 21 Sep 2015 14:07:03 GMT
https://trac.sagemath.org/ticket/12103#comment:114
https://trac.sagemath.org/ticket/12103#comment:114
<p>
Sorry for force-pushing again...
</p>
<p>
In the modified version of the previous commit, I do the "mkdir -p" thingy for all folders that I use ($SAGE_LOCAL/include and $SAGE_LOCAL/bin).
</p>
<p>
Also, I remove all but one compiler warnings for meataxe. The only remaining warning can not be removed. I need that the function <code>MatrxiToWindow</code> has a const argument, because it is used in a multiplication function which has const arguments. However, in <code>MatrixToWindow</code>, I assign the const argument to a pointer target type.
</p>
<p>
I think it is fine to ignore the warning. The matrix definitely is not altered inside of <code>MatrixToWindow</code> (but may of course be altered by a function that *later* modifies the window).
</p>
TicketSimonKingTue, 22 Sep 2015 07:27:21 GMT
https://trac.sagemath.org/ticket/12103#comment:115
https://trac.sagemath.org/ticket/12103#comment:115
<p>
I think there is a very severe problem: Error handling.
</p>
<p>
I thought that meataxe would set an error and then return an error value, for example in matinv.c in the function zmatinv:
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">if</span> <span class="p">(</span>f1 <span class="o">==</span> FF_ZERO<span class="p">)</span>
<span class="p">{</span>
MTX_ERROR1<span class="p">(</span><span class="s">"%E"</span><span class="p">,</span>MTX_ERR_DIV0<span class="p">);</span>
<span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
</pre></div></div><p>
which should propage to the function MatInverse:
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">if</span> <span class="p">(</span>zmatinv<span class="p">(</span>tmp<span class="p">,</span>dest<span class="o">-></span>Data<span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span>
<span class="p">{</span>
MatFree<span class="p">(</span>dest<span class="p">);</span>
<span class="k">return</span> <span class="nb">NULL</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> dest<span class="p">;</span>
</pre></div></div><p>
And in my wrapper, I also test for the error return value:
</p>
<div class="wiki-code"><div class="code"><pre> sig_on<span class="p">()</span>
OUT<span class="o">.</span>Data <span class="o">=</span> MatInverse<span class="p">(</span><span class="bp">self</span><span class="o">.</span>Data<span class="p">)</span>
sig_off<span class="p">()</span>
<span class="k">if</span> OUT<span class="o">.</span>Data <span class="o">!=</span> NULL<span class="p">:</span>
<span class="k">return</span> OUT
<span class="k">raise</span> <span class="ne">ArithmeticError</span><span class="p">(</span><span class="s">"This matrix is not invertible"</span><span class="p">)</span>
</pre></div></div><p>
However, it doesn't work. I get an immediate crash of Sage without any traceback:
</p>
<pre class="wiki">sage: M = MatrixSpace(GF(27,'x'),5).random_element(density=0.4)
sage: M.rank()
4
sage: ~M
matinv.c(50):Division by zero
</pre><p>
Hence, I need to study how meataxe manages to crash everything, even though it pretends to handle errors.
</p>
TicketSimonKingTue, 22 Sep 2015 07:39:19 GMT
https://trac.sagemath.org/ticket/12103#comment:116
https://trac.sagemath.org/ticket/12103#comment:116
<p>
I think it is the default error handler doing the following:
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">static</span> <span class="kt">void</span> <span class="nf">DefaultHandler</span><span class="p">(</span><span class="k">const</span> MtxErrorRecord_t <span class="o">*</span>e<span class="p">)</span>
<span class="p">{</span>
<span class="k">static</span> <span class="kt">int</span> count <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">if</span> <span class="p">(</span>LogFile <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span>
LogFile <span class="o">=</span> stderr<span class="p">;</span>
<span class="k">if</span> <span class="p">(</span>e<span class="o">-></span>FileInfo <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
fprintf<span class="p">(</span>LogFile<span class="p">,</span><span class="s">"%s(%d):"</span><span class="p">,</span>e<span class="o">-></span>FileInfo<span class="o">-></span>BaseName<span class="p">,</span>e<span class="o">-></span>LineNo<span class="p">);</span>
fprintf<span class="p">(</span>LogFile<span class="p">,</span><span class="s">"%s</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span>e<span class="o">-></span>Text<span class="p">);</span>
<span class="k">if</span> <span class="p">(</span><span class="o">--</span>count <span class="o"><=</span> <span class="mi">0</span><span class="p">)</span>
exit<span class="p">(</span><span class="mi">255</span><span class="p">);</span>
<span class="p">}</span>
</pre></div></div><p>
Apparently Sage's sig_on()/sig_off() cannot deal with the line <code>exit(255);</code>, right?
</p>
<p>
So, should I patch the default error handler, making it signal something that sig_on()/off() can deal with? What would that be?
</p>
<p>
Or perhaps I know something better: I think the usual MeatAxe binaries could very well keep using the current error handler. However, in my wrapper, I could instead define a new error handler and set it with <code>MtxSetErrorHandler</code>.
</p>
TicketjdemeyerTue, 22 Sep 2015 08:10:37 GMT
https://trac.sagemath.org/ticket/12103#comment:117
https://trac.sagemath.org/ticket/12103#comment:117
<p>
The fact that the error handler is called <code>DefaultHandler</code> seems to imply that it's possible to change the error handler...
</p>
<p>
For a simple example of a custom error handler for a C library, see the <code>error_handler</code> function in <code>src/sage/libs/gap/util.pyx</code>
</p>
TicketSimonKingTue, 22 Sep 2015 08:15:35 GMT
https://trac.sagemath.org/ticket/12103#comment:118
https://trac.sagemath.org/ticket/12103#comment:118
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:117" title="Comment 117">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
The fact that the error handler is called <code>DefaultHandler</code> seems to imply that it's possible to change the error handler...
</p>
</blockquote>
<p>
Sure. I already mentioned <code>MtxSetErrorHandler</code>.
</p>
<blockquote class="citation">
<p>
For a simple example of a custom error handler for a C library, see the <code>error_handler</code> function in <code>src/sage/libs/gap/util.pyx</code>
</p>
</blockquote>
<p>
Thank you, I'll have a look!
</p>
TicketjdemeyerTue, 22 Sep 2015 08:20:29 GMT
https://trac.sagemath.org/ticket/12103#comment:119
https://trac.sagemath.org/ticket/12103#comment:119
<p>
In case you're wondering: the function <code>PyErr_SetObject()</code> is a low-level version of <code>raise</code>: it "raises" an exception but execution continues to the <code>sig_error()</code> which is handled by <code>sig_on()</code>.
</p>
TicketSimonKingTue, 22 Sep 2015 08:20:49 GMT
https://trac.sagemath.org/ticket/12103#comment:120
https://trac.sagemath.org/ticket/12103#comment:120
<p>
I am not sure if the error handler should do sig_error().
</p>
<p>
There are some places in meataxe where a function A calls a function B, and if B returns an error value then A deallocates temporary data before returning an error value as well.
</p>
<p>
Wouldn't we prevent meataxe from these clean-up operations (causing a memory leak on error) if we would raise sig_error()?
</p>
TicketjdemeyerTue, 22 Sep 2015 08:22:58 GMT
https://trac.sagemath.org/ticket/12103#comment:121
https://trac.sagemath.org/ticket/12103#comment:121
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:120" title="Comment 120">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Wouldn't we prevent meataxe from these clean-up operations (causing a memory leak on error) if we would raise sig_error()?
</p>
</blockquote>
<p>
Yes.
</p>
<p>
But since I don't know the specifics of the meataxe error handling system, I cannot comment further.
</p>
TicketSimonKingTue, 22 Sep 2015 10:04:14 GMT
https://trac.sagemath.org/ticket/12103#comment:122
https://trac.sagemath.org/ticket/12103#comment:122
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:121" title="Comment 121">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:120" title="Comment 120">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Wouldn't we prevent meataxe from these clean-up operations (causing a memory leak on error) if we would raise sig_error()?
</p>
</blockquote>
<p>
Yes.
</p>
</blockquote>
<p>
The question is if we care. But perhaps we should, since catching errors and coping with it is typical for Python, and that has caused problems in the past (I recall some problem with the Gap interface, because a tight loop occasionally catching errors eventually exceeded the allowed number of errors in Gap).
</p>
<p>
Does meataxe care itself? That's unclear. I have seen instances of the cleaning-up-on-error, but I have seen other cases in which it does not clean up.
</p>
<blockquote class="citation">
<p>
But since I don't know the specifics of the meataxe error handling system, I cannot comment further.
</p>
</blockquote>
<p>
I am not sure if one can call it a "system". Anyway. There is a function that defines the error handler to-be-used. The function <code>MtxError</code> creates an error record (containing information on file name and line number and error code) and calls the error handler with it.
</p>
<p>
In sage.libs.gap.util, the error handler sets an exception and signals sig_error(). An alternative approach would be an error handler that just sets an exception. If the meataxe functions are wrapped with an error value (such as <code>cdef Matrix_t *MatInverse(Matrix_t M) except NULL</code>) then this error would be raised, wouldn't it?
</p>
<p>
To me, it seems like a cleaner approach, as it allows meataxe to cope with the exception. Plus, we would see if meataxe really respects its own error values (otherwise we would see crashes in the wrapper) and could fix that. Meanwhile I have THREE patches that should be send upstream, and I wouldn't mind a fourth patch.
</p>
TicketjdemeyerTue, 22 Sep 2015 10:23:49 GMT
https://trac.sagemath.org/ticket/12103#comment:123
https://trac.sagemath.org/ticket/12103#comment:123
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:122" title="Comment 122">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
In sage.libs.gap.util, the error handler sets an exception and signals sig_error(). An alternative approach would be an error handler that just sets an exception. If the meataxe functions are wrapped with an error value (such as <code>cdef Matrix_t *MatInverse(Matrix_t M) except NULL</code>) then this error would be raised, wouldn't it?
</p>
</blockquote>
<p>
At least in theory, that would work. You do need to be sure that the result is <code>NULL</code> <strong>if and only if</strong> the error handler was called. I agree that it would be cleaner if you can make it work because that would completely bypass the <code>sig_on()</code> system.
</p>
TicketSimonKingTue, 22 Sep 2015 10:28:44 GMT
https://trac.sagemath.org/ticket/12103#comment:124
https://trac.sagemath.org/ticket/12103#comment:124
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:123" title="Comment 123">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
At least in theory, that would work. You do need to be sure that the result is <code>NULL</code> <strong>if and only if</strong> the error handler was called.
</p>
</blockquote>
<p>
At least the meataxe documentation occasionally mentions that a certain value is returned on error.
</p>
<p>
And to be on the safe side, one could perhaps do <code>cdef Matrix_t *MatInverse(Matrix_t M) except? NULL</code>. Then, Cython would check if there is an exception set, and otherwise it would just continue.
</p>
TicketjdemeyerTue, 22 Sep 2015 10:33:29 GMT
https://trac.sagemath.org/ticket/12103#comment:125
https://trac.sagemath.org/ticket/12103#comment:125
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:124" title="Comment 124">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
otherwise it would just continue.
</p>
</blockquote>
<p>
Would that make sense? If you're doing something with the result, you need that it's not <code>NULL</code>, so the <code>except NULL</code> can actually be an additional sanity check (IIRC, Cython raises a <code>SystemError</code> when there is no exception set if there should be one. That's safer that a segfault because you forgot to check for a <code>NULL</code>).
</p>
TicketSimonKingTue, 22 Sep 2015 10:57:29 GMT
https://trac.sagemath.org/ticket/12103#comment:126
https://trac.sagemath.org/ticket/12103#comment:126
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:125" title="Comment 125">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:124" title="Comment 124">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
otherwise it would just continue.
</p>
</blockquote>
<p>
Would that make sense? If you're doing something with the result, you need that it's not <code>NULL</code>, so the <code>except NULL</code> can actually be an additional sanity check (IIRC, Cython raises a <code>SystemError</code> when there is no exception set if there should be one. That's safer that a segfault because you forgot to check for a <code>NULL</code>).
</p>
</blockquote>
<p>
Correct. The edits I am currently doing generally assume an error if an error value occurs (accepting Cython's SystemError as an answer). There is one function where the docs say that the value -1 means that PERHAPS there was an exception, and I'll use <code>except?</code> only in those cases.
</p>
TicketSimonKingTue, 22 Sep 2015 11:33:00 GMT
https://trac.sagemath.org/ticket/12103#comment:127
https://trac.sagemath.org/ticket/12103#comment:127
<p>
I was mistaken in one point: <code>MtxErrorRecord_t</code> does not contain the error code. It only contains a message that was created from the error record. The error messages are taken from a "static struct" that is part of the file message.c
</p>
<p>
Since the list of these error messages is finite and is in one-to-one correspondence to the error codes, I will translate each mesage back into the error code and use the appropriate error (<code>ZeroDivisionError</code>, <code>MemoryError</code>, <code>ArithmeticError</code> etc).
</p>
<p>
If you think that it isn't worth it, I could instead create a new error type <code>MtxError</code>, that is raised whenever an error occurs in meataxe. But I will go for the "long" solution, if you don't stop me...
</p>
TicketSimonKingTue, 22 Sep 2015 11:45:44 GMT
https://trac.sagemath.org/ticket/12103#comment:128
https://trac.sagemath.org/ticket/12103#comment:128
<p>
It seems to work. With the commit that I am preparing now and that also contains some doctests, I obtain:
</p>
<pre class="wiki">sage: M = MatrixSpace(GF(27,'x'),5).random_element(density=0.4)
sage: M.rank()
5
sage: ~M
[ 1 x^2 + 2*x + 2 0 0 0]
[ x^2 + 2*x 2*x^2 + 2 x^2 0 x^2 + x + 2]
[ x^2 + 2 x^2 2*x^2 2*x^2 + 1 x^2 + 2]
[ 1 x^2 + x 2*x 0 0]
[ 2*x^2 + x x 0 0 0]
sage: M = MatrixSpace(GF(27,'x'),5).random_element(density=0.4)
sage: M.rank()
4
sage: ~M
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
<ipython-input-6-1888fd9efc66> in <module>()
----> 1 ~M
/home/king/Sage/git/sage/src/sage/matrix/matrix_gfpn_dense.pyx in sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense.__invert__ (build/cythonized/sage/matrix/matrix_gfpn_dense.c:12186)()
1032 OUT._cache = {}
1033 sig_on()
-> 1034 OUT.Data = MatInverse(self.Data)
1035 sig_off()
1036 if OUT.Data != NULL:
ZeroDivisionError: Division by zero in file matinv.c (line 50)
</pre>
TicketgitTue, 22 Sep 2015 16:09:20 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:129
https://trac.sagemath.org/ticket/12103#comment:129
<ul>
<li><strong>commit</strong>
changed from <em>191477e697d5fb02c0e6bf7f8b80850e1092d4f6</em> to <em>2e6425793607152a39296a95c5c50f63cf796dea</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d889e0baf9308298c084f6d8ea2c1f052aeaf63c"><span class="icon"></span>d889e0b</a></td><td><code>Improve echelon computation in MeatAxe, and fix some compiler warnings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2e6425793607152a39296a95c5c50f63cf796dea"><span class="icon"></span>2e64257</a></td><td><code>Doctests and error handling for MeatAxe</code>
</td></tr></table>
TicketSimonKingTue, 22 Sep 2015 16:14:57 GMT
https://trac.sagemath.org/ticket/12103#comment:130
https://trac.sagemath.org/ticket/12103#comment:130
<p>
With the new commits, there is full doctest coverage for the MeatAxe wrapper. Both
</p>
<pre class="wiki">sage -t --optional=sage,meataxe src/sage/matrix/matrix_gfpn_dense.pyx
</pre><p>
and
</p>
<pre class="wiki">sage -t src/sage/matrix/matrix_gfpn_dense.pyx
</pre><p>
pass.
</p>
<p>
Moreover, as I have announced above, I can now handle errors in MeatAxe.
</p>
<p>
Another change: I have removed the <code>__pow__</code> method: The default <code>__pow__</code> method automatically uses Strassen multiplication and is thus faster than the previous method, which called MeatAxe's <code>MatPower</code> (which doesn't use Strassen).
</p>
<p>
Probably I have to work on several doctests in other files: All tests depending on a random matrix may fail with meataxe, thus, for these cases I need to force usage of <code>Matrix_generic_dense</code>.
</p>
TicketSimonKingTue, 22 Sep 2015 21:45:10 GMT
https://trac.sagemath.org/ticket/12103#comment:131
https://trac.sagemath.org/ticket/12103#comment:131
<p>
Problem:
</p>
<pre class="wiki">sage: K.<a> = GF(25)
sage: MS = MatrixSpace(K, 2, 4)
sage: M = MS([4, 4, 1, 0, 0, 2*a+1, a+2, 1])
sage: M.echelon_form()
[ 4 4 1 0]
[ 0 2*a + 1 a + 2 1]
</pre>
TicketgitTue, 22 Sep 2015 22:56:51 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:132
https://trac.sagemath.org/ticket/12103#comment:132
<ul>
<li><strong>commit</strong>
changed from <em>2e6425793607152a39296a95c5c50f63cf796dea</em> to <em>55a278da06ba77fdfde839aa2e45d43a6806f2fb</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7c389692bbc757d8d61e7f25e671527a80a7f6c5"><span class="icon"></span>7c38969</a></td><td><code>Fix computation of row-reduced echelon form</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=55a278da06ba77fdfde839aa2e45d43a6806f2fb"><span class="icon"></span>55a278d</a></td><td><code>Fix doctests when meataxe is installed</code>
</td></tr></table>
TicketSimonKingTue, 22 Sep 2015 23:04:43 GMTstatus, component changed
https://trac.sagemath.org/ticket/12103#comment:133
https://trac.sagemath.org/ticket/12103#comment:133
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>component</strong>
changed from <em>packages: experimental</em> to <em>packages: optional</em>
</li>
</ul>
<p>
I have fixed the computation of row-reduced echelon form.
</p>
<ul><li>With the current branch, meataxe in Sage is substantially improved compared with upstream (fixes for multiplication table IO, some speed-ups for echelon computation, Strassen-Winograd, error handling).
</li><li>Matrix arithmetic over small non-prime fields of odd order will be vastly faster with meataxe than with the previously used matrix implementation in Sage.
</li><li>Doctest coverage of the Cython wrapper is 100%.
</li><li><code>make test</code> should now pass (I need to re-run "make test" after fixing the errors, though).
</li></ul><p>
Hence: Needs review!
</p>
TicketSimonKingTue, 22 Sep 2015 23:05:15 GMT
https://trac.sagemath.org/ticket/12103#comment:134
https://trac.sagemath.org/ticket/12103#comment:134
<p>
PS: I suggest that meataxe will be optional, not experimental.
</p>
TickettscrimWed, 23 Sep 2015 14:34:44 GMTmilestone changed
https://trac.sagemath.org/ticket/12103#comment:135
https://trac.sagemath.org/ticket/12103#comment:135
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-6.9</em>
</li>
</ul>
<p>
+1 for making it optional.
</p>
TicketSimonKingWed, 23 Sep 2015 16:41:03 GMT
https://trac.sagemath.org/ticket/12103#comment:136
https://trac.sagemath.org/ticket/12103#comment:136
<p>
Sigh. I shot into my own foot: After installing this package, I couldn't install my cohomology package (because the latter relies on meataxe-2.2.4).
</p>
TicketSimonKingFri, 25 Sep 2015 07:06:11 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/12103#comment:137
https://trac.sagemath.org/ticket/12103#comment:137
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>improve error handling in meataxe (within reason)</em>
</li>
</ul>
<p>
Motivated by the attempt to rebase my cohomology package on the new meataxe version, I try to be a bit more careful concerning errors in meataxe.
</p>
<p>
I made a thorough list of all functions in meataxe that use MTX_ERROR (or some variation thereof). I found that not all of them have error values set. Some of them have a documentation defining an error value, but the function in some cases does not return them. And if a function returning an error value is called by a second function, then the error value is not always dealt with.
</p>
<p>
It would be a very messy work to fix error handling thoroughly. I thus try to go a middle way:
</p>
<ul><li>I will ignore MeatAxe's stand-alone programs, because they are *supposed* to immediately exit on error. In particular, I will also ignore functions checking command line arguments.
</li><li>I will try to only deal with functions that are relevant for matrix arithmetic, because that's the only part of meataxe that I am wrapping here.
</li></ul><p>
Hence, if someone in future wants to wrap the more interesting parts of MeatAxe (all the representation theory stuff), then he or she has to deal with it.
</p>
TicketSimonKingFri, 25 Sep 2015 07:10:46 GMT
https://trac.sagemath.org/ticket/12103#comment:138
https://trac.sagemath.org/ticket/12103#comment:138
<p>
PS: Also ignore the test suite, as that is supposed to have a non-default error handler anyway. And as long as the test suite passes, I could care less about its error handling.
</p>
TicketSimonKingFri, 25 Sep 2015 07:50:52 GMT
https://trac.sagemath.org/ticket/12103#comment:139
https://trac.sagemath.org/ticket/12103#comment:139
<p>
To summarise, it seems to me that everything concerning
</p>
<ul><li>stand-alone programs
</li><li>test suite
</li><li>"bit strings"
</li><li>polynomials and their factorisation (I currently do not wrap characteristic polynomials!)
</li><li>"greased" matrices (but see below!)
</li><li>integer matrices (I am only interested in finite fields)
</li><li>representations
</li><li>lattices
</li><li>matrix sets
</li><li>sets
</li><li>permutations
</li><li>operating system stuff. I am not going to fix setting a timeout in meataxe, because we can set a timeout in Sage, with <code>alarm(...)</code>, provided that we wrap meataxe calls in sig_on()/sig_off().
</li><li>word generators
</li></ul><p>
is not relevant at that point. I'll focus on what remains.
</p>
<p>
<span class="underline">Greased matrices</span>
</p>
<p>
Something that I have ignored but perhaps should consider in future: "Greased matrices". From the documentation, it seems that greased matrices use more memory, but have faster row operations achieved by precomputing linear combinations of blocks of rows. So, if meataxe becomes an optional package with <code>Matrix_gfpn_dense</code> wrapping meataxe matrices, then a further development would be a wrapper for greased matrices.
</p>
TicketSimonKingFri, 25 Sep 2015 10:22:02 GMT
https://trac.sagemath.org/ticket/12103#comment:140
https://trac.sagemath.org/ticket/12103#comment:140
<p>
Also I will not do error propagation for <code>MatFree</code>.
</p>
TicketSimonKingFri, 25 Sep 2015 12:15:29 GMT
https://trac.sagemath.org/ticket/12103#comment:141
https://trac.sagemath.org/ticket/12103#comment:141
<p>
I have a patch that "should work" (TM). But the test suite consistently fails in a part that I didn't change (concerning the stand-alone program zmw, which is supposed to "Make word"). The program relies on computation of null space which (I thinK) I haven't changed, except for error handling. Sigh.
</p>
TicketgitFri, 25 Sep 2015 22:52:50 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:142
https://trac.sagemath.org/ticket/12103#comment:142
<ul>
<li><strong>commit</strong>
changed from <em>55a278da06ba77fdfde839aa2e45d43a6806f2fb</em> to <em>f73337711df114571d1be0fa61140a41628703b7</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f73337711df114571d1be0fa61140a41628703b7"><span class="icon"></span>f733377</a></td><td><code>Use and propagate specific return values on error in matrix-related MeatAxe functions.</code>
</td></tr></table>
TicketSimonKingFri, 25 Sep 2015 23:00:04 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/12103#comment:143
https://trac.sagemath.org/ticket/12103#comment:143
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>improve error handling in meataxe (within reason)</em> deleted
</li>
</ul>
<p>
The problems with error propagation are solved, tests with the current patch should still pass, and I think it is good that with the fifth patch MeatAxe becomes a lot more consequent in using specific return values indicating an error. Thus, it an error handler that doesn't exit on error became even more useful.
</p>
<p>
For now, I have no idea for further improvements (but perhaps you have ideas?). So, I will continue to try and rebase David Green's programs for my group cohomology package.
</p>
TicketSimonKingSat, 26 Sep 2015 08:05:51 GMT
https://trac.sagemath.org/ticket/12103#comment:144
https://trac.sagemath.org/ticket/12103#comment:144
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:143" title="Comment 143">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
For now, I have no idea for further improvements ...
</p>
</blockquote>
<p>
One detail comes to my mind: MeatAxe does not only have MTX_ERROR, but also MTX_ASSERT and MTX_VERIFY. I made sure that after all instances of MTX_ERROR outside of stand-alone executables an error return value is returned. This is yet to be done for MTX_ASSERT and MTX_VERIFY.
</p>
TicketSimonKingSat, 26 Sep 2015 08:30:10 GMT
https://trac.sagemath.org/ticket/12103#comment:145
https://trac.sagemath.org/ticket/12103#comment:145
<p>
OTOH, I feel that I am overdoing it. So, I will *not* deal with MTX_ASSERT and MTX_VERIFY, unless requested by the referee.
</p>
TicketjdemeyerTue, 29 Sep 2015 11:20:38 GMT
https://trac.sagemath.org/ticket/12103#comment:146
https://trac.sagemath.org/ticket/12103#comment:146
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:51" title="Comment 51">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Complain to upstream. The tarball is directly from their website. I'm not going to fix that.
</p>
</blockquote>
<p>
Upstream's answer:
</p>
<pre class="wiki">I am currently working on a 2.4 release that will solve some known
problems and hopefully not break anthing else (it's been a long
time since I last touched the code...). The next TAR release will
contain a properly named root directory as you suggested.
I am not sure, however, when the release will be ready.
</pre>
TicketSimonKingTue, 29 Sep 2015 11:24:04 GMT
https://trac.sagemath.org/ticket/12103#comment:147
https://trac.sagemath.org/ticket/12103#comment:147
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:146" title="Comment 146">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:51" title="Comment 51">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Complain to upstream. The tarball is directly from their website. I'm not going to fix that.
</p>
</blockquote>
<p>
Upstream's answer:
</p>
<pre class="wiki">I am currently working on a 2.4 release that will solve some known
problems and hopefully not break anthing else (it's been a long
time since I last touched the code...). The next TAR release will
contain a properly named root directory as you suggested.
I am not sure, however, when the release will be ready.
</pre></blockquote>
<p>
OMG. I see coming that my patches won't apply on the new release.
</p>
TicketSimonKingWed, 30 Sep 2015 16:27:49 GMT
https://trac.sagemath.org/ticket/12103#comment:148
https://trac.sagemath.org/ticket/12103#comment:148
<p>
I have sent my patches upstream a minute ago.
</p>
TicketjdemeyerMon, 05 Oct 2015 08:05:17 GMT
https://trac.sagemath.org/ticket/12103#comment:149
https://trac.sagemath.org/ticket/12103#comment:149
<p>
Any answer from upstream?
</p>
<p>
Do you have an idea who could review those patches, because I seems to me that it should only be reviewed by somebody who knows meataxe.
</p>
<p>
One detail I spotted in the code: replace <code>except:</code> by <code>except BaseException:</code> (I assume that people write <code>except:</code> by mistake, so it's better to be explicit that you really want to catch everything).
</p>
TicketSimonKingMon, 05 Oct 2015 11:06:28 GMT
https://trac.sagemath.org/ticket/12103#comment:150
https://trac.sagemath.org/ticket/12103#comment:150
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:149" title="Comment 149">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Any answer from upstream?
</p>
</blockquote>
<p>
Unfortunately not.
</p>
<blockquote class="citation">
<p>
Do you have an idea who could review those patches, because I seems to me that it should only be reviewed by somebody who knows meataxe.
</p>
</blockquote>
<p>
This might be difficult. But the following should be possible even without deeper knowledge of meataxe:
</p>
<ul><li>Does the package keeps the promise that multiplication tables (name pXYZ.zzz, where XYZ is the order of the field) will not pollute the current directory?
</li><li>Are there memory leaks? Combine various random matrices by stacking, slicing, multiplication, copying etc, delete everything, repeat in a loop, and see if any memory is lost.
</li><li>Manually create the same large random matrices once in meataxe and once in the current sage backends. That includes the case of fields of characteristic 2 and prime fields, where meataxe will not be used by default. Then do arithmetic, including echolonization, and compare (using <code>M.list()</code>) if the results coincide in all implementations. There are examples of that type in the docs.
</li><li>In addition to the previous class of tests, compare the timings. You will hopefully find that for non-prime fields of odd characteristic meataxe is clearly superior over the current Sage implementation.
</li><li>Concerning Strassen-Winograd (which is not in upstream meataxe): Compare the results of multiplication using school book and Strassen-Winograd algorithm, with different cutoff and different matrix dimensions. Here, both the results (via <code>M.list()</code>) and the performance (memory consumption) should be compared. Also it can be tested if the default cutoff I chose is optimal even on 32bit machines (I only tested on 64 bit).
</li></ul><p>
I think a review based on such test would be valid. I doubt that for our current standard backends the review was more thorough than what I suggest here for an optional backend.
</p>
<blockquote class="citation">
<p>
One detail I spotted in the code: replace <code>except:</code> by <code>except BaseException:</code> (I assume that people write <code>except:</code> by mistake, so it's better to be explicit that you really want to catch everything).
</p>
</blockquote>
<p>
OK, can do.
</p>
TicketjdemeyerMon, 05 Oct 2015 12:01:43 GMT
https://trac.sagemath.org/ticket/12103#comment:151
https://trac.sagemath.org/ticket/12103#comment:151
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:150" title="Comment 150">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I doubt that for our current standard backends the review was more thorough than what I suggest here for an optional backend.
</p>
</blockquote>
<p>
A fair comment, but those standard backends are not heavily patched with patches which are not accepted by upstream.
</p>
<p>
Upstream code does not need a review, but these patches <em>do</em> need a review.
</p>
TicketjdemeyerMon, 05 Oct 2015 12:05:16 GMT
https://trac.sagemath.org/ticket/12103#comment:152
https://trac.sagemath.org/ticket/12103#comment:152
<p>
I think you are still mis-using some of the error handling.
</p>
<p>
For example, you have
</p>
<pre class="wiki">int MatEchelonize(Matrix_t *mat) except -1
</pre><p>
but you still write
</p>
<pre class="wiki"> if MatEchelonize(self.Data) == -1:
raise ArithmeticError("Error echelonizing this matrix")
</pre><p>
The latter should just be
</p>
<pre class="wiki">MatEchelonize(self.Data)
</pre>
TicketjdemeyerMon, 05 Oct 2015 12:22:05 GMT
https://trac.sagemath.org/ticket/12103#comment:153
https://trac.sagemath.org/ticket/12103#comment:153
<p>
You can remove these parts from <code>spkg-install</code>:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gi">+# Just to be sure, we also create other folders, although
+# they are standard SageMath folders
+
+mkdir -p $MTXBIN
+
+if [ $? -ne 0 ]; then
+ echo >&2 "Error creating directory for meataxe binaries."
+ exit 1
+fi
+
+mkdir -p "$SAGE_LOCAL/include"
+
+if [ $? -ne 0 ]; then
+ echo >&2 "Error creating SageMath's include directory."
+ exit 1
+fi
+
+mkdir -p "$SAGE_LOCAL/lib"
+
+if [ $? -ne 0 ]; then
+ echo >&2 "Error creating SageMath's lib folder."
+ exit 1
+fi
</span></pre></div></div><p>
(I know I asked you to add these, but in the mean time the build system was improved)
</p>
TicketSimonKingMon, 05 Oct 2015 12:22:21 GMT
https://trac.sagemath.org/ticket/12103#comment:154
https://trac.sagemath.org/ticket/12103#comment:154
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:152" title="Comment 152">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I think you are still mis-using some of the error handling.
</p>
<p>
For example, you have
</p>
<pre class="wiki">int MatEchelonize(Matrix_t *mat) except -1
</pre><p>
but you still write
</p>
<pre class="wiki"> if MatEchelonize(self.Data) == -1:
raise ArithmeticError("Error echelonizing this matrix")
</pre><p>
The latter should just be
</p>
<pre class="wiki">MatEchelonize(self.Data)
</pre></blockquote>
<p>
Right. I guess I wrote it before I changed to using error return values. How important is it to change that?
</p>
TicketjdemeyerMon, 05 Oct 2015 12:48:20 GMT
https://trac.sagemath.org/ticket/12103#comment:155
https://trac.sagemath.org/ticket/12103#comment:155
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:154" title="Comment 154">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
How important is it to change that?
</p>
</blockquote>
<p>
That's a very philosophical question. It's not important. This ticket is not important. Even Sage itself is not really that important.
</p>
<p>
Seriously: it's a small thing which makes your code more readable, so why wouldn't you fix it?
</p>
TicketgitMon, 05 Oct 2015 13:50:38 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:156
https://trac.sagemath.org/ticket/12103#comment:156
<ul>
<li><strong>commit</strong>
changed from <em>f73337711df114571d1be0fa61140a41628703b7</em> to <em>710668d45f5f1e75672482db62a00b57c29cd16a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=710668d45f5f1e75672482db62a00b57c29cd16a"><span class="icon"></span>710668d</a></td><td><code>Remove overcautious commands in spkg-install; rely on default error return values in matrix_gfpn_dense</code>
</td></tr></table>
TicketSimonKingMon, 05 Oct 2015 13:54:10 GMT
https://trac.sagemath.org/ticket/12103#comment:157
https://trac.sagemath.org/ticket/12103#comment:157
<p>
In fact there were several places in which I explicitly tested for error return values, where I should better let Cython do the job. Fixed now. Of course, I can't easily solve the problem that upstream didn't comment on (or just acknowledges receive of) my patches.
</p>
TicketSimonKingMon, 05 Oct 2015 13:54:39 GMTupstream changed
https://trac.sagemath.org/ticket/12103#comment:158
https://trac.sagemath.org/ticket/12103#comment:158
<ul>
<li><strong>upstream</strong>
changed from <em>None of the above - read trac for reasoning.</em> to <em>Reported upstream. No feedback yet.</em>
</li>
</ul>
TicketSimonKingSun, 11 Oct 2015 11:13:51 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/12103#comment:159
https://trac.sagemath.org/ticket/12103#comment:159
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Pickling</em>
</li>
</ul>
<p>
I thought that I did test pickling. But now I obtain crashes when unpickling a pickle.
</p>
<pre class="wiki">sage: M = MatrixSpace(GF(9,'x'),10,10)(0)
sage: M[2,3] = M[3,7] = 1
sage: f = tmp_filename()
sage: save(M, f)
sage: load(f+".sobj")
------------------------------------------------------------------------
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/ext/interrupt/interrupt.so(+0x4125)[0x7f5a7dd08125]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/ext/interrupt/interrupt.so(+0x4177)[0x7f5a7dd08177]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/ext/interrupt/interrupt.so(+0x60c9)[0x7f5a7dd0a0c9]
/lib64/libpthread.so.0(+0xf890)[0x7f5a85922890]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/matrix/matrix_gfpn_dense.so(+0xd9a0)[0x7f5a46fad9a0]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/matrix/matrix_dense.so(+0x629a)[0x7f5a6290029a]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/matrix/matrix0.so(+0x39496)[0x7f5a62d99496]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7f5a85b84a23]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_CallObjectWithKeywords+0x47)[0x7f5a85c35317]
/home/king/Sage/git/sage/local/lib/python2.7/lib-dynload/cPickle.so(+0x4f4e)[0x7f5a80250f4e]
/home/king/Sage/git/sage/local/lib/python2.7/lib-dynload/cPickle.so(+0xa669)[0x7f5a80256669]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/sage_object.so(+0x21fa2)[0x7f5a7e83bfa2]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/sage_object.so(+0x77df)[0x7f5a7e8217df]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/sage_object.so(+0x25e10)[0x7f5a7e83fe10]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x48a9)[0x7f5a85c3a1a9]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x7f5a85c3bb02]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x4dae)[0x7f5a85c3a6ae]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x43a1)[0x7f5a85c39ca1]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x43a1)[0x7f5a85c39ca1]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x43a1)[0x7f5a85c39ca1]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x43a1)[0x7f5a85c39ca1]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x43a1)[0x7f5a85c39ca1]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x43a1)[0x7f5a85c39ca1]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x80d)[0x7f5a85c3b9cd]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x7f5a85c3bb02]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyRun_FileExFlags+0x92)[0x7f5a85c666d2]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyRun_SimpleFileExFlags+0xd9)[0x7f5a85c67c09]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(Py_Main+0xc4d)[0x7f5a85c7d99d]
/lib64/libc.so.6(__libc_start_main+0xf5)[0x7f5a84e85b05]
python[0x4007be]
------------------------------------------------------------------------
Attaching gdb to process id 4561.
...
</pre>
TicketSimonKingSun, 11 Oct 2015 19:28:24 GMT
https://trac.sagemath.org/ticket/12103#comment:160
https://trac.sagemath.org/ticket/12103#comment:160
<p>
What can I change in my local git configuration so that I can push to trac if port 22 is blocked?
</p>
TickettscrimSun, 11 Oct 2015 19:43:33 GMT
https://trac.sagemath.org/ticket/12103#comment:161
https://trac.sagemath.org/ticket/12103#comment:161
<p>
You could try the solution posted here: <a class="ext-link" href="http://stackoverflow.com/questions/4891527/git-protocol-blocked-by-company-how-can-i-get-around-that"><span class="icon"></span>http://stackoverflow.com/questions/4891527/git-protocol-blocked-by-company-how-can-i-get-around-that</a>, but I'm not sure that will work because it is a different port (and IDK about how the trac server is setup and which ports it is listening to).
</p>
TicketSimonKingSun, 11 Oct 2015 21:07:03 GMT
https://trac.sagemath.org/ticket/12103#comment:162
https://trac.sagemath.org/ticket/12103#comment:162
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12103#comment:161" title="Comment 161">tscrim</a>:
</p>
<blockquote class="citation">
<p>
You could try the solution posted here: <a class="ext-link" href="http://stackoverflow.com/questions/4891527/git-protocol-blocked-by-company-how-can-i-get-around-that"><span class="icon"></span>http://stackoverflow.com/questions/4891527/git-protocol-blocked-by-company-how-can-i-get-around-that</a>, but I'm not sure that will work because it is a different port (and IDK about how the trac server is setup and which ports it is listening to).
</p>
</blockquote>
<p>
It didn't work; in particular, after the change, the error messages still mentioned port 22, which is not available to me.
</p>
TicketvbraunSun, 11 Oct 2015 22:14:27 GMT
https://trac.sagemath.org/ticket/12103#comment:163
https://trac.sagemath.org/ticket/12103#comment:163
<p>
not access to port 22 == no access to the internet. Complain to whoever is blocking you that you can't do your work and their service is useless to you
</p>
TicketgitMon, 12 Oct 2015 09:44:28 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:164
https://trac.sagemath.org/ticket/12103#comment:164
<ul>
<li><strong>commit</strong>
changed from <em>710668d45f5f1e75672482db62a00b57c29cd16a</em> to <em>c67cb42042b25d17aeb17999ac7430aafef0f142</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c67cb42042b25d17aeb17999ac7430aafef0f142"><span class="icon"></span>c67cb42</a></td><td><code>Fix pickling of meataxe matrices</code>
</td></tr></table>
TicketSimonKingMon, 12 Oct 2015 10:09:28 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/12103#comment:165
https://trac.sagemath.org/ticket/12103#comment:165
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>Pickling</em> deleted
</li>
</ul>
<p>
The problem was: The default implementation of unpickling relies on <code>set_unsafe(i,j,val)</code>. In my implementation, <code>set_unsafe</code> relies on a converter from finite field elements to the internal representation---and the converter is not created during the unpickling.
</p>
<p>
Hence, I created a custom <code>__reduce__</code> relying on some unpickling function.
</p>
<p>
There, I used the occasion to return to what I did in the old group cohomology spkg: Pickling is *not* by conversion of the matrix to a list of entries, but it dumps the densely packed internal representation. Advantage: It is a lot faster!
</p>
<p>
For the group cohomology spkg, it was checked that the internal representation does not depend on details such as big versus little endian machines: A pickle created on a big-endian machine can correctly be unpickled with a little-endian machine.
</p>
<p>
Another advantage of the new approach will be apparent in <a class="closed ticket" href="https://trac.sagemath.org/ticket/18514" title="defect: Upgrade of p_group_cohomology spkg (closed: fixed)">#18514</a>: Since the new pickling/unpickling scheme for meataxe matrices is a lot closer to the scheme used in the old group cohomology spkg, the *new* group cohomology package should relatively easily be able to read data from existing cohomology data bases.
</p>
TickettscrimWed, 16 Dec 2015 20:56:34 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/12103#comment:166
https://trac.sagemath.org/ticket/12103#comment:166
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-6.11</em>
</li>
</ul>
<p>
I get 2 doctest failures with MeatAxe <em>not</em> installed. Both I think are because they should be marked optional:
</p>
<pre class="wiki">File "../../matrix/matrix_gfpn_dense.pyx", line 213, in sage.matrix.matrix_gfpn_dense.PrimeFieldConverter_class.int_to_field
Failed example:
C.int_to_field(int(2))
Exception raised:
Traceback (most recent call last):
File "/home/travis/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/home/travis/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
exec(compiled, globs)
File "<doctest sage.matrix.matrix_gfpn_dense.PrimeFieldConverter_class.int_to_field[1]>", line 1, in <module>
C.int_to_field(int(Integer(2)))
NameError: name 'C' is not defined
**********************************************************************
File "../../matrix/matrix_space.py", line 992, in sage.matrix.matrix_space.MatrixSpace._get_matrix_class
Failed example:
type(matrix(GF(125,'z'), 2, range(4)))
Expected:
<type 'sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense'>
Got:
<type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
</pre>
TickettscrimWed, 16 Dec 2015 20:58:22 GMT
https://trac.sagemath.org/ticket/12103#comment:167
https://trac.sagemath.org/ticket/12103#comment:167
<p>
However, all tests pass in <code>src/matrix</code> with it installed.
</p>
TicketgitSat, 16 Jan 2016 13:05:44 GMTcommit changed
https://trac.sagemath.org/ticket/12103#comment:168
https://trac.sagemath.org/ticket/12103#comment:168
<ul>
<li><strong>commit</strong>
changed from <em>c67cb42042b25d17aeb17999ac7430aafef0f142</em> to <em>74edf19ac9217428c482cef93e77226cca84aab3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c2e6fe5cd34ae01fe4096312c6d1f9133dd267ee"><span class="icon"></span>c2e6fe5</a></td><td><code>A full wrapper for MeatAxe matrices</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=395aa9a75fd03bb87ffbfe09f8c2ed556132569e"><span class="icon"></span>395aa9a</a></td><td><code>Improve echelon computation in MeatAxe, and fix some compiler warnings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c5f328c5cc83e5cc4c67d626f9ba1368d12cab23"><span class="icon"></span>c5f328c</a></td><td><code>Doctests and error handling for MeatAxe</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c29d1f87ad8f397b89e46f20ffdf703994122de4"><span class="icon"></span>c29d1f8</a></td><td><code>Fix computation of row-reduced echelon form</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f816e41dfe0cd77310de4b8010bdfee975b2153e"><span class="icon"></span>f816e41</a></td><td><code>Fix doctests when meataxe is installed</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=80af75e962f077169a64191d5b9a7db5aa7cc1a7"><span class="icon"></span>80af75e</a></td><td><code>Use and propagate specific return values on error in matrix-related MeatAxe functions.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6649c821107b0c9c023083bf3075857e409d0f8f"><span class="icon"></span>6649c82</a></td><td><code>Remove overcautious commands in spkg-install; rely on default error return values in matrix_gfpn_dense</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d24260c5dee3faadd274545abdef757e2077d7ca"><span class="icon"></span>d24260c</a></td><td><code>Fix pickling of meataxe matrices</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bddc09d39f7d60b9d5216d37442ffdacb7f9d707"><span class="icon"></span>bddc09d</a></td><td><code>Merge branch 'u/SimonKing/meataxe' of trac.sagemath.org:sage into t/12103/meataxe</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=74edf19ac9217428c482cef93e77226cca84aab3"><span class="icon"></span>74edf19</a></td><td><code>Make two doctests optional</code>
</td></tr></table>
TicketSimonKingSat, 16 Jan 2016 13:07:20 GMTstatus changed
https://trac.sagemath.org/ticket/12103#comment:169
https://trac.sagemath.org/ticket/12103#comment:169
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I made the two failing tests optional and at that occasion merged the latest develop.
</p>
<p>
Is it fine now?
</p>
TickettscrimSat, 16 Jan 2016 15:44:46 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/12103#comment:170
https://trac.sagemath.org/ticket/12103#comment:170
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jeroen Demeyer, Travis Scrimshaw</em>
</li>
</ul>
<p>
Looks good to me now. Thanks.
</p>
TicketvbraunWed, 20 Jan 2016 10:20:08 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/12103#comment:171
https://trac.sagemath.org/ticket/12103#comment:171
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/SimonKing/meataxe</em> to <em>74edf19ac9217428c482cef93e77226cca84aab3</em>
</li>
</ul>
TicketdimpaseWed, 24 Feb 2016 23:26:50 GMTcommit deleted
https://trac.sagemath.org/ticket/12103#comment:172
https://trac.sagemath.org/ticket/12103#comment:172
<ul>
<li><strong>commit</strong>
<em>74edf19ac9217428c482cef93e77226cca84aab3</em> deleted
</li>
</ul>
<p>
there is no tarball on the mirrors, apparently
</p>
TicketvbraunThu, 25 Feb 2016 09:34:58 GMT
https://trac.sagemath.org/ticket/12103#comment:173
https://trac.sagemath.org/ticket/12103#comment:173
<p>
Fixed
</p>
Ticket