Hi, > > Btw. Magma does it in 4.37 seconds on my computer, to get a sense of what > > is the state-of-the-art. > > You mean for 2000x2000 over GF(125)? So, it is a long way to go, even > for MeatAxe.
Yes, and it should get worse as you increase the degree or did they implement Strassen in MeatAxe by now? > BTW, Sage's current implementation needs 906.69 s for a > single multiplication. We suck at this it seems :) > If I understand correctly, the basic idea can be easily automatised: > - The given base field F (=GF(125), for instance) determines a > (Conway) polynomial p of degree d. > - One starts with a polynomial ring R over the corresponding prime > field F0 and 2*d variables, constructs the polynomial ring in x over > R, and mods out p. The result is a quotient ring Q. > - Multiplication of two "general" elements of Q, represented by degree- > (d-1) polynomials whose coefficients are the 2*d variables from R, > results in a d-tuple T of elements of R. > - Matrices over F are represented by d-tuples of matrices over F0, and > multiplication is obtained by inserting the elements of these d-tuples > into the elements of T. Yep & it would be much faster already than what we have currently. > But is it possible to *automatically* find a Karatsuba- or Toom-Cook- > type formula that reduces the number of products that appear in T? > > An example from the paper: Over GF(4), the multiplication of A=A0+xA1 > with B=B0+xB1 (using p=x^2+x+1) would naively be > (A0*B0+A1*B1) + x*(A1*B1+A1*B0+A0*B1) > But using Karatsuba, it becomes > (A0*B0+A1*B1) + x*((A0+A1)*(B0+B1)+A0*B0), > which saves one product. > > Is there an automated procedure that finds the second formula, given > the first? If not, how could one do better than with schoolboy > multiplication, in the general case? Well, the paper does search for Karatsuba-style formulas automatically, but it's a non-trivial (brute-force-ish) computation. So far, there does not seem to be anything better than this. But other people would know better than me. 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: [email protected] -- To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
