mersenneforum.org November 2019
 Register FAQ Search Today's Posts Mark Forums Read

2019-11-15, 18:04   #45
SmartMersenne

Sep 2017

10101102 Posts

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

2019-11-15, 18:33   #46
bsquared

"Ben"
Feb 2007

3,361 Posts

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

 2019-11-15, 19:49 #47 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·2,897 Posts 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?
2019-11-15, 20:19   #48
bsquared

"Ben"
Feb 2007

D2116 Posts

Quote:
 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).

 2019-11-15, 22:46 #49 yae9911     "Hugo" Jul 2019 Germany 3110 Posts 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: Code: 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
2019-11-16, 02:31   #50
Dieter

Oct 2017

11000112 Posts

Quote:
 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: Code: 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.

2019-11-17, 11:01   #51
yae9911

"Hugo"
Jul 2019
Germany

31 Posts

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

 2019-11-17, 12:51 #52 LaurV Romulan Interpreter     Jun 2011 Thailand 100011101111002 Posts 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). Code: \\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,]), ) ); }
2019-11-17, 13:05   #53
SmartMersenne

Sep 2017

2×43 Posts

Quote:
 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!

 2019-11-17, 14:05 #54 yae9911     "Hugo" Jul 2019 Germany 3110 Posts 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.
 2019-11-17, 14:07 #55 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·2,897 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Puzzles 5 2018-12-03 13:31 Batalov Puzzles 3 2017-12-08 14:55 Xyzzy Puzzles 1 2016-12-06 16:41 R. Gerbicz Puzzles 3 2015-12-01 17:48 Xyzzy Puzzles 1 2014-12-02 17:40

All times are UTC. The time now is 19:39.

Wed Jan 20 19:39:38 UTC 2021 up 48 days, 15:50, 0 users, load averages: 4.09, 4.26, 4.14