caching of transforms used for large multiplications

[Niels Möller]

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.

> Possibly one value would be
> a factor of two larger in size than the other (i.e. the smaller
> on the order of the square root of the bigger). This might be
> what Niels had in mind with "splitting the larger factor..."

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.

> 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

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.