Re: Linear algebra via CUP decomposition and reduction to matrix multiplication

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

Hi Bill,

I can confirm this strange behaviour: on one machine I get

? for(m=50,80,my(n=10*m);M=matrix(n,n,i,j,random(Mod(0,659)));gettime();M^2;print(n,":",gettime()))
500:168
510:176
520:188
530:252
540:337
550:396
560:245
570:336
580:468
590:469
600:533
610:644
620:637
630:717
640:745
650:824
660:865
670:973
680:1008
690:1105
700:1184
710:1280
720:1401
730:1412
740:1493
750:1544
760:1661
770:3433
780:1793
790:1860
800:1961

and on another one (although here it seems less extreme at first sight):

? for(m=50,80,my(n=10*m);M=matrix(n,n,i,j,random(Mod(0,659)));gettime();M^2;print(n,":",gettime()))
500:272
510:244
520:421
530:588
540:721
550:877
560:905
570:965
580:1032
590:1264
600:1632
610:1493
620:1616
630:1900
640:1992
650:1804
660:2457
670:2284
680:2897
690:2941
700:2345
710:3164
720:3433
730:3648
740:3800
750:3913
760:4125
770:4276
780:4461
790:4472
800:4833

Peter


Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

> 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.