Mathematica Asked by Stanley Rabinowitz on July 22, 2020
Most of the time when I use FindIntegerNullVector with inexact numbers, I get useful results.
But occasionally, it seems to miss finding a simple null vector.
Example:
a = 13.4414592345679;
b = 3.402468500410153;
c = 3.7037718641975403;
d = 12.34799099999999;
Quiet[FindIntegerNullVector[{a b, c d}, 10]]
finds no integer relationship even though a b-c d < 3 * 10^(-14).
I was expecting a result of {1, -1}.
What am I doing wrong and/or how can I fix this line so that it will recognize that the two arguments are approximately equal?
I have tried varying WorkingPrecision and ZeroTest.
This seems to work on the case at hand:
FindIntegerNullVector[SetPrecision[{a b, c d}, 15] 10]
(* {1, -1} *)
But why the precision 15
? The problem is to find, for real numbers $A$ and $B$, integers $x$ and $y$ such that
$$Ax+By=0 ,.tag{1}$$
Suppose $A^*,,B^*$ are floating-point approximations of $A,B$ resp. Then the problem is to find an integer point $(x^*,y^*)$ such that the line in the real $xy$-plane given by equation (1) passes "close enough" to $(x^*,y^*)$, where close enough depends on the error of the approximations $A^*,,B^*$. FindIntegerNullVector
does this with some notion of "close enough" depending on the precision of the input.
Below is an adaptation fINS
of an example in the documentation for LatticeReduce
to solve the FindIntegerNullVector
problem that diminishes the precision until we get a solution with a relatively small error (rough 1 ulp at the current precision). In the couple of tests in which there is an integer null relation, it tends to overestimate the reduction in precision needed (pick a precision that is lower than necessary). In the one totally random example, it did the reverse. Consequently, fINS
only approximates the precision needed for FindIntegerNullVector
to reproduce the result of LatticeReduce
/fINS
.
fINS[z_?VectorQ] := Module[{a, b, err},
a = IdentityMatrix[Length[z]];
b = {{2, 2, 2}}; (* dummy values: fails While test *)
err = 1;
While[Abs[b[[1, -1]]] > 1,
b = PadRight[a, {Automatic, Length@z + 1},
List /@ Round[-10^Precision[z]/err*z]]; (* scale the FP vec z and round *)
(* which simulates FP round-off *)
(* in integers *)
b = LatticeReduce[b];
If[b[[1, -1]] != 0, err *= b[[1, -1]]];
];
{b[[1, ;; -2]], 10.^-Precision[z] * err}
];
Note fINS
returns the null sequence and the estimate of the error tolerance needed.
{sol, tol} = fINS[{a b, c d}]
(* {{-1, 1}, 2.84217*10^-14} *)
Map the tolerance to Precision
:
reltol = Abs@tol/Max@Abs@{a b, c d};
prec = -Log10[reltol]
(* 15.2066 *)
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
(* {1, -1} *)
We can increase the precision a little; too much, and FindIntegerNullVector
fails:
prec = -Log10[reltol/2];
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
prec = -Log10[reltol/5];
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
(* {1, -1} *)
FindIntegerNullVector::norel: There is no integer null vector for {45.73414164516444,45.73414164516441} with norm less than or equal to 10.
(* FindIntegerNullVector[{45.73414164516444, 45.73414164516441}, 10] *)
LatticeReduce
example perturbed by noise.First, the exact problem:
FindIntegerNullVector[{Cos[4], Cos[1]^4, Cos[1]^2, 1}]
(* {1, -8, 8, -1} *)
The perturbed problem: a tolerance of around 10^-14
or precision of around 14
should be needed.
SeedRandom[1];
coeffs = N@{Cos[4], Cos[1]^4, Cos[1]^2, 1} + RandomReal[10^-14, 4];
{sol, tol} = fINS[coeffs]
reltol = Abs@tol/Max@Abs@coeffs;
prec = -Log10[reltol];
(* {{-1, 8, -8, 1}, 6.15064*10^-13} *)
FindIntegerNullVector[SetPrecision[coeffs, prec]]
FindIntegerNullVector[coeffs]
(* {1, -8, 8, -1} {78257927, -626063069, 626063140, -78257876} *)
In this case the precision can be raised more:
prec = -Log10[reltol/10];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
prec = -Log10[reltol/50];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
(* {1, -8, 8, -1} {-36655, -42915, 67969, -40144} *)
No relationship is expected but FindIntegerNullVector
finds one with large norm. The precision in this particular case needs to be lowered to get FindIntegerNullVector
to return the same result as fINS
SeedRandom[0];
coeffs = RandomReal[1, 4];
{sol, tol} = fINS[coeffs]
reltol = Abs@tol/Max@Abs@coeffs;
prec = -Log10[reltol ];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
FindIntegerNullVector[coeffs]
(* {{6, -6, -1, 1}, 0.0000326167} <-- prec ~ 4.3 {-12, 7, 0, 6} {-18811, -20158, 21650, 18102} *)
To get the smaller norm solution, we need to lower the precision:
Norm /@ N@{{-6, 6, 1, -1}, {-12, 7, 0, 6}}
(* {8.60233, 15.1327} *)
FindIntegerNullVector[SetPrecision[coeffs, prec], 12]
FindIntegerNullVector[SetPrecision[coeffs, prec - 0.3], 12]
FindIntegerNullVector::rnf: FindIntegerNullVector has not found an integer null vector for {0.6525,0.6331,0.6828,0.5664} with norm less than or equal to 12.
(* FindIntegerNullVector[{0.6525, 0.6331, 0.6828, 0.5664}, 12] *)
(* {-6, 6, 1, -1} *)
Correct answer by Michael E2 on July 22, 2020
A solution is give the built-in the right amout of toleranz with a constant in another dimension:
FindIntegerNullVector[{a b, c d, 10^-14}, 10]
{1, -1, -3}
Answered by Steffen Jaeschke on July 22, 2020
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP