November 2019

[EdH]

You guys are making me feel better with your posts. I actually have a high of 916e6 with a poorer implementation of LaurV's concept (arrived at on my own, btw). Unfortunately, you're also encouraging me to take machines away from other projects.

Additional thoughts: I had already decided that there would be situations where swapping two elements could no longer increase the determinant, but my solution was (is currently) to start with an entirely new random matrix. Of course, the success still rests on pure luck at this point. . .

[SmartMersenne]

Originally Posted by 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.

Been there, done that. And with lots of tuning over the last couple of days... still no result.

[a1call]

Originally Posted by SmartMersenne

Been there, done that. And with lots of tuning over the last couple of days... still no result.

Ditto. It takes much more than sacrificing the pawn (accepting few step backs) to even surpass the threshold in a few days with more than a dozen cores.

I have tried sacrificing-few/many-prawns thousands and thousands of runs with the best Latin-Square solution as well as my own highest solution and gave up on that approach. Back to random swaps with better progress than sacrificing the pawn.

[a1call]

I think one positive tip (as if I have progressed enough to give them out, which I haven't) is not to discard/reject negative determinants as not-high-enough. A detriment will change sign each time you swap a row or column.

[bsquared]

Originally Posted by yae9911

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.

I'll have to check on that, but I don't think so.

Best by my search procedure so far is now 925432245.

[SmartMersenne]

I guess this is not for me as it involves luck. I was never lucky. In a previous puzzle, I had to guess the last two digits due to precision, so I tried everything. I got it at 96th trial (out of possible 100).

[a1call]

In the continuing series of tips from someone who hasn't cracked the lower threshold:
* If I had the time I would rewrite the code to shuffle diagonal and parallel to diagonal sets of cells rather than just cells. The logic behind this is that swaging rows and columns does not create any new determinant trials and swapping cells would have wasted efforts equivalents to swapping rows and columns. Swapping diagonals and their parallels should be the most/more efficient brute force approach.

[EdH]

Darn it! I was prepared to call off the search due to total inactivity, which would have let me get back to other things. But, I found that the "total inactivity" was self-inflicted by my poor programming. Upon a small adjustment, I outdid my previous high with 919685927, on the initial test run. Now I guess I'll still let this run awhile. . .

[bsquared]

For fun, since progress has pretty much stopped on the 9x9 problem, I thought I'd try to find maximal solutions on smaller problems (https://oeis.org/A301371). Happily, I've rediscovered both a(7) and a(8). a(7) took a couple minutes and a(8) a couple hours. But a(9) is not scaling the same :(

[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.

[uau]

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?

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.