Re: Linear algebra via CUP decomposition and reduction to matrix multiplication

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

On Mon, Mar 27, 2017 at 11:49:45PM +0200, Bill Allombert wrote:
> On Thu, Mar 09, 2017 at 11:02:43AM +0100, Peter Bruin wrote:
> > Hello,
> > 
> > Since matrix multiplication over Flxq fields is already reduced to
> > matrix multiplication over Z via Kronecker substition, and since we have
> > Strassen multiplication over Z, linear algebra over Flxq fields now
> > becomes asymptotically faster than O(n^3), namely O(n^{log_2(7)}).
> > Strassen multiplication over Fl fields is not implemented yet but would
> > be easy to add, although the matrix sizes for which it will have a
> > substantial effect will probably be larger than over Flxq fields.
> 
> Yes, it would be nice to implement it.

I implemented it in commit 31e6a3d50b.
Please check if you see some optimization to do.
I only avoided the call to shallowmatconcat.

The major speed up comes from the better use of the CPU cache.
Even doing a single Strassen step can get a 4x speed up.

p=nextprime(2^63);M=matrix(1000,1000,i,j,random(Mod(1,p)));
M^2;
##

Without Strassen:        13,212 ms
With one Strassen step:   3,028 ms.
With recursive Strassen:  1,681 ms

One Strassen step should only gives a speed-up of 12.5%
So this is very useful.

Cheers,
Bill