On 06/13/2013 04:50 AM, Niels Möller wrote:
Daniel Lichtblau<d...@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
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel