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.


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.