Re: Strassen multiplication over the integers

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Apr 25, 2015 at 11:49:49AM +0200, Peter Bruin wrote:
> Bonjour,
> 
> I have been working on a PARI implementation of Strassen's algorithm for
> matrix multiplication (more precisely, Winograd's variant, which uses
> fewer additions), in particular over the integers.  This has complexity
> O(n^(log_2(7)) (instead of the classical O(n^3)) for n x n-matrices.
> 
> The code is in the attached ZM_mul_sw.patch; a program for tuning it is
> in tune.c, and the output of running this tuning program on my laptop
> (x86_64 Core i5-4210M with Gentoo GNU/Linux and PARI 2.8.0-development)
> is in tune.txt.

Hello Peter,

I have applied your patch with very minor modifications.

However there are things that need to be done.

- ZM_sqr should be implemented as well.

- gmul or RgM_mul should be changed to call ZM_mul when appropriate.

- the tuning should depend on the size of the coefficients, I think.

- ideally the program src/test/tune.c should deal with the tuning.
This program deal with dependencies between tuning parameters.

- Most of the code is fairly generic, so maybe there could be a 
gen_matmul_sw function.

A note: do not use cgiv on a recursive type, it does not work.

Thanks a lot for your contribution to PARI!
Bill.