Hi Simon, > wrote: > > As far as I know it's the fastest implementation for medium size primes > > (16 bits or so). For very small primes one can do better > > But actually linbox is already much faster over GF(3) than what is > currently done in Sage.
Yep, it was just meant as a statement about the viability of the chosen strategy (using ATLAS) > > It's a shame we are not using the libraries we ship to full potential but > > so far no one stepped up (me included) to fix this situation. > > OK, but how much work would be needed? It depends on how far you want to go: 1) Only switch multiplication over to LinBox, that's probably easy to do 2) Switch everything to LinBox of FFLAS/FFPACK directly. This probably needs some hacking around. > It appears to me that there is > only very little overhead in calling the linbox routines (via > sage.libs.linbox.linbox), since the data of a Matrix_modn_dense is > already stored in the same format used by linbox (namely mod_int **). > In particular, I wounder about your statement that the memory > consumption would increase. Is that because of internal linbox > computations? > Here is how linbox is wrapped (see > sage.matrix.matrix_modn_dense.Matrix_modn_dense._multiply_linbox): > ... > self._init_linbox() > sig_on() > linbox.matrix_matrix_multiply(ans._matrix, B._matrix, > B._nrows, B._ncols) > sig_off() > > self._init_linbox() seems rather light-weight, and > linbox.matrix_multiply is also a very thin wrapper of the linbox > routines. Similarly, one proceeds with other routines (computing > echelon form and so on) Actually, this is how we are wrapping our wrapper for LinBox which is part of the LinBox SPKG. This is where the actual heavy lifting is done such as converting ints to doubles etc. So what you see in Sage gives you a misleading impression. Btw. the reason why this wrapper exists is that LinBox takes so long to compile and takes so much memory. A harmless doctest change thus triggered a long compilation. Hence we outsourced it. > Actually I think it would even be easy enough to call the linbox > routines directly (without using the sage.libs.linbox.linbox wrapper, > thus avoiding all overhead). Since I need fast matrix arithmetics over > finite fields, I have some motivation to rewrite _mul_ accordingly. If one is serious about this then one should probably use the FFLAS/FFPACK low-level routines directly (Burcin might have some old patches for this, he's the last person I know of who tried) since that avoids compiling all thee layers of C++ in LinBox. > But one question: Can linbox deal with non-prime finite fields? They had some experimental code at some point IIRC but nothing for general use. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
