mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-11-20, 12:28   #67
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

Quote:
Originally Posted by uau View Post
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.
henryzz is offline   Reply With Quote
Old 2019-11-24, 02:05   #68
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·3·557 Posts
Default

Quote:
Originally Posted by yae9911 View Post
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
bsquared is offline   Reply With Quote
Old 2019-11-26, 17:30   #69
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101000011102 Posts
Default

Quote:
Originally Posted by uau View Post
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.
bsquared is offline   Reply With Quote
Old 2019-11-26, 18:52   #70
SmartMersenne
 
Sep 2017

2·43 Posts
Default

Quote:
Originally Posted by bsquared View Post
I hope to someday learn how the record determinants were found.
Some technique probably but a lot of luck, too.
SmartMersenne is offline   Reply With Quote
Old 2019-11-26, 19:22   #71
SmartMersenne
 
Sep 2017

2·43 Posts
Default

Quote:
Originally Posted by bsquared View Post
This has been a fun challenge!
And sorry for not being able to share your enthusiasm. :(
SmartMersenne is offline   Reply With Quote
Old 2019-11-26, 22:58   #72
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

22·863 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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.
EdH is offline   Reply With Quote
Old 2019-11-26, 23:37   #73
SmartMersenne
 
Sep 2017

8610 Posts
Default

Quote:
Originally Posted by EdH View Post
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.
SmartMersenne is offline   Reply With Quote
Old 2019-11-26, 23:38   #74
uau
 
Jan 2017

1178 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
uau is offline   Reply With Quote
Old 2019-11-27, 02:24   #75
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

Quote:
Originally Posted by EdH View Post
I would have to...
Excellent post!
LaurV is offline   Reply With Quote
Old 2019-11-27, 06:23   #76
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·3·557 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
bsquared is offline   Reply With Quote
Old 2019-11-27, 20:00   #77
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5810 Posts
Exclamation

Quote:
Originally Posted by SmartMersenne View Post
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
Kebbaj is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 17:47.

Sat Nov 28 17:47:38 UTC 2020 up 79 days, 14:58, 3 users, load averages: 1.42, 1.36, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.