You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
however, direct multiplication with calculator shows, that element (6, 6) of the HNF in this case would be 18446744073728005951 instead of 18454335 (i.e. the answer has even a self-contradiction). Numpy multiplication doesn't work normally in this case due to int overflow; seems, an implementation has the same problem.
@SiggyLaewsky Thank you for reporting the example to cause an overflow in calculating HNF.
In fact, the current algorithm for HNF and SNF will fail due to overflow in matrix multiplications. A possible solution is to use modular arithmetic, but I am not fully understand the modular-arithmetic algorithm to compute HNF and SNF so far...
All functions sometimes return a wrong answer even for small-size matrices with small values. For instance:
For matrix
[[ 1 -10 0 4 2 -3 6]
[ -6 -8 -3 -2 7 0 -8]
[ -8 0 0 -4 8 10 -5]
[ 8 -3 3 9 9 10 6]
[ -5 -3 -9 10 -4 7 9]
[ -4 -9 -9 -5 2 0 1]
[ 4 2 -5 1 7 -10 -1]]
function column_style_hermite_normal_form provides output
[[-346925671050097202 -252755 -466370
-630998 -478778 -600398
-659835]
[ 835296760844636953 608561 1122884
1519261 1152759 1445585
1588692]
[-479143188193987710 -349083 -644109
-871479 -661246 -829217
-911306]
[ 191046112789960095 139188 256822
347480 263655 330629
363360]
[1118641869143326448 814994 1503783
2034617 1543792 1935949
2127600]
[-828222439379453903 -603407 -1113374
-1506394 -1142996 -1433342
-1575237]
[ 535626295318601958 390234 720039
974212 739196 926968
1018734]],
[[ 1 0 0 0 0 0 0]
[ 0 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0]
[ 0 0 0 1 0 0 0]
[ 0 0 0 0 1 0 0]
[ 0 0 0 0 0 1 0]
[18454335 13439499 24797837 33551452 25457599 31924387 35084770]]
however, direct multiplication with calculator shows, that element (6, 6) of the HNF in this case would be 18446744073728005951 instead of 18454335 (i.e. the answer has even a self-contradiction). Numpy multiplication doesn't work normally in this case due to int overflow; seems, an implementation has the same problem.
To compare, the correct answer is
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
20000231 13439499 24797837 33551452 25457599 31924387 35084770.
--
All the best,
Siggy Laewsky
The text was updated successfully, but these errors were encountered: