Bill Allombert on Thu, 26 Oct 2017 19:00:50 +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 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