Bill Allombert on Mon, 27 Mar 2017 23:49:52 +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 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.