Re: new FFM_mul (and FlxqM_mul, FqM_mul, ...)

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Bill Allombert [2014-01-14 11:48]:
> Do you know how to compute the square of a matrix faster than by using M*M ?

Obviously for matrices of size 1, we do :-)

For size 2 as well (2 squares + 4 multiply) :

(12:15) gp > [a,b;c,d]^2
%1 = 
[a^2 + c*b b*a + d*b]

[c*a + d*c c*b + d^2]

=

[a^2 + c*b b*(a + d)]

[c*(a + d) c*b + d^2]

Same (uglier :-) in dimension 3 !

Presumably you can go on for very small sizes exploiting the commutativity at
the level of scalars, as well as optimized squarings at that same level.


For general sizes, there are variants of Strassen (and Winograd) optimized for
squarings: recursively 4 squarings + 3 multiplications (instead of 7
multiplications) and 9 additions (instead of 15 for Winograd).

This Bodrato ISSAC2010 paper is probaly the best practical version:

  http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatrixMultiplicationForSquares.pdf


For computing general powers, it depends of the size of the exponent : either
naive (binary exponentiation + optimized squarings :-) or first reducing
x^n mod charpoly(A).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`