Talk:Defactoring algorithms: Difference between revisions

(One intermediate revision by the same user not shown)

Line 59:

from sympy import Matrix, normalforms

def ~~__hnf~~ (main):

def __hnf_col (main):

return np.flip (np.array (normalforms.hermite_normal_form (Matrix (np.flip (main)).T).T, dtype = int))

return np.flip (np.array (normalforms.hermite_normal_form (Matrix (np.flip (main))), dtype = int))

def __sat (main):

return np.rint (linalg.inv (~~__hnf~~ (main.T).T) @ main).astype (int)

return np.rint (linalg.inv (__hnf_col (main)) @ main).astype (int)

</syntaxhighlight>

Line 126:

::::::: You can find an example of us computing the entire thing by hand in the article. No pseudoinverse is required. --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 22:12, 10 February 2023 (UTC)

:::::::: Oh, allow me to correct myself. After some trial and errors it turns out the pseudoinverse doesn't get you the unimodular matrix, but a singular matrix, so it doesn't work. The correct way seems to be using the augmented matrix to track the elementary row operations in HNF: (A|I) → (H|U), as you pointed out and as one of them showed in the development thread. Here's my implementation of the column Hermite method:

:::::::: <syntaxhighlight lang="python">

def __sat (main):

r = Matrix (main).rank ()

unimodular = __hnf_col (np.vstack ((main, np.eye (main.shape[1], dtype = int))))[r:]

return np.rint (linalg.inv (unimodular)[:r]).astype (int)

</syntaxhighlight>

:::::::: As I said, "Hermite decomposition" isn't a single operation. Here it involves concatenation, HNF, and slice, tho it doesn't involve the pseudoinverse. Compare Pernet-Stein:

:::::::: <syntaxhighlight lang="python">

def __sat (main):

r = Matrix (main).rank ()

return np.rint (linalg.inv (__hnf_col (main)[:, :r]) @ main).astype (int)

</syntaxhighlight>

:::::::: Note the slice and thus computing the rank are redundant; they're there just for futureproofness.

:::::::: [[User:FloraC|FloraC]] ([[User talk:FloraC|talk]]) 10:58, 11 February 2023 (UTC)

:::::::: Edit: update the code to adopt column-style HNF so as to get rid of all the transpositions.

:::::::: [[User:FloraC|FloraC]] ([[User talk:FloraC|talk]]) 07:08, 15 February 2023 (UTC)

@@ Line 59: / Line 59: @@
 from sympy import Matrix, normalforms
-def __hnf (main):
+def __hnf_col (main):
-     return np.flip (np.array (normalforms.hermite_normal_form (Matrix (np.flip (main)).T).T, dtype = int))
+     return np.flip (np.array (normalforms.hermite_normal_form (Matrix (np.flip (main))), dtype = int))
 def __sat (main):
-     return np.rint (linalg.inv (__hnf (main.T).T) @ main).astype (int)
+     return np.rint (linalg.inv (__hnf_col (main)) @ main).astype (int)
 </syntaxhighlight>
@@ Line 126: / Line 126: @@
 ::::::: You can find an example of us computing the entire thing by hand in the article. No pseudoinverse is required. --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 22:12, 10 February 2023 (UTC)
+:::::::: Oh, allow me to correct myself. After some trial and errors it turns out the pseudoinverse doesn't get you the unimodular matrix, but a singular matrix, so it doesn't work. The correct way seems to be using the augmented matrix to track the elementary row operations in HNF: (A|I) → (H|U), as you pointed out and as one of them showed in the development thread. Here's my implementation of the column Hermite method:
+:::::::: <syntaxhighlight lang="python">
+def __sat (main):
+    r = Matrix (main).rank ()
+    unimodular = __hnf_col (np.vstack ((main, np.eye (main.shape[1], dtype = int))))[r:]
+    return np.rint (linalg.inv (unimodular)[:r]).astype (int)
+</syntaxhighlight>
+:::::::: As I said, "Hermite decomposition" isn't a single operation. Here it involves concatenation, HNF, and slice, tho it doesn't involve the pseudoinverse. Compare Pernet-Stein:
+:::::::: <syntaxhighlight lang="python">
+def __sat (main):
+    r = Matrix (main).rank ()
+    return np.rint (linalg.inv (__hnf_col (main)[:, :r]) @ main).astype (int)
+</syntaxhighlight>
+:::::::: Note the slice and thus computing the rank are redundant; they're there just for futureproofness.
+:::::::: [[User:FloraC|FloraC]] ([[User talk:FloraC|talk]]) 10:58, 11 February 2023 (UTC)
+:::::::: Edit: update the code to adopt column-style HNF so as to get rid of all the transpositions.
+:::::::: [[User:FloraC|FloraC]] ([[User talk:FloraC|talk]]) 07:08, 15 February 2023 (UTC)