On Tuesday 12 July 2011, Volker Braun wrote:
> Does linbox actually use blas for fast matrix multiplication over finite
> fields? I know its hard to tell from the linbox source code but I don't
> think floating point stuff could be faster than the direct application of
> Strassen's algorithm.
Yes. It uses FFLAS/FFPACK for dense matrices over GF(p). Which in top of the
numerical routines it implements Strassen:
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/FFLAS/
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
1) by bit-slicing:
http://arxiv.org/abs/0901.1413
or 2) bit-packing:
http://wiki.sagemath.org/days10/JGDumasTalk
http://wiki.sagemath.org/days10?action=AttachFile&do=view&target=Dumas_SD10_talk.pdf
Btw. the main author of FFLAS/FFPACK Clément Pernet was the first Sage Postdoc
at UW.
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.
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
