Talk:Diophantine linear system solving
Totally lost
Some questions:
What does any of this actually mean?
What is a basis?
What is the standard basis?
What is a vector space?
What is the dimension of the vector space?
What is linear independence?
What is spanning property?
What is a spanning set?
What is a polynomial ring?
What is a monomial?
What is a monomial basis?
What is the Steinitz exchange lemma?
What is the axiom of choice?
What is the ultrafilter lemma?
What is the dimension theory?
I think you can see where I'm going with this, and I'm not even halfway through the first of, I dunno, 30,000 wikipedia pages I would have to read.
Let's try this: what does this actually mean?
2 1| 2 6 5| 2 7 6| 2
==>
P | Hnf 1 -1 0 | 1 1 1 0 -1 2 -0 | -0 4 5 -0 -2 2 1 | 0 0 0 1 -solution loop 7
I have a very vague grasp of what the input is, but the output is pure gibberish, and obviously "Transformation matrix P (left) and the Hermite normal form" elicits qs as above.
Detailed step-by-step inner workings of all 21 puzzles might be a start... --Pete Lomax (talk) 22:24, 24 December 2021 (UTC)
Sorry Pete, this task wasn't intended to swamp you in some murky math morass.
Let me reflect on this. I have a few busy days ahead, will be back sometime after Xmas.
But for now: if more people find this task...objectionable, it probably doesn't belong on RC after all.
--M.C., Udo e. (talk)
Thanks, I have slowly figured a couple of things out. That example means, I think, solve {2a+b=2, 6a+5b=2, 7a+6b=2} ==> the answer, from (-2 2)*-1, is {a=2,b=-2}. I was thinking (and about to say) that a proper set of unit tests on Reduce() would help, but actually what I think I really need right now is unit tests (/detailed examples) on Swop(), especially with what it is trying to do to d[], so I can properly visualise (and maybe even understand) it. --Pete Lomax (talk) 16:40, 25 December 2021 (UTC)
Also, you show the squares in the null space, can you explain why that might be useful? --Pete Lomax (talk) 15:48, 26 December 2021 (UTC)
Deserves to be on rc
Regarding objectional/belong, this task has more merit than 9/10 tasks that get added to rc. I won't deny there was a little (and irrelevant) grumpage (sorry), but that was much more about timing you could not possibly have known about. If a task author wants to see an algorithm in different programming languages, it belongs on rc, and that want should be incentive enough to take some extra trouble to explain it in layman terms. From my point of view I'd like to know more about how this might be used/prove useful in some future (non-rc) project, and that requires my understanding it well enough to debug and/or extend it. Despite now having posted a Phix entry, I don't remotely feel I'm done with this task yet, and it remains on my watchlist eagerly awaiting your updates. --Pete Lomax (talk) 15:01, 26 December 2021 (UTC)
Back again
and glad to see you've persisted.
As to the comment below your Phix entry:
the flipping signs are o.k. Because the null space vectors are solutions to
A·x = 0, they have 'ambiguous sign'. For example
x + 3y + 5z = 0 4x + 6y + 8z = 0
is solved with both [-1 2 -1]T and [1 -2 1]T. In fact with all t * [1 -2 1]T, with free parameter t taking every positive or negative integer value.
The lengths-squared are there just to help you quickly spot the shortest vector.
Thus in the final test, searching for the coefficients of a polynomial that has
-1.417... as root, the shortest vector is indeed the one you want, giving
f(x) = x9 + 3x7 - 5x5 - 7x3 + 9
For a unit test, see this 4x4 example on the home page of one of the LLLHnf inventors (Matthews). If you're there, also check out the LLL-page one level up, with many useful links (including his own BCMath and CALC implementations of LLLHnf).
But his example leaves out the λ-matrix and its denominator vector.
For good reason likely:
if I let my program output their state at the 17th iteration
Swapping Rows 1 and 2 0 0 0 0 3 0 0 0 (17) -1 9 0 0 -1 -27 29 0 / 6 69 182 1
it doesn't instantly enlighten me.
'Properly visualize' or even understand what Swop does to la(,) and d() is not so easy. I would say the Gram coefficients are updated to restore the almost orthogonal relation (disturbed by the swap) between the projections of the row vectors they represent, and orthogonal implies short vectors. But this is really clumsy and doesn't clarify anything.
My reasoning: the updating formulas being the result of an experimental refinement process over many iterations, they are terse to the point of being impenetrable, and best used as-they-are, copied verbatim from a reliable source. --Udo e. (talk)