Re: Strassen multiplication over the integers

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

Hello Bill,

>> >> > - Most of the code is fairly generic, so maybe there could be a
>> >> > gen_matmul_sw function.
>> 
>> I have now implemented this; see the attached patch.  It is
>> completely analogous to ZM_mul_sw.  There are some new tests to
>> ensure that the new code is covered.
>
> Did you test whether ZM_mul_sw was faster than gen_matmul_sw (with the
> same tuning) ?

I haven't compared the two functions over Z; I would personally prefer a
specialised ZM_mul that is as fast as possible, rather than implementing
it via gen_matmul_sw.  I do see that this is not very desirable from the
perspective of code duplication, though.

> One would need to write a bb_field instance for Z (the inv field is
> not used).

In fact, the operations that one needs for Strassen's algorithm don't
correspond directly to the set of operations defined by a bb_field: one
needs addition, subtraction, negation, zero element, and basecase matrix
multiplication (either subtraction or negation might be implemented via
the other, given addition and zero element).

> It is unfortunate that gen_matmul() takes a bb_field because it is
> also valid over rings. I am not sure what is the best way to handle
> that.

Maybe the bb_field and bb_ring structures could eventually be merged,
allowing the inv member to raise an error when it is applied to a
non-unit element?

Actually, I'm still unsure for what kind of applications we would really
want to have gen_matmul_sw.  At least in the cases where bb_field is
currently used (non-prime finite fields), Kronecker representation
combined with Strassen multiplication over Z is certainly much faster
than Strassen over the original field.  I would expect it to be up to
about 4 times as fast for matrices of size around 100, based on the
speedup it gives in my project and on the improvements I got while
implementing Kronecker substitution for classical matrix multiplication.
Also, ZM_mul_sw is definitely easier to tune.

Peter