November 2019

[SmartMersenne]

Originally Posted by bsquared

Largest for me is now 925119207 but I have no other ideas for how to find larger values. I'm just throwing CPUs at it now.

Originally Posted by bsquared

Since the recent pseudo-hints I've looked more at matrix structure but discovered nothing useful. I'm tending to either immediately rediscover det=929587995 circulant latin squares or find nothing but singular matrices...

I thought you already found 925119207.

[bsquared]

Originally Posted by SmartMersenne

I thought you already found 925119207.

That's my best pseudo-random matrix, yes. 929587995 is the determinant of the maximal circulant Latin square and re-finding it isn't valid for this challenge. What I meant was that when I started trying to generate matrices with structure (symmetric, etc.) then I tended to either find 929587995 or 0... i.e., not useful.

[henryzz]

What is a good speed for calculating a 9x9 determinant? I believe I am currently taking around 5-7 microseconds. Is this reasonable or should I be putting effort into speeding this up?

[bsquared]

Originally Posted by henryzz

What is a good speed for calculating a 9x9 determinant? I believe I am currently taking around 5-7 microseconds. Is this reasonable or should I be putting effort into speeding this up?

On my machine MATLAB takes about 1.2 us per 9x9. My C code takes about half that. Depending a little on the differences between our computers, you seem to be in the right ballpark (same OOM).

[yae9911]

To contribute something more substantial than "pseudo-hints": On my aged Windows computer one 9x9 determinant takes ~ 6.2e-7 s, using 8 byte floats and Gauss elimination from LAPACK running on one core with PARI checking ispseudoprime on a second core. I.e. 10^9 determinants in 10 minutes CPU. For comparison of machine speed: yafu-1.34 tune tells me:

SIQS on c100: ... 

elapsed time for ~10k relations of c100 = 54.6251 seconds.
extrapolated time for complete factorization = 8707.0082 seconds
... WIN64 -         Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz

[Dieter]

Originally Posted by yae9911

To contribute something more substantial than "pseudo-hints": On my aged Windows computer one 9x9 determinant takes ~ 6.2e-7 s, using 8 byte floats and Gauss elimination from LAPACK running on one core with PARI checking ispseudoprime on a second core. I.e. 10^9 determinants in 10 minutes CPU. For comparison of machine speed: yafu-1.34 tune tells me:

SIQS on c100: ... 

elapsed time for ~10k relations of c100 = 54.6251 seconds.
extrapolated time for complete factorization = 8707.0082 seconds
... WIN64 -         Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz

That‘s exactly my time. PC from 2012, Gauss elimination,, 8 Byte floats, 64-bit assembly, Linux.

[yae9911]

Originally Posted by bsquared

That's my best pseudo-random matrix, yes. 929587995 is the determinant of the maximal circulant Latin square and re-finding it isn't valid for this challenge. What I meant was that when I started trying to generate matrices with structure (symmetric, etc.) then I tended to either find 929587995 or 0... i.e., not useful.

Among the examples of structured matrices with determinant value 929587995, were there also some that did not have the very special structure of Latin squares? That would be a justification for my somewhat strange-seeming formulation of the challenge question.

[LaurV]

You guys are quite good. I actually have no idea how to solve this, beside of "random" or "brute force". The "random" brings you quite fast close to 900M (in just few hours, or less then an hour, depending on your luck), but to advance more, you really need a "clever" way to "improve" the arrangement. By random I mean what I described in my first post, change two elements, and keep the matrix with the highest det, like in the code below (which can be launched with parameters 0 to 3, we played together for half a day, but gave up after being stuck for some long time without any progress. My "best score" is just barely under 900M. I will post the code, some of you may have enough patience, or a lot of more luck... (this is not easy, it is hard, you really need a lot of patience or a lot of luck, that is why I do not consider it spoiler, the code is just some shitty stuff that anybody could put together).

\\value to beat (loophole) = 923062279
ponder1911(initial=0)=
{
  my(m,x,l,c,d);
  if(initial==0,        \\start from det=0, fast growing for small values till about 500M
        m=[1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9],
  /*else*/
    if(initial==1,      \\det=215233605, but moving fast to over 700M
        m=[1, 2, 3, 4, 5, 6, 7, 8, 9;
           9, 1, 2, 3, 4, 5, 6, 7, 8;
           8, 9, 1, 2, 3, 4, 5, 6, 7;
           7, 8, 9, 1, 2, 3, 4, 5, 6;
           6, 7, 8, 9, 1, 2, 3, 4, 5;
           5, 6, 7, 8, 9, 1, 2, 3, 4;
           4, 5, 6, 7, 8, 9, 1, 2, 3;
           3, 4, 5, 6, 7, 8, 9, 1, 2;
           2, 3, 4, 5, 6, 7, 8, 9, 1],
    /*else*/
      if(initial==2,    \\det=215233605, difficult to move
        m=[1, 2, 3, 4, 5, 6, 7, 8, 9;
           2, 3, 4, 5, 6, 7, 8, 9, 1;
           3, 4, 5, 6, 7, 8, 9, 1, 2;
           4, 5, 6, 7, 8, 9, 1, 2, 3;
           5, 6, 7, 8, 9, 1, 2, 3, 4;
           6, 7, 8, 9, 1, 2, 3, 4, 5;
           7, 8, 9, 1, 2, 3, 4, 5, 6;
           8, 9, 1, 2, 3, 4, 5, 6, 7;
           9, 1, 2, 3, 4, 5, 6, 7, 8],
      /*else*/          \\det=929587995 this is the record for Latin squares, to beat to get two stars
        m=[1, 2, 4, 8, 6, 7, 5, 3, 9;
           9, 1, 2, 4, 8, 6, 7, 5, 3;
           3, 9, 1, 2, 4, 8, 6, 7, 5;
           5, 3, 9, 1, 2, 4, 8, 6, 7;
           7, 5, 3, 9, 1, 2, 4, 8, 6;
           6, 7, 5, 3, 9, 1, 2, 4, 8;
           8, 6, 7, 5, 3, 9, 1, 2, 4;
           4, 8, 6, 7, 5, 3, 9, 1, 2;
           2, 4, 8, 6, 7, 5, 3, 9, 1]
      )
    )
  );
  x=matdet(m);
  print(x";\n "m[1,]"\n "m[2,]"\n "m[3,]"\n "m[4,]"\n "m[5,]"\n "m[6,]"\n "m[7,]"\n "m[8,]"\n "m[9,]);
  while(1,
    l=random(9)+1;
    c=random(9)+1;
    d=m[l,c];
    m[l,c]=m[c,l];
    m[c,l]=d;
    d=matdet(m);
    if(d>x,
      x=d;
      print(x";\n "m[1,]"\n "m[2,]"\n "m[3,]"\n "m[4,]"\n "m[5,]"\n "m[6,]"\n "m[7,]"\n "m[8,]"\n "m[9,]),
    )
  );
}

[SmartMersenne]

Originally Posted by LaurV

... we played together for half a day, but gave up after being stuck for some long time without any progress

I have been running it on two laptops non-stop for more than a week with many different approaches and still no luck!

[yae9911]

I am really happy that you have a little fun with the problem. I can give you a simple tip on random exchanges of matrix entries: Instead of just greedily looking for improvements to the determinants, it's worth accepting also reductions of the determinant value at the beginning. The acceptance probability of moves in the "wrong" direction is governed by a decaying threshold similar to the cooling down of a melt in a furnace. One can embed this in a framework program that performs a temperature control. The keyword to look for is simulated annealing.


If implemented properly (not more than 5 lines of code ) it will give you a dramatic increase in search progress and much more fun than just watching the awful performance of pure random swaps.

[henryzz]

I have also tried two random swaps(4 cells changing). This takes a lot of solutions a bit further but slows it down massively. Currently, my best is 917e6. I should probably only run the double swap if single swaps take it past a threshold.