Talk:Diophantine linear system solving: Difference between revisions

Content added Content deleted
(→‎Totally lost: why show squares in null space?)
(Back again)
Line 50: Line 50:
how this might be used/prove useful in some future (non-rc) project, and that requires my understanding it well enough
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)
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>&#183;<b>x</b>&nbsp;=&nbsp;<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|&nbsp;<big>f(x) &#61; 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 &#955;-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 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. --[[User:Udo_e._pops|Udo e.]]
([[User talk:Udo e. pops|talk]])
Retrieved from "https://rosettacode.org/wiki/Talk:Diophantine_linear_system_solving"