Talk:Diophantine linear system solving: Difference between revisions
Content added Content deleted
mNo edit summary |
(cleanup) |
||
Line 1: | Line 1: | ||
===Totally lost=== |
===Totally lost=== |
||
<snip> |
|||
Some questions:<br> |
|||
What does any of this actually mean?<br> |
|||
What is a basis?<br> |
|||
What is the standard basis?<br> |
|||
What is a vector space?<br> |
|||
What is the dimension of the vector space?<br> |
|||
What is linear independence?<br> |
|||
What is spanning property?<br> |
|||
What is a spanning set?<br> |
|||
What is a polynomial ring?<br> |
|||
What is a monomial?<br> |
|||
What is a monomial basis?<br> |
|||
What is the Steinitz exchange lemma?<br> |
|||
What is the axiom of choice?<br> |
|||
What is the ultrafilter lemma?<br> |
|||
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... --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 22:24, 24 December 2021 (UTC) |
|||
Sorry Pete, this task wasn't intended to swamp you in some murky math morass.<br/> |
|||
Let me reflect on this. I have a few busy days ahead, will be back sometime after Xmas.<br/> |
|||
But for now: if more people find this task...objectionable, it probably doesn't belong on RC after all. |
|||
--M.C., [[User:Udo_e._pops|Udo e.]] ([[User talk:Udo e. pops|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 <del>right now</del> 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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 16:40, 25 December 2021 (UTC) |
|||
Also, you show the squares in the null space, can you explain why that might be useful? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:01, 26 December 2021 (UTC) |
|||
===Back again=== |
|||
and glad to see you've persisted.<br/> |
|||
As to the comment below your Phix entry:<br/> |
|||
the flipping signs are o.k. Because the null space vectors are solutions to |
|||
<b>A</b>·<b>x</b> = <b>0</b>, they have 'ambiguous sign'. For example<br/> |
|||
x + 3y + 5z = 0 |
|||
4x + 6y + 8z = 0 |
|||
is solved with both [-1 2 -1]<sup>T</sup> and [1 -2 1]<sup>T</sup>. |
|||
In fact with all t * [1 -2 1]<sup>T</sup>, 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.<br/> |
|||
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 |
|||
{{math| <big>f(x) = x<sup>9</sup> + 3x<sup>7</sup> - 5x<sup>5</sup> - 7x<sup>3</sup> + 9</big>}} |
|||
For a unit test, see [http://www.numbertheory.org/lll/HERMITE4.html 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:<br/> |
|||
if I let my program output their state at the 17<sup>th</sup> 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 corresponding row vectors, and |
|||
orthogonal implies short vectors. But this is really clumsy and doesn't clarify anything. |
|||
⚫ | |||
over many iterations, they are terse to the point of being impenetrable, and best used |
over many iterations, they are terse to the point of being impenetrable, and best used |
||
as-they-are, copied ''verbatim'' from a reliable source. --[[User:Udo_e._pops|Udo e.]] |
as-they-are, copied ''verbatim'' from a reliable source. --[[User:Udo_e._pops|Udo e.]] |
||
([[User talk:Udo e. pops|talk]]) |
([[User talk:Udo e. pops|talk]]) |
||
:OK, I can live with that. Moved your clarification up, added the above, removed the difficulty tag, and cleaned up this page. I also added some extra comments to my input/output, which can be seen in the source code of the run online Phix link (but I gave up a bit towards the end). Happy New Year! --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 14:37, 31 December 2021 (UTC) |
Revision as of 14:38, 31 December 2021
Totally lost
<snip>
...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)
- OK, I can live with that. Moved your clarification up, added the above, removed the difficulty tag, and cleaned up this page. I also added some extra comments to my input/output, which can be seen in the source code of the run online Phix link (but I gave up a bit towards the end). Happy New Year! --Pete Lomax (talk) 14:37, 31 December 2021 (UTC)