Sum-and-difference defactoring: Difference between revisions
Cmloegcmluin (talk | contribs) m explanatory note |
Cmloegcmluin (talk | contribs) fix bad vector and map templates |
||
| Line 31: | Line 31: | ||
== problem 1. edge case: multiple common factors == | == problem 1. edge case: multiple common factors == | ||
Some matrices can have multiple common factors, such as {{ | 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 == | == problem 2. edge case: well-hidden common factors == | ||
| Line 38: | Line 38: | ||
ones where there are no common factors to be found in sums or differences of the rows, but are to be found in sums or differences of ''multiples of'' these rows (what is described above as [[Canonical_form#well-hidden_enfactoring|"well-hidden" enfactoring]]). In order to solve this problem, SAD defactoring would need to be reworked to check every possible combination of integer multiples of each row, potentially up to the largest absolute value of integer in the given mapping, which would cause it to become intractably slow to compute. | ones where there are no common factors to be found in sums or differences of the rows, but are to be found in sums or differences of ''multiples of'' these rows (what is described above as [[Canonical_form#well-hidden_enfactoring|"well-hidden" enfactoring]]). In order to solve this problem, SAD defactoring would need to be reworked to check every possible combination of integer multiples of each row, potentially up to the largest absolute value of integer in the given mapping, which would cause it to become intractably slow to compute. | ||
Fortunately this did not turn out to be necessary. The solution here was to do one pass of HNF before doing the defactoring (and still do the HNF pass at the end too, when going for a canonical form). This pre-pass of HNF doesn't manage to remove the common factor, but it does at least unearth it from the well-hidden state into at least the [[Canonical_form#hidden_enfactoring|merely "hidden" state]], and possibly the [[Canonical_form#immediately_apparent_enfactoring|revealed state]]. For example, in the case of {{ | Fortunately this did not turn out to be necessary. The solution here was to do one pass of HNF before doing the defactoring (and still do the HNF pass at the end too, when going for a canonical form). This pre-pass of HNF doesn't manage to remove the common factor, but it does at least unearth it from the well-hidden state into at least the [[Canonical_form#hidden_enfactoring|merely "hidden" state]], and possibly the [[Canonical_form#immediately_apparent_enfactoring|revealed state]]. For example, in the case of {{ket|{{map|6 5 -4}} {{map|4 -4 1}}}}, the HNF is {{ket|{{map|2 9 -5}} {{map|0 22 -11}}}}, so that hidden common factor of 11 has now been completely revealed to humans, but more importantly put in a form where SAD defactoring is capable of removing it. | ||
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. | ||