caching of transforms used for large multiplications

[Daniel Lichtblau]

On 06/13/2013 04:50 AM, Niels Möller wrote:
> Daniel Lichtblau<danl at wolfram.com>  writes:
>
>> Re GCD usage, mostly I had in mind the matrix multiplications
>> (which I believe are balanced) and a few others that,
>
> You may want to have a look at
> http://gmplib.org:8000/gcd-nisse/file/tip/mpn/generic/matrix22_mul.c.
> This code reuses transforms, and it does a few additions in the
> transform domain. So 8 forward transforms, 8 pointwise muls, and 4
> inverse transforms. One pointwise multiplication could be eliminated
> using Strassen's trick, at the cost of more complicated operations in
> the transform domain.

These forward transforms are exactly the sort of thing I was hoping 
might be cached, either automatically or on prompting from the user. It 
is perhaps... in theory... maybe... possible for one to invoke GMP at 
that deep a level, and retain the forward transforms while needed. But 
that would be bad because it would involve either bypassing, or 
independently running, the smarts that determine what multiplication 
method to use in the first place. Also it would be a wheel that every 
user wanting it would have to reinvent. Much better if it were built in 
directly.

That said, I confess I am not sure there is much need for this outside 
of subquadratic gcd code. If it is not more generally useful, then I 
guess this automation would only be of benefit to a limited set of 
users. (Like, maybe four of us.)


> Exactly. Another trick, suggested by Paul, iirc: Say you have the 2x2
> matrix M, elements of size n, and a vector (x;y) of size 2n, and you
> want the (unbalanced) matrix-vector product
>
>    M (x;y)
>
> Then split x and y as x = x_1 B^n + x_0, y = y_1 B^n + y_0, and compute
> the balanced *matrix* product
>
>    M (x_0, x_1; y_0, y_1)
>
> using any optimization tricks available. The two resulting columns can
> be combined cheaply to get the desired vector.

Hey, that's neat. So you can get both forward transform reuse, and 7-for-8.


>> It was indeed Niels' "Subquadratic GCD", dated October 30, 2008-- did
>> not say where the presentation was given but it could well be an
>> update of the slides referred to in Niels' response.
>
> I wonder where I have those files. The timing matches the two-month
> period where I worked at KTH, sharing a room with Torbjörn and working
> with integration and optimization of the subquadratic gcd code. I
> made a longer presentation at the department towards the end of that
> project.
>
> Regards,
> /Niels

If you do not manage to locate them I can scan and send a pdf. (Least I 
can do for someone who shared a room for two months with that Torbjörn 
fellow..)

Regards,
Daniel