Hi Martin, On 13 Jul., 13:50, Martin Albrecht <martinralbre...@googlemail.com> wrote: > Note that these timings are for the school book multiplication (i.e. 9 = 3^2 > multiplications) instead of Karatsuba-style, Python overhead and Sage <=> > LinBox overhead.
Sure. As you said in your previous post, that implementation is the most naive, given the basic idea. > 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. BTW, Sage's current implementation needs 906.69 s for a single multiplication. 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. 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? Best regards, Simon -- 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