Re: FlxqM_mul_Kronecker

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Feb 07, 2015 at 01:22:47PM +0100, Peter Bruin wrote:
> Bonjour,
> 
> Here is a patch to add a new (private) function FlxqM_mul_Kronecker that
> I have been working on since the Atelier PARI/GP in January.  It uses
> Kronecker substitution to multiply matrices over non-prime finite fields
> of small characteristics.  Over the range of matrices I tested it on, it
> is on average 60%-80% faster than the existing FlxqM_mul; for some
> examples, the speedup is up to 4-5 times.
> 
> When multiplying m x n matrices by n x k matrices, the speedup is
> already noticeable (up to 20%) when n >= 2 (again on average over a
> range of reasonable field sizes; in a small number of "unlucky" cases,
> it is up to 20% slower because it has to use larger integers than
> Flx_mulspec because several products must be added).
> 
> The new FlxqM_mul_Kronecker is called by FlxqM_mul (and hence by FFM_mul
> and gmul) precisely when n >= 2.  All new functions are covered by the
> new tests.

Thanks ! I have created a branch peter-FlxqM_mul_Kronecker with your patch.

We will look at it.

Cheers,
Bill.