Defactoring algorithms: Difference between revisions

Line 208:

</pre>

So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. Note that the <code>~~hnf~~</code> is only available in row-style, so we first transpose the matrix to convert it to column-style. The decomposition in Wolfram returns two items – the unimodular matrix, and the input matrix in Hermite normal form, in that order – and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we transpose it again to in effect undo the transposition we did at the beginning.

So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. Note that the <code>HermiteDecomposition[]</code> is only available in row-style, so we first transpose the matrix to convert it to column-style. The decomposition in Wolfram returns two items – the unimodular matrix, and the input matrix in Hermite normal form, in that order – and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we transpose it again to in effect undo the transposition we did at the beginning.

The next step is to invert that matrix, which is doable because it is unimodular; a key property of unimodular matrices is that they are always invertible, and because their determinant is ±1, if they contain all integer entries, their inverse will also contain all integer entries (which it does, and we need it to)<ref>Interesting tidbit regarding [[full-rank]] matrices and unimodular matrices: for square matrices, unimodularity implies full-rank, and while full-rank does not imply unimodularity, it does imply a non-zero determinant.</ref>.

Line 252:

===== Relationship with other defactoring methods =====

[[File:Comparison of defactoring algorithms.png|400px|thumb|right|~~A comparison~~ of defactoring ~~methods,~~ using ~~the function names built in to~~ Wolfram Language]]

[[File:Comparison of defactoring algorithms.png|400px|thumb|right|Comparison of defactoring algorithms using Wolfram Language. Notice how HermiteDecomposition simultaneously returns the HNF and the unimodular matrix]]

If ~~you describe~~ column Hermite defactoring as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite ~~...~~ inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until ~~you've achieved~~ Smith normal form, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.

If column Hermite defactoring is described as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite … inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until Smith normal form has been achieved, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.

According to Wolfram<ref>~~See:~~ https://reference.wolfram.com/language/ref/SmithDecomposition.html</ref>, "the Smith decomposition can often be found by two iterations of the Hermite decomposition". This notion is echoed in the Sage docs<ref>~~See:~~ https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html</ref>, which read, "Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation," remembered that saturation is the same as defactoring. The reason for the multiple applications of Hermite decomposition to achieve Smith normal form is that you ~~won't~~ necessarily get a diagonal matrix on the first go. But as we know from Smith defactoring, the center matrix of the Smith decomposition — the Smith normal form one — is not the target matrix, so its exact form is not necessary to achieve to accomplish defactoring.

According to Wolfram<ref>[https://reference.wolfram.com/language/ref/SmithDecomposition.html Wolfram Language Documentation | SmithDecomposition]</ref>, "the Smith decomposition can often be found by two iterations of the Hermite decomposition". This notion is echoed in the Sage docs<ref>[https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html Sage Reference Manual | Dense matrices over the integer ring]</ref>, which read, "Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation," remembered that saturation is the same as defactoring. The reason for the multiple applications of Hermite decomposition to achieve Smith normal form is that you will not necessarily get a diagonal matrix on the first go. But as we know from Smith defactoring, the center matrix of the Smith decomposition – the Smith normal form one – is not the target matrix, so its exact form is not necessary to achieve to accomplish defactoring.

Column Hermite defactoring is very similar to Pernet-Stein defactoring. If you compare the set of methods that they call, they are almost identical; Pernet-Stein just uses ~~an extra step for~~ matrix multiplication.

Column Hermite defactoring is very similar to Pernet-Stein defactoring. If you compare the set of methods that they call, they are almost identical; Pernet-Stein just uses matrix multiplication in exchange of column Hermite's concatenation and slice.

{| class="wikitable"

|+~~comparison~~ of ~~methods used~~ in column Hermite and Pernet-Stein defactoring

{| class="wikitable center-all"

!~~column~~ Hermite

|+Comparison of steps in column Hermite and Pernet-Stein defactoring

!Pernet-Stein

! Column Hermite

|-

! Pernet-Stein

|

~~|Dot (matrix multiplication)~~

|-

~~|First~~

~~|Last~~

|-

|~~HermiteDecomposition~~

| Concatenation

|~~HermiteDecomposition~~

|

|-

|~~Inverse~~

| Hermite normal form

|~~Inverse~~

| Hermite normal form

|-

|~~MatrixRank~~

| Slice

|~~MatrixRank~~

|

|-

|~~Take~~

| Inversion

|~~Take~~

| Inversion

|-

|~~Transpose~~

| Slice

|~~Transpose~~

| Slice

|-

|~~Transpose~~

|

|~~Transpose~~

| Matrix multiplication

|}

@@ Line 208: / Line 208: @@
 </pre>
-So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. Note that the <code>hnf</code> is only available in row-style, so we first transpose the matrix to convert it to column-style. The decomposition in Wolfram returns two items – the unimodular matrix, and the input matrix in Hermite normal form, in that order – and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we transpose it again to in effect undo the transposition we did at the beginning.
+So this implementation begins by finding the unimodular matrix from a column Hermite decomposition. Note that the <code>HermiteDecomposition[]</code> is only available in row-style, so we first transpose the matrix to convert it to column-style. The decomposition in Wolfram returns two items – the unimodular matrix, and the input matrix in Hermite normal form, in that order – and in this case we actually want the unimodular matrix. So we take that with <code>First[]</code>. Then we transpose it again to in effect undo the transposition we did at the beginning.
 The next step is to invert that matrix, which is doable because it is unimodular; a key property of unimodular matrices is that they are always invertible, and because their determinant is ±1, if they contain all integer entries, their inverse will also contain all integer entries (which it does, and we need it to)<ref>Interesting tidbit regarding [[full-rank]] matrices and unimodular matrices: for square matrices, unimodularity implies full-rank, and while full-rank does not imply unimodularity, it does imply a non-zero determinant.</ref>.
@@ Line 252: / Line 252: @@
 ===== Relationship with other defactoring methods =====
-[[File:Comparison of defactoring algorithms.png|400px|thumb|right|A comparison of defactoring methods, using the function names built in to Wolfram Language]]
+[[File:Comparison of defactoring algorithms.png|400px|thumb|right|Comparison of defactoring algorithms using Wolfram Language. Notice how HermiteDecomposition simultaneously returns the HNF and the unimodular matrix]]
-If you describe column Hermite defactoring as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite ... inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until you've achieved Smith normal form, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.
+If column Hermite defactoring is described as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite … inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until Smith normal form has been achieved, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.
-According to Wolfram<ref>See: https://reference.wolfram.com/language/ref/SmithDecomposition.html</ref>, "the Smith decomposition can often be found by two iterations of the Hermite decomposition". This notion is echoed in the Sage docs<ref>See: https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html</ref>, which read, "Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation," remembered that saturation is the same as defactoring. The reason for the multiple applications of Hermite decomposition to achieve Smith normal form is that you won't necessarily get a diagonal matrix on the first go. But as we know from Smith defactoring, the center matrix of the Smith decomposition — the Smith normal form one — is not the target matrix, so its exact form is not necessary to achieve to accomplish defactoring.
+According to Wolfram<ref>[https://reference.wolfram.com/language/ref/SmithDecomposition.html Wolfram Language Documentation | SmithDecomposition]</ref>, "the Smith decomposition can often be found by two iterations of the Hermite decomposition". This notion is echoed in the Sage docs<ref>[https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html Sage Reference Manual | Dense matrices over the integer ring]</ref>, which read, "Use Hermite normal form twice to find an invertible matrix whose inverse transforms a matrix with the same row span as self to its saturation," remembered that saturation is the same as defactoring. The reason for the multiple applications of Hermite decomposition to achieve Smith normal form is that you will not necessarily get a diagonal matrix on the first go. But as we know from Smith defactoring, the center matrix of the Smith decomposition – the Smith normal form one – is not the target matrix, so its exact form is not necessary to achieve to accomplish defactoring.
-Column Hermite defactoring is very similar to Pernet-Stein defactoring. If you compare the set of methods that they call, they are almost identical; Pernet-Stein just uses an extra step for matrix multiplication.
+Column Hermite defactoring is very similar to Pernet-Stein defactoring. If you compare the set of methods that they call, they are almost identical; Pernet-Stein just uses matrix multiplication in exchange of column Hermite's concatenation and slice.
-{| class="wikitable"
-|+comparison of methods used in column Hermite and Pernet-Stein defactoring
+{| class="wikitable center-all"
-!column Hermite
+|+Comparison of steps in column Hermite and Pernet-Stein defactoring
-!Pernet-Stein
+! Column Hermite
-|-
+! Pernet-Stein
-|
-|Dot (matrix multiplication)
-|-
-|First
-|Last
 |-
-|HermiteDecomposition
+| Concatenation
-|HermiteDecomposition
+|
 |-
-|Inverse
+| Hermite normal form
-|Inverse
+| Hermite normal form
 |-
-|MatrixRank
+| Slice
-|MatrixRank
+|
 |-
-|Take
+| Inversion
-|Take
+| Inversion
 |-
-|Transpose
+| Slice
-|Transpose
+| Slice
 |-
-|Transpose
+|
-|Transpose
+| Matrix multiplication
 |}