Talk:Defactoring algorithms: Difference between revisions

← Older edit Newer edit →

VisualWikitext

@@ Line 41: / Line 41: @@
 ::: --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 17:13, 9 February 2023 (UTC)
+:::: I'm afraid your conclusion (that the column Hermite defactoring was the superior method) was critically affected by Mathematica, the tool of your choice, as it wraps "Hermite decomposition" as a single operation where you simultaneously get both the Hermite normal form and the unimodular matrix. In general, this isn't the case. For example, in SymPy, you have direct access to the function HNF: A → H. You gotta obtain the unimodular matrix U = HA<sup>+</sup> from UA = H. So using the unimodular matrix involves three steps:
+::::# find H = HNF (A);
+::::# find the pseudoinverse A<sup>+</sup>;
+::::# Multiply them.
+:::: By contrast, the Pernet-Stein method only needs H i.e. the first step at this point. It could be simplified a bit in an algorithm that's designed to return both, but the unimodular matrix is still something more than the HNF itself (see discussion at [https://github.com/sympy/sympy/pull/22845 add igcdLLL to numbers by smichr · Pull Request #22845 · sympy/sympy]). Your comparsion made it as if they were the same.
+:::: Then you actually use U<sup>-1</sup> instead of U, so to sum it up you're taking an inverse after taking a pseudoinverse, with multiplication involved also. That looks to me like there's a lot of back and forth in it.
+:::: That's why I chose to implement Pernet-Stein in my code:
+:::: <syntaxhighlight lang="python">
+import numpy as np
+from scipy import linalg
+from sympy import Matrix
+def __hnf (main):
+    return np.flip (np.array (normalforms.hermite_normal_form (Matrix (np.flip (main)).T).T, dtype = int))
+def __sat (main):
+    return np.rint (linalg.inv (__hnf (main.T).T) @ main).astype (int)
+</syntaxhighlight>
+:::: where <code>__hnf</code> is just a wrapper for A → H due to SymPy's unusual implementation as we know. Note it somehow removes the extra rows of zeros already.
+:::: So my finding is a 180-degree turn from yours, and I'll insist that Pernet-Stein be included. To be clear I never intended to remove any of these methods, but I just want every word to count. For example, in the first section I think one obvious enfactoring and one hidden enfactoring are enough to show the possibility as well as the difficulty of the heuristic method.
+:::: I accept the other suggestions and I'm dropping the idea of starting anew or changing the title.
+:::: [[User:FloraC|FloraC]] ([[User talk:FloraC|talk]]) 10:58, 10 February 2023 (UTC)