November 2019

[henryzz]

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.

[bsquared]

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

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]

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.

[SmartMersenne]

Originally Posted by bsquared

I hope to someday learn how the record determinants were found.

Some technique probably but a lot of luck, too.

[SmartMersenne]

Originally Posted by bsquared

This has been a fun challenge!

And sorry for not being able to share your enthusiasm. :(

[EdH]

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 b²'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 b² 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.

[SmartMersenne]

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.

[uau]

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.

[LaurV]

Originally Posted by EdH

I would have to...

Excellent post!

[bsquared]

Originally Posted by bsquared

Here is one for A085000(7):

and one for a(8) with determinant 440970981670289 > 440960274696935

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

[Kebbaj]

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