|Bill Allombert on Sat, 25 Apr 2015 15:20:10 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Strassen multiplication over the integers|
On Sat, Apr 25, 2015 at 11:49:49AM +0200, Peter Bruin wrote: > Bonjour, > > I have been working on a PARI implementation of Strassen's algorithm for > matrix multiplication (more precisely, Winograd's variant, which uses > fewer additions), in particular over the integers. This has complexity > O(n^(log_2(7)) (instead of the classical O(n^3)) for n x n-matrices. > > The code is in the attached ZM_mul_sw.patch; a program for tuning it is > in tune.c, and the output of running this tuning program on my laptop > (x86_64 Core i5-4210M with Gentoo GNU/Linux and PARI 2.8.0-development) > is in tune.txt. Hello Peter, I have applied your patch with very minor modifications. However there are things that need to be done. - ZM_sqr should be implemented as well. - gmul or RgM_mul should be changed to call ZM_mul when appropriate. - the tuning should depend on the size of the coefficients, I think. - ideally the program src/test/tune.c should deal with the tuning. This program deal with dependencies between tuning parameters. - Most of the code is fairly generic, so maybe there could be a gen_matmul_sw function. A note: do not use cgiv on a recursive type, it does not work. Thanks a lot for your contribution to PARI! Bill.