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 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.

On the paridev machine, I get different result
?  for(m=70,80,my(n=10*m);M=matrix(n,n,i,j,random(Mod(0,659)));gettime();M^2;print(n,":",gettime()))
700:485
710:500
720:517
730:576
740:577
750:613
760:644
770:3168
780:885
790:777
800:1108

This is reproducible. Other slow dimensions are 761 and 779

Cheers,
Bill.