Hi Martin, On 13 Jul., 12:11, Martin Albrecht <martinralbre...@googlemail.com> wrote: > Do you know Tom Boothby's and Robert Bradshaw's excellent paper > > Bitslicing and the Method of Four Russians Over Larger Finite Fields > > http://arxiv.org/abs/0901.1413
Thank you for your hint! > sage: P.<A2,A1,A0,B2,B1,B0> = PolynomialRing(GF(5)) > sage: R.<x> = P[] > sage: Q.<x> = R.quo(x^3 + 3*x + 3) > > sage: f = (A2*x^2+A1*x+A0) > sage: g = (A2*x^2+A1*x+A0) > > # so this is what we need to compute: > > sage: f*g > (2*A2^2 + A1^2 + 2*A2*A0)*x^2 + (2*A2^2 - A2*A1 + 2*A1*A0)*x - A2*A1 + A0^2 That is the same as f*f. Did you intend to do sage: g = (B2*x^2+B1*x+B0) sage: f*g (2*A2*B2 + A0*B2 + A1*B1 + A2*B0)*x^2 + (2*A2*B2 + 2*A1*B2 + 2*A2*B1 + A0*B1 + A1*B0)*x + 2*A1*B2 + 2*A2*B1 + A0*B0 ? > sage: def my_mul(A2,A1,A0, B2,B1,B0): > ... A22 = A2._multiply_linbox(A2) > ... A2A1 = A2._multiply_linbox(A1) > ... A22_2 = 2*A22 > ... C2 = (A22_2 + A1._multiply_linbox(A1) + 2*A2._multiply_linbox(A0)) > ... C1 = (A22_2 - A2A1 + 2*A1._multiply_linbox(A0)) > ... C0 = - A2A1 + A0._multiply_linbox(A2) > ... return C2,C1,C0 B2,B1,B0 are not used, it just computes the square of the first argument. f*g from above yields sage: def my_mul(A2,A1,A0, B2,B1,B0): ....: A0B0 = A0._multiply_linbox(B0) ....: A0B1 = A0._multiply_linbox(B1) ....: A0B2 = A0._multiply_linbox(B2) ....: A1B0 = A1._multiply_linbox(B0) ....: A1B1 = A1._multiply_linbox(B1) ....: A1B2 = A1._multiply_linbox(B2)*2 ....: A2B0 = A2._multiply_linbox(B0) ....: A2B1 = A2._multiply_linbox(B1)*2 ....: A2B2 = A2._multiply_linbox(B2)*2 ....: C2 = A2B2+A0B2+A1B1+A2B0 ....: C1 = A2B2+A1B2+A2B1+A0B1+A1B0 ....: C0 = A1B2+A2B1+A0B0 ....: return C2,C1,C0 ....: sage: A = [random_matrix(GF(5),500,500) for _ in range(3)] sage: B = [random_matrix(GF(5),500,500) for _ in range(3)] sage: %time _ =my_mul(*(A+B)) CPU times: user 0.42 s, sys: 0.05 s, total: 0.47 s Wall time: 0.48 s sage: A = [random_matrix(GF(5),2000,2000) for _ in range(3)] sage: B = [random_matrix(GF(5),2000,2000) for _ in range(3)] sage: %time _ =my_mul(*(A+B)) CPU times: user 15.08 s, sys: 0.39 s, total: 15.46 s Wall time: 15.51 s It is a bit slower than MeatAxe (for 2000x2000 over GF(125), it needs 11.68 seconds on my computer), but I think that's not bad for the first attempt. 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
