Re: Strassen multiplication over the integers

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

On Tue, Apr 28, 2015 at 12:42:42AM +0200, Peter Bruin wrote:
> Hello Bill,
> 
> > 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 above two points are addressed by the attached patch.  (Note that
> the assumption that A == B in A*B doesn't really seem to simplify either
> the classical algorithm or Strassen's algorithm.  Even the following
> could be reasonable: "GEN ZM_sqr(GEN x) { return ZM_mul(x, x); }" ...)

Applied thanks!
Eventually, the tuning parameter could be different for ZM_mul and 
ZM_sqr, but I do not think so.

> > - the tuning should depend on the size of the coefficients, I think.
> 
> Certainly, for larger coefficients it is advantageous to use Strassen
> multiplication already for smaller matrices.  I haven't yet done any
> good experiments to see how the bound should depend on the maximum
> coefficient size, though.
> 
> > - ideally the program src/test/tune.c should deal with the tuning.
> > This program deal with dependencies between tuning parameters.
> 
> OK, I hope to have some time soon to try to write an addition for
> src/test/tune.c for this.

Do not waste too much time with tune.c. The most important is to find out
how the tuning is affected by the coefficient size.

By the way, what matrix size your project is using ?

> > - Most of the code is fairly generic, so maybe there could be a
> > gen_matmul_sw function.
> 
> Indeed, and I actually already have an implementation of exactly this
> function, but it is an older version with awkward conventions for the
> indices.  I will try to update this soon.  (Unfortunately it will be
> hard to tune that one...)

Well, we might let the caller provide the tuning parameter.

Thanks for your contribution!
Bill.