Toom symmetries

[Alberto Zanoni]

Alle 14:08, mercoledì 10 giugno 2009, David Harvey ha scritto:
> On Jun 10, 2009, at 3:00 AM, bodrato at mail.dm.unipi.it wrote:
> > There are a lot of tricks like this, the first one in Karatsuba
> > (due to?)
> > saving half an addition. There is one in Toom-3, saving half a sum
> > again,
> > and it is implemented in the current[1] interpolate_5pts, another in
> > Toom-3.5, saving two half additions, implemented in interpolate_6pts.
>
> Marco,
>
> At some point I skimmed over your paper with Zanoni on the optimality
> of Toom-Cook matrices; I recall your automated search did not take
> into account these kind of tricks that merge the interpolation and
> recomposition stages. Is this correct?

Hi, I'm Alberto (Zanoni).

Yes, it is. The paper deals only with the interpolation stage. We didn't 
consider its merging with evaluation and/or recomposition there.

> Have you tried this since 
> writing the paper? It seems that it shouldn't be difficult in theory
> to extend the search method, although I have no idea if it's
> practical (the search spaces are very large...?).

Just to know, in our case the search space - for interpolation only - for 
Toom-3.5 was analyzed in about one week of running time (while Toom-3 took 
just some seconds). 

It seems difficult to use the same tool from the very beginning of 
interpolation phase with higher Toom. In our paper, for higher Toom 
some "manual" steps had to be done, in order to have a sufficient number of 
zero entries in the matrix, so that the analysis could be done in reasonable 
time.

This limitation was in practice the starting point to look for other 
techniques searching for optimization or generalization somewhere else 
(stages merging, use of the "divide by 2" technique, the "general" Toom using 
powers of 2,...)

We didn't try to insert these techniques in our "old" automated search tool. 

Alberto