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

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

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 found the following strange behaviour:

?  for(m=50,60,my(n=10*m);M=matrix(n,n,i,j,random(Mod(0,659)));gettime();M^2;print(n,":",gettime()))
500:240
510:196
520:357
530:524
540:645
550:761
560:805
570:841
580:921
590:1128
600:1464

Maybe it is a CPU cache issue.

Cheers,
Bill.