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

2019-11-20, 12:28   #67
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

33·7·31 Posts

Quote:
 Originally Posted by uau BTW calculating determinants for each candidate separately may not be optimal. If you calculate the inverse matrix, you can then for example calculate the effect of swapping any two entries for a much cheaper per-candidate-pair price. So at least if you test many candidate pairs before actually doing a swap, this can be a win despite the extra cost of the inverse. Suppose you have a matrix A with determinant d and inverse matrix B. You consider swapping entries at position (r1, c1) and (r2, c2). v=A(r2,c2)-A(r1,c1). Let A' be the matrix with those entries swapped (add v to number at (r1,c1), subtract v from number at (r2,c2)). Then det(A') = d * ( (1+v*B(c1,r1))*(1-v*(B(c2,r2)) + v*v*B(c2,r1)*B(c1,r2) ) You can derive this by considering the product of B and A'. The determinant of this product is 1/det(A) * det(A'). On the other hand, you can directly calculate the determinant cheaply, since only two rows/columns (depending on whether you multiply from right or left) change from the identity matrix result of A*B, and the remaining zeros of the identity matrix eliminate most determinant terms.
That sort of idea was on my list of things to look at when I have time. I was more thinking of looking at the derivative with respect to each element but this probably works better.

2019-11-24, 02:05   #68
bsquared

"Ben"
Feb 2007

22·853 Posts

Quote:
 Originally Posted by yae9911 If your program solves A301371(7) and A301371(8), you may also try A085000(7) and A085000(8). For both results, independent confirmations are desirable.
Here is one for A085000(7):

Code:
39,46,04,26,20,09,32;
34,02,25,41,06,30,37;
29,24,49,01,23,14,35;
13,27,38,47,33,07,10;
05,18,12,21,45,31,43;
11,42,28,22,08,48,16;
44,15,19,17,40,36,03

2019-11-26, 17:30   #69
bsquared

"Ben"
Feb 2007

22·853 Posts

Quote:
 Originally Posted by uau BTW calculating determinants for each candidate separately may not be optimal. If you calculate the inverse matrix, you can then for example calculate the effect of swapping any two entries for a much cheaper per-candidate-pair price. So at least if you test many candidate pairs before actually doing a swap, this can be a win despite the extra cost of the inverse. Suppose you have a matrix A with determinant d and inverse matrix B. You consider swapping entries at position (r1, c1) and (r2, c2). v=A(r2,c2)-A(r1,c1). Let A' be the matrix with those entries swapped (add v to number at (r1,c1), subtract v from number at (r2,c2)). Then det(A') = d * ( (1+v*B(c1,r1))*(1-v*(B(c2,r2)) + v*v*B(c2,r1)*B(c1,r2) ) You can derive this by considering the product of B and A'. The determinant of this product is 1/det(A) * det(A'). On the other hand, you can directly calculate the determinant cheaply, since only two rows/columns (depending on whether you multiply from right or left) change from the identity matrix result of A*B, and the remaining zeros of the identity matrix eliminate most determinant terms.
Thanks - this is clever!

With this idea and other minor improvements my search code now runs over 5x faster. 9x9 determinant time is 0.38 usec and 9x9 inverse time is 0.52 usec (both home-grown Gauss-elimination based).

This has been a fun challenge! I hope to someday learn how the record determinants were found.

2019-11-26, 18:52   #70
SmartMersenne

Sep 2017

32×11 Posts

Quote:
 Originally Posted by bsquared I hope to someday learn how the record determinants were found.
Some technique probably but a lot of luck, too.

2019-11-26, 19:22   #71
SmartMersenne

Sep 2017

32·11 Posts

Quote:
 Originally Posted by bsquared This has been a fun challenge!
And sorry for not being able to share your enthusiasm. :(

2019-11-26, 22:58   #72
EdH

"Ed Hall"
Dec 2009

33·137 Posts

Quote:
 Originally Posted by SmartMersenne Some technique probably but a lot of luck, too.
I would have to favor technique over luck. If you've followed b2's adventure, you'll see a lot of tweaking to achieve the fastest processing of a search space. He probably covered that space in a much more efficient manner than many of us, myself included. And, it even sounds like b2 may have picked up some new methodology, too.

I've personally thrown a large number of CPUs at this, and various test methods, without success. I've found 921e6 and even 922e6 values and am finding the same ones regularly with my current methodology, but what I'm doing just isn't reaching the search space where I need to be. What I would need is a shift in my technique.

On the plus side, I have (re)learned quite a bit of Python along this venture, which is the gain that really matters. Getting my name on a list would be nice, but it will be lost in the past soon enough. Becoming more familiar with programming will take me further into the future. (And, it still might turn something up in these last few days.)

So, let's rejoice in the success of others, even if we've been frustrated by our own efforts.

2019-11-26, 23:37   #73
SmartMersenne

Sep 2017

32×11 Posts

Quote:
 Originally Posted by EdH So, let's rejoice in the success of others, even if we've been frustrated by our own efforts.
I am happy for him. I am just saying I am not having the same fun like him during this adventure.

2019-11-26, 23:38   #74
uau

Jan 2017

23×11 Posts

Quote:
 Originally Posted by bsquared With this idea and other minor improvements my search code now runs over 5x faster. 9x9 determinant time is 0.38 usec and 9x9 inverse time is 0.52 usec (both home-grown Gauss-elimination based).
You don't need to calculate the inverse from scratch either. Since BA' only has (at most) two columns changed from the identity matrix, restoring it to an identity matrix with row operations is about 2/9 as costly as doing that to a full matrix. And like generating an inverse with Gaussian elimination in the first place, applying to B the same row operations which turn BA' into the identity matrix will turn B into the inverse of A'.

There could be numerical stability issues with continuously modifying the same matrix like that, but the number of swaps doesn't seem to be so high that it'd be an issue in practice.

2019-11-27, 02:24   #75
LaurV
Romulan Interpreter

Jun 2011
Thailand

2·3·5·313 Posts

Quote:
 Originally Posted by EdH I would have to...
Excellent post!

2019-11-27, 06:23   #76
bsquared

"Ben"
Feb 2007

341210 Posts

Quote:
 Originally Posted by bsquared Here is one for A085000(7):
and one for a(8) with determinant 440970981670289 > 440960274696935

Code:
62,34,17,31,11,39,57,10;
40,52,7,45,54,3,22,37;
8,30,55,46,47,24,48,2;
20,1,13,56,33,51,35,50;
53,12,44,6,59,41,16,29;
43,32,60,49,4,21,9,42;
14,63,26,23,27,64,15,28;
19,36,38,5,25,18,58,61

2019-11-27, 20:00   #77
Kebbaj

"Kebbaj Reda"
May 2018
Casablanca, Morocco

83 Posts

Quote:
 Originally Posted by SmartMersenne Some technique probably but a lot of luck, too.
In my humble opinion there is only isotopy as a brutal technique to solve this question

 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 11:42.

Fri Apr 23 11:42:37 UTC 2021 up 15 days, 6:23, 0 users, load averages: 1.76, 1.67, 1.60