Diophantine linear system solving: Difference between revisions

Content added Content deleted
(New task and FreeBasic solution.)
 
mNo edit summary
Line 16: Line 16:
How is this task different from [[Gaussian_elimination| Gaussian elimination]]?
How is this task different from [[Gaussian_elimination| Gaussian elimination]]?
We now need a triangularization method that doesn't introduce fractions.
We now need a triangularization method that doesn't introduce fractions.
The LLLHnf algorithm adapts Lenstra-Lenstra-Lovász (LLL) lattice basis reduction
The LLLHnf algorithm adapts Lenstra-Lenstra-Lovász lattice basis reduction
to put the transpose of the input system into Hermite normal form,
to put the transpose of the input system into Hermite normal form,
the integer analogue of the usual [[Reduced_row_echelon_form| reduced row echelon form]].
the integer analogue of the usual [[Reduced_row_echelon_form| reduced row echelon form]].
Line 191: Line 191:
0 0 0 0 -1 1 1 0
0 0 0 0 -1 1 1 0
0 0 0 0 0 -1 -1 0
0 0 0 0 0 -1 -1 0
'Aij = i^2 * j^3 + i + j (example 7.4)
'Hnf(A) with Aij = i^3 * j^2 + i + j (example 7.4)
10
10
10
10
Line 435: Line 435:




'Aij = i^2 * j^3 + i + j (example 7.4)
'Hnf(A) with Aij = i^3 * j^2 + i + j (example 7.4)
P | Hnf
P | Hnf
-10 -8 -5 1 2 3 5 3 0 -4 0 | 1 0 7 22 45 76 115 162 217 280 0
-10 -8 -5 1 2 3 5 3 0 -4 0 | 1 0 7 22 45 76 115 162 217 280 0
Retrieved from "https://rosettacode.org/wiki/Diophantine_linear_system_solving"