Bill Allombert on Sun, 02 Apr 2017 13:34:36 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Linear algebra via CUP decomposition and reduction to matrix multiplication |
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.