Defactoring algorithms: Difference between revisions
Cmloegcmluin (talk | contribs) →How/why it works: add proof from Tom Price's advice |
Cmloegcmluin (talk | contribs) →New development: column Hermite defactoring: more information showing relationship between the three algorithms |
||
| Line 205: | Line 205: | ||
# Proving (c) is a bit trickier, because S⁻¹ is not necessarily an integer matrix. But can show that S⁻¹A is an integer matrix by showing that it maps lattice points to lattice points. Suppose we have that same equation from the proof of (a), namely that y = S⁻¹Ax, where x is a lattice point. We want to show that y is a lattice point. Again, since A and S have the same image (when considered as functions on lattice points), there must be some lattice point z with Sz = Ax. But we also know that Sy = Ax. Since S is invertible, and therefore injective, y = z, so y is a lattice point. | # Proving (c) is a bit trickier, because S⁻¹ is not necessarily an integer matrix. But can show that S⁻¹A is an integer matrix by showing that it maps lattice points to lattice points. Suppose we have that same equation from the proof of (a), namely that y = S⁻¹Ax, where x is a lattice point. We want to show that y is a lattice point. Again, since A and S have the same image (when considered as functions on lattice points), there must be some lattice point z with Sz = Ax. But we also know that Sy = Ax. Since S is invertible, and therefore injective, y = z, so y is a lattice point. | ||
=== | ====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]] | |||
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 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. | ||
| Line 213: | Line 213: | ||
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>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. | ||
==== Relationship with EA ==== | 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. | ||
{| class="wikitable" | |||
|+comparison of methods used in column Hermite and Pernet-Stein defactoring | |||
!column Hermite | |||
!Pernet-Stein | |||
|- | |||
| | |||
|Dot (matrix multiplication) | |||
|- | |||
|First | |||
|Last | |||
|- | |||
|HermiteDecomposition | |||
|HermiteDecomposition | |||
|- | |||
|Inverse | |||
|Inverse | |||
|- | |||
|MatrixRank | |||
|MatrixRank | |||
|- | |||
|Take | |||
|Take | |||
|- | |||
|Transpose | |||
|Transpose | |||
|- | |||
|Transpose | |||
|Transpose | |||
|} | |||
====Relationship with EA==== | |||
Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the minor determinants (or "minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply extract the GCD of the entries in this list of minors. So if defactoring a list of minor determinants means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity. | Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the minor determinants (or "minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply extract the GCD of the entries in this list of minors. So if defactoring a list of minor determinants means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity. | ||
=== By hand === | ===By hand === | ||
In an effort to demystify the effects of column Hermite defactoring, let's walk though an example manually. | In an effort to demystify the effects of column Hermite defactoring, let's walk though an example manually. | ||
First we need to learn how to perform its two building blocks by hand: | First we need to learn how to perform its two building blocks by hand: | ||
# Hermite decomposition | #Hermite decomposition | ||
# inversion | # inversion | ||
| Line 228: | Line 259: | ||
Fortunately, both of these two processes can be done using a technique you may already be familiar with if you've learned how to calculate the null-space of a mapping by hand (as demonstrated [[Douglas_Blumeyer%27s_RTT_How-To#Null-space|here]]): | Fortunately, both of these two processes can be done using a technique you may already be familiar with if you've learned how to calculate the null-space of a mapping by hand (as demonstrated [[Douglas_Blumeyer%27s_RTT_How-To#Null-space|here]]): | ||
# augmenting your matrix with an identity matrix | #augmenting your matrix with an identity matrix | ||
# performing elementary row or column operations until a desired state is achieved<ref>For convenience, here is a summary of the three different techniques and their targets:<br> | # performing elementary row or column operations until a desired state is achieved<ref>For convenience, here is a summary of the three different techniques and their targets:<br> | ||
* null-space: augment to the bottom, go until you get columns with all zeros. | *null-space: augment to the bottom, go until you get columns with all zeros. | ||
* Hermite: augment to the right, go until echelon form. | *Hermite: augment to the right, go until echelon form. | ||
* inverse: augment to the right, go until identity matrix. | *inverse: augment to the right, go until identity matrix. | ||
</ref> | </ref> | ||
==== Hermite decomposition by hand ==== | ====Hermite decomposition by hand==== | ||
Let's do a Hermite decomposition example first. We begin with the mapping for the temperament 12&26bbb, which looks like {{ket|{{map|12 19 28}} {{map|26 43 60}}}}, or as a matrix: | Let's do a Hermite decomposition example first. We begin with the mapping for the temperament 12&26bbb, which looks like {{ket|{{map|12 19 28}} {{map|26 43 60}}}}, or as a matrix: | ||
| Line 262: | Line 293: | ||
Now we begin applying elementary row operations until the part on the left is in Hermite Normal Form. If you need to review the definition of HNF and its constraints, you can find more detail [[matrix echelon forms#HNF|here]]. The quick and dirty is: | Now we begin applying elementary row operations until the part on the left is in Hermite Normal Form. If you need to review the definition of HNF and its constraints, you can find more detail [[matrix echelon forms#HNF|here]]. The quick and dirty is: | ||
# all pivots > 0 | #all pivots > 0 | ||
# all entries in pivot columns below the pivots = 0 | # all entries in pivot columns below the pivots = 0 | ||
# all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot | #all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot | ||
One special thing about computing the HNF is that we're not allowed to use all elementary operations; in particular we're not allowed to multiply (or divide) rows. Our main technique, then, will be adding or subtract rows from each other. This, of course, includes adding or subtracting ''multiples'' of rows from each other, because doing so is equivalent to performing those additions or subtractions one at a time (note that adding or subtracting ''multiples'' of rows from each other is significantly different than simply ''multiplying'' a row by itself).<ref>The fact that you're not allowed to multiply or divide is equivalent to the fact that at every step along the way, the augmented matrix remains unimodular.</ref> | One special thing about computing the HNF is that we're not allowed to use all elementary operations; in particular we're not allowed to multiply (or divide) rows. Our main technique, then, will be adding or subtract rows from each other. This, of course, includes adding or subtracting ''multiples'' of rows from each other, because doing so is equivalent to performing those additions or subtractions one at a time (note that adding or subtracting ''multiples'' of rows from each other is significantly different than simply ''multiplying'' a row by itself).<ref>The fact that you're not allowed to multiply or divide is equivalent to the fact that at every step along the way, the augmented matrix remains unimodular.</ref> | ||
| Line 330: | Line 361: | ||
And we're done! Let's confirm though. | And we're done! Let's confirm though. | ||
# '''all pivots > 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11. | #'''all pivots > 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11. | ||
# '''all entries in pivot columns below the pivots = 0'''? Check. This only applies to one entry — the bottom right one, below the 1st row's pivot — but it is indeed 0. | #'''all entries in pivot columns below the pivots = 0'''? Check. This only applies to one entry — the bottom right one, below the 1st row's pivot — but it is indeed 0. | ||
# '''all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry — the center top one, above the 2nd row's pivot of 11 — but it is 5, and 5 is indeed non-negative and < 11. | #'''all entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry — the center top one, above the 2nd row's pivot of 11 — but it is 5, and 5 is indeed non-negative and < 11. | ||
And so, we have performed the Hermite decomposition. The matrix to the left of the augmentation line — the one in place of our original matrix — is that original matrix in HNF: | And so, we have performed the Hermite decomposition. The matrix to the left of the augmentation line — the one in place of our original matrix — is that original matrix in HNF: | ||
| Line 373: | Line 404: | ||
And that's all there is to the Hermite decomposition. | And that's all there is to the Hermite decomposition. | ||
==== Inversion by hand ==== | ====Inversion by hand==== | ||
Now let's take a look at how to do inversion by hand. The first thing to note is that this process only works for rectangular matrices. So you will not be using on non-trivial mappings or comma bases directly. But, as you know, there is a useful application for this process on the unimodular matrix which is the other result of the Hermite decomposition than the HNF, and unimodular matrices are always square. | Now let's take a look at how to do inversion by hand. The first thing to note is that this process only works for rectangular matrices. So you will not be using on non-trivial mappings or comma bases directly. But, as you know, there is a useful application for this process on the unimodular matrix which is the other result of the Hermite decomposition than the HNF, and unimodular matrices are always square. | ||
| Line 489: | Line 520: | ||
I chose this matrix specifically to demonstrate the importance of the unimodularity of the other matrix produced by the Hermite decomposition. A unimodular matrix is defined by having a determinant of ±1. And what does this have to do with inverses? Well, take a look at the determinant of our original matrix here, {{ket|{{map|3 -2 4}} {{map|1 0 2}} {{map|0 1 0}}}}. It's 2. The determinant of an invertible matrix will tell you what the LCM of all the denominators in the inverse will be<ref>If you're familiar with the formula for the Moore-Penrose pseudoinverse of rectangular matrices, you may recognize this fact as akin to how you multiply the outside of the pseudoinverse by the reciprocal of the determinant of the matrix.</ref><ref>This may also shed some light on the fact that the only square matrices that are not invertible are those with determinants equal to 0.</ref> And so, the fact that the other matrix produced by the Hermite decomposition is unimodular means that not only is it invertible, if it has only integer terms (which it will, being involved in HNF), then its inverse will also have only integer terms. And this is important because the inverse of a Hermite unimodular matrix is just one step away from the defactored form of an input matrix. | I chose this matrix specifically to demonstrate the importance of the unimodularity of the other matrix produced by the Hermite decomposition. A unimodular matrix is defined by having a determinant of ±1. And what does this have to do with inverses? Well, take a look at the determinant of our original matrix here, {{ket|{{map|3 -2 4}} {{map|1 0 2}} {{map|0 1 0}}}}. It's 2. The determinant of an invertible matrix will tell you what the LCM of all the denominators in the inverse will be<ref>If you're familiar with the formula for the Moore-Penrose pseudoinverse of rectangular matrices, you may recognize this fact as akin to how you multiply the outside of the pseudoinverse by the reciprocal of the determinant of the matrix.</ref><ref>This may also shed some light on the fact that the only square matrices that are not invertible are those with determinants equal to 0.</ref> And so, the fact that the other matrix produced by the Hermite decomposition is unimodular means that not only is it invertible, if it has only integer terms (which it will, being involved in HNF), then its inverse will also have only integer terms. And this is important because the inverse of a Hermite unimodular matrix is just one step away from the defactored form of an input matrix. | ||
==== Putting it all together ==== | ====Putting it all together==== | ||
In the Wolfram Language algorithm described above, the input matrix is first transposed and then Hermite decomposed. In fact, this is due to a limitation of the built-in <code>HermiteDecomposition[]</code> function in Wolfram Language. The HNF is well understood both in its more common and default row-style as well as a column-style, so it might be expected for Wolfram Language to provide an option for the <code>HermiteDecomposition[]</code> function to perform it by columns. Alas, it does not. So the transposition our code does is a workaround for this lack. | In the Wolfram Language algorithm described above, the input matrix is first transposed and then Hermite decomposed. In fact, this is due to a limitation of the built-in <code>HermiteDecomposition[]</code> function in Wolfram Language. The HNF is well understood both in its more common and default row-style as well as a column-style, so it might be expected for Wolfram Language to provide an option for the <code>HermiteDecomposition[]</code> function to perform it by columns. Alas, it does not. So the transposition our code does is a workaround for this lack. | ||
When doing a column-style Hermite decomposition by hand, we have two options: | When doing a column-style Hermite decomposition by hand, we have two options: | ||
# Mimic this workaround that we're doing in the code: transpose the matrix, and then do a Hermite decomposition as demonstrated above: augment to the right and perform row operations; | #Mimic this workaround that we're doing in the code: transpose the matrix, and then do a Hermite decomposition as demonstrated above: augment to the right and perform row operations; | ||
# Augment the matrix to the ''bottom'', and then use elementary column operations instead of elementary row operations (such that it looks more similar to the process for computing the null-space by hand). | #Augment the matrix to the ''bottom'', and then use elementary column operations instead of elementary row operations (such that it looks more similar to the process for computing the null-space by hand). | ||
Here, we'll be demonstrating the process using the first option, because we might as well follow the same approach as the code unless we have a compelling reason not to. And we don't! If we were to follow the second option — rotating everything 90 degrees — we'd have to rewire our brains to recognize matrices in HNF but rotated 90 degrees, which is certainly harder than just transposing a matrix 90 degrees and then treating it the same way with respect to the complexities of Hermite decomposition as we've already become accustomed to. | Here, we'll be demonstrating the process using the first option, because we might as well follow the same approach as the code unless we have a compelling reason not to. And we don't! If we were to follow the second option — rotating everything 90 degrees — we'd have to rewire our brains to recognize matrices in HNF but rotated 90 degrees, which is certainly harder than just transposing a matrix 90 degrees and then treating it the same way with respect to the complexities of Hermite decomposition as we've already become accustomed to. | ||
| Line 763: | Line 794: | ||
The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref>In the doubly-enfactored case of {{ket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of 33 = 3 × 11, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref>It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with -3 of the 2nd row, i.e. 2{{map|6 5 -4}} + -3{{map|4 -4 1}} = {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{ket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{bra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: -1{{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} = {{vector|0 11}}.</ref>. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows. | The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref>In the doubly-enfactored case of {{ket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of 33 = 3 × 11, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref>It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with -3 of the 2nd row, i.e. 2{{map|6 5 -4}} + -3{{map|4 -4 1}} = {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{ket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{bra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: -1{{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} = {{vector|0 11}}.</ref>. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows. | ||
== Other defactoring methods == | |||
==Other defactoring methods== | |||
When in development on an ideal defactoring method — the effort which culminated in column Hermite defactoring — Dave and Douglas experimented on other methods, which are imperfect (don't work all the time, are very slow, or too complicated). | When in development on an ideal defactoring method — the effort which culminated in column Hermite defactoring — Dave and Douglas experimented on other methods, which are imperfect (don't work all the time, are very slow, or too complicated). | ||
=== Null-space'n'back defactoring === | ===Null-space'n'back defactoring=== | ||
It's fairly self-explanatory: '''Null-space'n'back defactoring''' is a defactoring algorithm that works by finding a basis for the null-space of a mapping, and then finding a basis for the anti-null-space of that result, which brings one back to a mapping. Unfortunately this does not work all of the time<ref>Although it is supposedly proven otherwise in this other paper by Pernet, where the terms "right kernel basis" and "left kernel basis" are used instead: https://hal.archives-ouvertes.fr/hal-01829139 This may be due to implementation details of Wolfram Language, or some other constraint that we do not yet understand. Pernet has yet to weigh in but has been contacted about this by email.</ref>. For example, {{ket|{{map|7 11 16}} {{map|22 35 51}}}} has a null-space basis of {{bra|{{vector|1 -5 3}}}}, and when we take the anti-null-space of that, we get {{ket|{{map|3 0 -1}} {{map|0 3 5}}}} which is a classic case of hidden enfactoring as described above. | It's fairly self-explanatory: '''Null-space'n'back defactoring''' is a defactoring algorithm that works by finding a basis for the null-space of a mapping, and then finding a basis for the anti-null-space of that result, which brings one back to a mapping. Unfortunately this does not work all of the time<ref>Although it is supposedly proven otherwise in this other paper by Pernet, where the terms "right kernel basis" and "left kernel basis" are used instead: https://hal.archives-ouvertes.fr/hal-01829139 This may be due to implementation details of Wolfram Language, or some other constraint that we do not yet understand. Pernet has yet to weigh in but has been contacted about this by email.</ref>. For example, {{ket|{{map|7 11 16}} {{map|22 35 51}}}} has a null-space basis of {{bra|{{vector|1 -5 3}}}}, and when we take the anti-null-space of that, we get {{ket|{{map|3 0 -1}} {{map|0 3 5}}}} which is a classic case of hidden enfactoring as described above. | ||
=== Sum-and-difference defactoring === | ===Sum-and-difference defactoring=== | ||
When in development on an ideal defactoring method — the effort which culminated in [[column Hermite defactoring]] — Dave and Douglas invested a great deal of time in a defactoring method which still has some advantages over column Hermite defactoring but was ultimately rejected. This other method is called '''"sum-and-difference" defactoring''', or '''SAD defactor''' (it is sad partially because it didn't work out). | When in development on an ideal defactoring method — the effort which culminated in [[column Hermite defactoring]] — Dave and Douglas invested a great deal of time in a defactoring method which still has some advantages over column Hermite defactoring but was ultimately rejected. This other method is called '''"sum-and-difference" defactoring''', or '''SAD defactor''' (it is sad partially because it didn't work out). | ||
| Line 781: | Line 813: | ||
SAD defactoring's key reason for rejection is that a number of edge cases were discovered that caused its algorithm to balloon in complexity, both insofar as it could be implemented in code as well as understood by humans. | SAD defactoring's key reason for rejection is that a number of edge cases were discovered that caused its algorithm to balloon in complexity, both insofar as it could be implemented in code as well as understood by humans. | ||
==== | ====How it works==== | ||
Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all <span><math>\frac{3^r - 1}{2}</math></span> sums and differences where <span><math>r</math></span> is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check | Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all <span><math>\frac{3^r - 1}{2}</math></span> sums and differences where <span><math>r</math></span> is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check | ||
* A | *A | ||
* B | *B | ||
* C | *C | ||
* A+B | *A+B | ||
* A-B | *A-B | ||
* A+C | *A+C | ||
* A-C | *A-C | ||
* B+C | *B+C | ||
* B-C | *B-C | ||
* A+B+C | *A+B+C | ||
* A+B-C | *A+B-C | ||
* A-B+C | *A-B+C | ||
* A-B-C | *A-B-C | ||
In other words, for each of A, B, and C, you have to check -1 of it, 0 of it, or 1 of it. You don't need to check any counts less than -1 or greater than 1, because then you'd of course be introducing a common factor to the mapping! | In other words, for each of A, B, and C, you have to check -1 of it, 0 of it, or 1 of it. You don't need to check any counts less than -1 or greater than 1, because then you'd of course be introducing a common factor to the mapping! | ||
| Line 803: | Line 835: | ||
Anyway, the point is, if any of these combinations has a common factor, you simply remove the common factor, then replace a row in the mapping with this combined-and-defactored row. | Anyway, the point is, if any of these combinations has a common factor, you simply remove the common factor, then replace a row in the mapping with this combined-and-defactored row. | ||
==== | ====Problem 1. edge case: multiple common factors ==== | ||
Some matrices can have multiple common factors, such as {{ket|{{map|17 16 -4} {{map|4 -4 1}}}}. The SNF of this mapping is {{ket|{{map|1 0 0}} {{map|0 33 0}}}}, and that 33 is actually a double common factor because it's not prime, but the product of 3 and 11. SAD defactoring unfortunately only removes one of these factors at a time, and so it therefore needs to be designed to perform recursively until no change occurs in an iteration, at which point all common factors have been removed. | Some matrices can have multiple common factors, such as {{ket|{{map|17 16 -4} {{map|4 -4 1}}}}. The SNF of this mapping is {{ket|{{map|1 0 0}} {{map|0 33 0}}}}, and that 33 is actually a double common factor because it's not prime, but the product of 3 and 11. SAD defactoring unfortunately only removes one of these factors at a time, and so it therefore needs to be designed to perform recursively until no change occurs in an iteration, at which point all common factors have been removed. | ||
==== | ====Problem 2. edge case: well-hidden common factors==== | ||
SAD defactoring was found to fail in the case of [[canonical_form#well-hidden_enfactoring|well-hidden common factor]]s, i.e. | SAD defactoring was found to fail in the case of [[canonical_form#well-hidden_enfactoring|well-hidden common factor]]s, i.e. | ||
| Line 816: | Line 848: | ||
So this is better than initially thought. But still not great to have to add another HNF pass at the onset. | So this is better than initially thought. But still not great to have to add another HNF pass at the onset. | ||
==== | ====Problem 3. picking the correct row to replace==== | ||
Initially it was thought that, upon finding a common factor in a combination of rows and removing it, it would be acceptable to replace any row of the mapping with the fixed row, and that we could then simply replace the first row. However this is not the case. When replacing a row with a defactored sum or difference, the replaced row has to be one of those involved in the sum or difference. It can always be the topmost one of those, but it can't always be the topmost row of the matrix. So this increases the complexity of the algorithm. | Initially it was thought that, upon finding a common factor in a combination of rows and removing it, it would be acceptable to replace any row of the mapping with the fixed row, and that we could then simply replace the first row. However this is not the case. When replacing a row with a defactored sum or difference, the replaced row has to be one of those involved in the sum or difference. It can always be the topmost one of those, but it can't always be the topmost row of the matrix. So this increases the complexity of the algorithm. | ||
==== | ====Problem 4. failure to remove rank-deficient rows==== | ||
The way Smith defactoring works, and column Hermite defactoring works, a step which ensures that the final number of rows of the output is equal to the rank is built into how the core of the implementation works already. However, for SAD defactoring, a special extra pass is required to ensure this. | The way Smith defactoring works, and column Hermite defactoring works, a step which ensures that the final number of rows of the output is equal to the rank is built into how the core of the implementation works already. However, for SAD defactoring, a special extra pass is required to ensure this. | ||
| Line 826: | Line 858: | ||
At this point, SAD defactor was considered "a mess". | At this point, SAD defactor was considered "a mess". | ||
==== Wolfram Language implementation ==== | ====Wolfram Language implementation==== | ||
This is the furthest progress that was made on SAD defactor before efforts were shifted to column Hermite defactor. This implementation still exhibits problems 2 and 3; only problems 1 and 4 were solved here. Problem 3 started to be solved, but wasn't quite quashed. | This is the furthest progress that was made on SAD defactor before efforts were shifted to column Hermite defactor. This implementation still exhibits problems 2 and 3; only problems 1 and 4 were solved here. Problem 3 started to be solved, but wasn't quite quashed. | ||
<nowiki> | <nowiki> | ||
confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced}, | confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced}, | ||
enfactoredRowReplaced = True; | |||
For[i = 1, i <= Length[m], i++, | |||
If[Apply[GCD, m[[i]]] > 1, enfactoredRowReplaced = False] | |||
]; | |||
enfactoredRowReplaced | |||
]; | ]; | ||
handleEnfactored[m_, maybeDisarmedRow_] := Module[{defactored, attemptedReplacementOfEnfactoredRow, i, enfactoredRowReplaced}, | handleEnfactored[m_, maybeDisarmedRow_] := Module[{defactored, attemptedReplacementOfEnfactoredRow, i, enfactoredRowReplaced}, | ||
For[i = 1, i <= Length[m], i++, | |||
attemptedReplacementOfEnfactoredRow = Prepend[Drop[m, {i}], First[maybeDisarmedRow]]; | |||
enfactoredRowReplaced = confirmEnfactoredRowReplaced[attemptedReplacementOfEnfactoredRow]; | |||
If[enfactoredRowReplaced, defactored = enhancedSadDefactor[attemptedReplacementOfEnfactoredRow]]; | |||
]; | |||
defactored | |||
]; | ]; | ||
enhancedSadDefactor[m_] := Module[{mNoAllZeros, reduced, linCombs, linCombsDisarmed, maybeDisarmedRow}, | enhancedSadDefactor[m_] := Module[{mNoAllZeros, reduced, linCombs, linCombsDisarmed, maybeDisarmedRow}, | ||
mNoAllZeros = removeAllZeroRows[m]; | |||
linCombs = linCombsToCheck[mNoAllZeros]; | |||
linCombsDisarmed = Map[extractGcd, linCombs]; | |||
maybeDisarmedRow = Complement[linCombsDisarmed, linCombs]; | |||
If[Length[maybeDisarmedRow] == 0, mNoAllZeros, handleEnfactored[mNoAllZeros, maybeDisarmedRow]] | |||
];</nowiki> | ];</nowiki> | ||
=== MADAM defactoring === | ===MADAM defactoring === | ||
A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] took advantage of the fact that the list of minor determinants (or simply "minors") of a mapping is guaranteed to include any common factor as its entries' GCD. So, if one simply converted a mapping to its list of minors, removed the GCD (at which point you would have what in RTT is called a [[User:Cmloegcmluin/RTT_How-To#multimaps|canonical multimap]], or [[wedgie]]), and then performed an "anti-minors" operation to get back to a mapping form, any common factors should be removed. | A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] took advantage of the fact that the list of minor determinants (or simply "minors") of a mapping is guaranteed to include any common factor as its entries' GCD. So, if one simply converted a mapping to its list of minors, removed the GCD (at which point you would have what in RTT is called a [[User:Cmloegcmluin/RTT_How-To#multimaps|canonical multimap]], or [[wedgie]]), and then performed an "anti-minors" operation to get back to a mapping form, any common factors should be removed. | ||
| Line 865: | Line 896: | ||
[[Dave Keenan]] and [[Douglas Blumeyer]] record a summary of their work here in case it may be helpful to anyone else who might want to iterate on this later. The other major failed experimental defactoring technique was [[Sum-and-difference_defactoring|SAD defactoring]]. | [[Dave Keenan]] and [[Douglas Blumeyer]] record a summary of their work here in case it may be helpful to anyone else who might want to iterate on this later. The other major failed experimental defactoring technique was [[Sum-and-difference_defactoring|SAD defactoring]]. | ||
= References = | =References= | ||
<references /> | |||