Xenharmonic Wiki

Defactoring: Difference between revisions

← Older editNewer edit →
VisualWikitext
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,160 edits
→other details to report: preserving trailing zeros (not trim/fit/so-called "dimensionality deficiency" which I'm banning from my thoughts)
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,160 edits
→other details to report: extract the "development notes" typo info
Line 950: Line 950:


The reason these additional zeros should be preserved and these temperaments be treated as different from their untrimmed counterparts is made clear when we consider the difference in the duals. For a comma-basis, the extra dimension implies the presence of extra generators that are unbound to the other generators. For example, a basis for the anti-null-space of {{map|{{vector|4 -4 1}}}}, or in other words its mapping, as we know well is {{vector|{{map|1 0 -4}} {{map|0 1 4}}}}. But that is not a basis for the anti-null-space of {{map|{{vector|4 -4 1 <span><math>\color{red}0</math></span>}}}}; the mapping for that comma-basis would have to be {{vector|{{map|1 0 -4 <span><math>\color{red}0</math></span>}} {{map|0 1 4 <span><math>\color{red}0</math></span>}} {{map|<span><math>\color{red}0</math></span> <span><math>\color{red}0</math></span> <span><math>\color{red}0</math></span> <span><math>\color{red}1</math></span>}}}}.
The reason these additional zeros should be preserved and these temperaments be treated as different from their untrimmed counterparts is made clear when we consider the difference in the duals. For a comma-basis, the extra dimension implies the presence of extra generators that are unbound to the other generators. For example, a basis for the anti-null-space of {{map|{{vector|4 -4 1}}}}, or in other words its mapping, as we know well is {{vector|{{map|1 0 -4}} {{map|0 1 4}}}}. But that is not a basis for the anti-null-space of {{map|{{vector|4 -4 1 <span><math>\color{red}0</math></span>}}}}; the mapping for that comma-basis would have to be {{vector|{{map|1 0 -4 <span><math>\color{red}0</math></span>}} {{map|0 1 4 <span><math>\color{red}0</math></span>}} {{map|<span><math>\color{red}0</math></span> <span><math>\color{red}0</math></span> <span><math>\color{red}0</math></span> <span><math>\color{red}1</math></span>}}}}.
= other details to report =
The rest of the material in this article is not strictly necessary to understand canonical form and defactoring, but for posterity the work Dave and Douglas did to attain their insights has been summarized here in case it may be helpful to anyone else who might want to iterate on this later.
== relationship between various matrix echelon forms ==
There are several well-known echelon forms for matrices that predate DCF. Let's review them and their properties.
=== REF ===
The most general form, with the fewest constraints, is simply called '''[https://en.wikipedia.org/wiki/Row_echelon_form Row Echelon Form]''', or '''REF'''. Its only constraint is ''echelon<ref>The name "echelon" is a French word for a military troop formation with a similar triangular shape: https://en.wikipedia.org/wiki/Echelon_formation.</ref> form'': each row's pivot, or first nonzero entry, is strictly to the right of the preceding row's pivot. This single constraint is fairly weak, and therefore REF does not produce a unique representation. This constraint is shared by every matrix form discussed here.<ref>Note that the definition of REF is inconsistent and sometimes it includes some of the constraints of RREF, discussed further below. See: https://www.statisticshowto.com/matrices-and-matrix-algebra/reduced-row-echelon-form-2/</ref><ref>REF also requires that all rows that are entirely zeros should appear at the bottom of the matrix. However this rule is only relevant for rank-deficient matrices. We'll be assuming all matrices here are full-rank, so we don't have to worry about this.</ref>
In the below example, <span><math>x_{ij}</math></span> represents any number.
{| class="wikitable" style="text-align: center;"
|+REF
|style="width: 25px; background-color: #6d9eeb;"|x₁₁
|style="width: 25px; background-color: #6d9eeb;"|x₁₂
|style="width: 25px; background-color: #6d9eeb;"|x₁₃
|style="width: 25px; background-color: #6d9eeb;"|x₁₄
|style="width: 25px; background-color: #6d9eeb;"|x₁₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #6d9eeb;"|x₂₂
|style="width: 25px; background-color: #6d9eeb;"|x₂₃
|style="width: 25px; background-color: #6d9eeb;"|x₂₄
|style="width: 25px; background-color: #6d9eeb;"|x₂₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #6d9eeb;"|x₃₄
|style="width: 25px; background-color: #6d9eeb;"|x₃₅
|}
=== IREF ===
'''[https://people.sc.fsu.edu/~jburkardt/f_src/row_echelon_integer/row_echelon_integer.html Integer Row Echelon Form]''', or '''IREF''', is, unsurprisingly, any REF which meets an additional ''integer'' constraint, or in other words, that all of its entries are integers. This is still not a sufficiently strict set of constraints to ensure a unique representation.
In the below example, <span><math>n_{ij}</math></span> represents any number.
{| class="wikitable" style="text-align: center;"
|+IREF
|style="width: 25px; background-color: #93c47d;"|n₁₁
|style="width: 25px; background-color: #93c47d;"|n₁₂
|style="width: 25px; background-color: #93c47d;"|n₁₃
|style="width: 25px; background-color: #93c47d;"|n₁₄
|style="width: 25px; background-color: #93c47d;"|n₁₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₂₂
|style="width: 25px; background-color: #93c47d;"|n₂₃
|style="width: 25px; background-color: #93c47d;"|n₂₄
|style="width: 25px; background-color: #93c47d;"|n₂₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₃₄
|style="width: 25px; background-color: #93c47d;"|n₃₅
|}
=== RREF ===
'''[https://en.wikipedia.org/wiki/Row_echelon_form#Reduced_row_echelon_form Reduced Row Echelon Form]''', or '''RREF''', takes REF in a different direction than IREF. Instead of stipulating anything about integers, it requires that the matrix is ''reduced'', i.e. that the pivots are exactly equal to 1. This may require dividing rows by a number such that some resulting entries are no longer integers. Actually, there's a second part to the "reduced" constraint: each pivot column (a column which contains any row's pivot) has zeros for all other entries besides the pivot it contains. Due to these strict constraints, the RREF of a matrix is the first one we've looked at so far here which does ensure uniqueness.
{| class="wikitable" style="text-align: center;"
|+RREF
|style="width: 25px; background-color: #d9ead3;"|1
|style="width: 25px; background-color: #93c47d;"|0
|style="width: 25px; background-color: #6d9eeb;"|x₁₃
|style="width: 25px; background-color: #93c47d;"|0
|style="width: 25px; background-color: #6d9eeb;"|x₁₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #d9ead3;"|1
|style="width: 25px; background-color: #6d9eeb;"|x₂₃
|style="width: 25px; background-color: #93c47d;"|0
|style="width: 25px; background-color: #6d9eeb;"|x₂₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #d9ead3;"|1
|style="width: 25px; background-color: #6d9eeb;"|x₃₅
|}
So IREF and RREF make a [https://en.wikipedia.org/wiki/Venn_diagram Venn diagram] inside the category of REF: some IREF are RREF, but there are some RREF that are not IREF and some IREF that are not RREF. When we scope the situation to a specific matrix, however, because RREF is a unique form, this means that one or the other sector of the Venn diagram for RREF will be empty; either the unique RREF will also be IREF (and therefore the RREF-but-not-IREF sector will be empty), or it will not be IREF (and vice versa).
=== IRREF ===
'''[[Normal_lists|Integer Reduced Row Echelon Form]]''', or '''IRREF''': based on the name, one might expect this form to be a combination of the constraints for RREF and IREF, and therefore if represented in an [https://en.wikipedia.org/wiki/Euler_diagram Euler diagram] (generalization of Venn diagram) would only exist within their intersection. However this is not the case. That's because the IRREF does not include the key constraint of RREF which is that all of the pivots must be 1. IRREF is produced by simply taking the unique RREF and multiplying each row by whatever minimum value is necessary to make all of the entries integers<ref>Alternatively, IRREF can be computed by finding the null-space of a mapping, or in other words, the corresponding comma-basis for the temperament represented by the mapping, and then in turn taking the null-space of the comma-basis to get back to an equivalent mapping. The relationship between the process for finding the IRREF from the RREF and this process is not proven, but thousands of automated tests run as an experiment strongly suggest that these two techniques are equivalent.<br>
<span style="font-family: monospace; font-size: 10px;"><br>
rref[m_] := RowReduce[m]<br>
multByLcd[row_] := Apply[LCM,Denominator[row]]*row<br>
irref[m_] := Map[multByLcd,rref[m]]<br>
<br>
nullSpaceAndBack[m_]:=Reverse[NullSpace[Reverse[NullSpace[m],2]],2]<br>
<br>
<br>
output = "";<br>
Do[<br>
    d = RandomInteger[{2,6}];<br>
    r = RandomInteger[{1,d-1}];<br>
    m = RandomInteger[{-99,99},{r,d}];<br>
<br>
    n = nullSpaceAndBack[m];<br>
    i = irref[m];<br>
<br>
    If[n!=i,output = output <> "bad" <> n <> i, output = output <> "ok "],<br>
    10000<br>
]<br>
<br>
Print[output] <br>
<br></span><br>
There is a difference in that IRREF does not remove rows of zeros in the end for rank-deficient mappings, while this "null-space'n'back" does, but for most normal cases, they're the same.
</ref>. Of course, this sometimes results in the pivots no longer being 1, so sometimes it is no longer RREF. It is always still REF, though<ref>Also, it will always still satisfy the second aspect of reduced, i.e. that all other entries in pivot columns besides the pivots are zeroes.</ref>, and because it is also always integer, that makes it always IREF; therefore, IRREF is strictly a subcategory of IREF. And because the RREF is unique, and the conversion process does not alter that, the IRREF is also unique. 
{| class="wikitable" style="text-align: center;"
|+IRREF
|style="width: 25px; background-color: #93c47d;"|n₁₁
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₁₃
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₁₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₂₂
|style="width: 25px; background-color: #93c47d;"|n₂₃
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₂₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #93c47d;"|n₃₄
|style="width: 25px; background-color: #93c47d;"|n₃₅
|}
The multiplication of rows by whatever integer is required to clear the denominators of the RREF form is the action which is responsible for causing enfactoring, whenever the IRREF produces an enfactored mapping from a defactored one.
It is not possible for an RREF to be IREF without also being IRREF.
=== HNF ===
'''[https://en.wikipedia.org/wiki/Hermite_normal_form Hermite Normal Form]''', or '''HNF''': this one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced (as discussed above; [[canonical_form#RREF|link here]]); instead, it is ''normalized'', which — similarly to reduced — is a two-part constraint. Where reduced requires that all pivots be exactly equal to 1, normalized requires only that all pivots be positive (positive integers, of course, due to the other integer constraint). And where reduced requires that all entries in pivot columns besides the pivots are exactly equal to 0, normalized requires only that all entries in pivot columns below the pivots are exactly equal to 0, while entries in pivot columns above the pivots only have to be strictly less than the pivot in the respective column (while still being non-negative).<ref>The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref>There is also a rarely mentioned Hermite Canonical Form, or HCF, described here: http://home.iitk.ac.in/~rksr/html/03CANONICALFACTORIZATIONS.htm, which sort of combines the HNF's normalization constraint and the RREF's reduced constraint (all pivots equal 1, all other entries in pivot columns are 0, both above and below the pivot), but we didn't find it useful because due to its constraint that all pivots be 1, it does not preserve periods that are genuinely unit fractions of an octave (at first glance, when a pivot is not equal to 1, it might trigger you to think that the mapping is enfactored. But temperaments can legitimately have generators that divide primes evenly, such as 5-limit Blackwood, {{vector|{{map|5 8 0}} {{map|0 0 1}}}}, which divides the octave into 5 parts. So any form that enforces pivots all be 1's, such as HCF and RREF, would fail this criteria.) It also doesn't qualify as an echelon form, which becomes apparent only when you use it on rank-deficient matrices, because it doesn't require the rows of all zeros to be at the bottom; instead it (bizarrely, though maybe it's related to how the SNF requires all pivots exactly along the main diagonal) requires the rows to be sorted so that all the pivots fall on the main diagonal.</ref><ref>We are using "row-style" Hermite Normal Form here, not "column-style"; the latter would involve simply flipping everything 90 degrees so that the echelon requirement was that pivots be strictly ''below'' the pivots in the previous ''column'', and that pivot ''rows'' are considered for the normalization constraint rather than pivot ''columns''.</ref> In other words, elements above the pivot have to be reduced modulo the pivot. The normalization HNF uses is cool because this constraint, while strictly less strict than the reduced constraint used by RREF, is still strict enough to ensure uniqueness, but loose enough to ensure the integer constraint can be simultaneously satisfied, where RREF cannot ensure that.
So HNF has a lot in common with IRREF, which is the IREF you find by converting the RREF, but it is not always the same as IRREF.
Canonical form is closely related to HNF, because the second step of finding the DCF is taking the HNF. So the DCF is always ''a'' HNF, and therefore it has all the same properties of being echelon, integer, and normalized, and in turn therefore it also provides a unique representation. However it is not necessary ''the'' same HNF of the original mapping, due to the first step being defactoring; it is the same as as HNF except when the original mapping is enfactored.
In the below example, <span><math>p_{ij}</math></span> represents any positive integer, and <span><math>a_{ij}</math></span> represents any nonnegative integer less than the <span><math>p</math></span> in its column.
{| class="wikitable" style="text-align: center;"
|+HNF (and DFC)
|style="width: 25px; background-color: #e69138;"|p₁₁
|style="width: 25px; background-color: #ffe599;"|a₁₂
|style="width: 25px; background-color: #93c47d;"|n₁₃
|style="width: 25px; background-color: #ffe599;"|a₁₄
|style="width: 25px; background-color: #93c47d;"|n₁₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #e69138;"|p₂₂
|style="width: 25px; background-color: #93c47d;"|n₂₃
|style="width: 25px; background-color: #ffe599;"|a₂₄
|style="width: 25px; background-color: #93c47d;"|n₂₅
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #e69138;"|p₃₄
|style="width: 25px; background-color: #93c47d;"|n₃₅
|}
=== SNF ===
There is also the '''[https://en.wikipedia.org/wiki/Smith_normal_form Smith Normal Form]''', or '''SNF''', but we won't be discussing it in this context, because putting a mapping into SNF obliterates a lot of meaningful RTT information. SNF is also echelon, and integer, so like HNF it is also always IREF. But SNF requires that every single entry other than the pivots are zero, and that the pivots all fall exactly along the main diagonal of the matrix. The SNF essentially reduces a matrix down to the information of what its rank is and whether it is enfactored. For example, all 5-limit rank-2 temperaments such as meantone, porcupine, mavila, hanson, etc. have the same SNF: {{vector|{{map|1 0 0}} {{map|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{vector|{{map|1 0 0}} {{map|0 2 0}}}}. So while the SNF is closely related to defactoring, it is not itself a useful form to put mappings into.<ref>Here is a useful resource for computing the Smith Normal Form manually, if you are interested: https://math.stackexchange.com/questions/133076/computing-the-smith-normal-form The fact that it involves calculating so many GCDs is unsurprising given its ability to defactor matrices.</ref>
{| class="wikitable" style="text-align: center;"
|+SNF
|style="width: 25px; background-color: #e69138;"|p₁₁
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #e69138;"|p₂₂
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|-
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #e69138;"|p₃₃
|style="width: 25px; background-color: #274e13;"|0
|style="width: 25px; background-color: #274e13;"|0
|}
== cases temperaments can be regarding which of their mapping forms equal each other ==
[[File:Cases for temperament mapping forms3.png|300px|thumb|right]]
Considering only full-rank, integer mappings, we find three cases for a given temperament which is not enfactored. In all three cases, HNF is the same as DCF:
# The RREF, IRREF, and HNF are all ''different''. Example: [[Porcupine_family#Porcupine|porcupine]] with RREF of {{vector|{{map|1 0 <span><math>-\frac13</math></span>}} {{map|0 1 <span><math>\frac53</math></span>}}}}, IRREF of {{vector|{{map|3 0 -1}} {{map|0 3 5}}}}, and HNF of {{vector|{{map|1 2 3}} {{map|0 3 5}}}}.
# The RREF, IRREF, HNF are all ''the same''. Example: [[Meantone_family#Meantone_.2812.2619.2C_2.3.5.29|meantone]] with all equal to {{vector|{{map|1 0 -4}} {{map|0 1 4}}}}. This case is quite rare.
# The IRREF and HNF are the same, but the ''RREF is different''. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{vector|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{vector|{{map|1 0 1}} {{map|0 1 <span><math>\frac56</math></span>}}}}.
And there are three corresponding cases when a temperament is enfactored. In all three cases, the key difference is that HNF is no longer the same as DCF, with the only difference being that the common factor is not removed. In all cases below, the examples are shown with a common factor of 2 introduced in their second row, which stays behind in the second row of the HNF:
# Now ''all four'' are different. Example: enfactored porcupine, e.g. {{vector|{{map|15 24 35}} {{map|14 22 32}}}} causes the HNF to be {{vector|{{map|1 2 3}} {{map|0 6 10}}}}.
# Everything is still the same now, ''except HNF''. Example: enfactored meantone, e.g. {{vector|{{map|5 8 12}} {{map|14 22 32}}}} causes the HNF to be {{vector|{{map|1 0 -4}} {{map|0 2 8}}}}. This case, like the corresponding defactored state, is also quite rare.
# The ''only match'' now is between IRREF and DCF. In other words, the HNF and DCF diverged, and it was the DCF which remained the same as IRREF. Example: enfactored hanson, e.g. {{vector|{{map|15 24 35}} {{map|38 60 88}}}} causes the HNF to be {{vector|{{map|1 0 1}} {{map|0 12 10}}}}.
There is also a final case which is incredibly rare. It can be compared to the #3 cases above, the ones using hanson as their example. The idea here is that when the HNF and DCF diverge, instead of DCF remaining the same as IRREF, it's the HNF that remains the same as IRREF. There may be no practical temperoids with this case, but {{vector|{{map|165 264 393}} {{map|231 363 524}}}} will do it<ref>AKA 165b⁴c¹⁹&231b⁶c²⁴, which tempers out the 7.753¢ comma {{vector|-131 131 -33}}!</ref>, with IRREF and HNF of {{vector|{{map|33 0 -131}} {{map|0 33 131}}}}, DCF of {{vector|{{map|1 1 0}} {{map|0 33 131}}}}, and RREF of {{vector|{{map|1 0 <span><math>\frac{-131}{33}</math></span>}} {{map|0 1 <span><math>\frac{131}{33}</math></span>}}}}.
That accounts for 7 of the 15 total possible cases for a system of equalities between 4 entities. The remaining 9 cases are impossible due to properties of the domain:
* If HNF equals RREF, then the pivots of HNF are all 1's, which means the temperament is not enfactored, which means HNF also equals DCF. This eliminates 3 cases: HNF=RREF; HNF=RREF,HNF=IRREF,RREF=IRREF; HNF=RREF,IRREF=DCF.
* If RREF equals DCF, then RREF must be integer, which means RREF must also equal IRREF. This eliminates 3 cases: RREF=DCF; RREF=DCF,HNF=RREF,HNF=DCF; RREF=DCF,HNF=IRREF.
* The case where the only equality is between RREF and IRREF would only be possible when the temperament is both enfactored and rank-deficient, such as {{vector|{{map|0 0 0}} {{map|2 4 6}}}} which gives to HNF, RREF, IRREF, and DCF of {{vector|{{map|2 4 6}} {{map|0 0 0}}}}, {{vector|{{map|1 2 3}} {{map|0 0 0}}}}, {{vector|{{map|1 2 3}} {{map|0 0 0}}}}, and {{vector|{{map|1 2 3}}}}, respectively.
* The case where the only equalities are between RREF and IRREF and between HNF and DCF is impossible, because if RREF=IRREF that suggests that all entries are multiples of their pivots, which is easy if the temperament is enfactored, but if HNF=DCF then it is not.
== SAD (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).
SAD defactoring's key advantage over column Hermite defactoring is that its mechanism for removing common factors is more straightforward to see and understand, as we will see in the next section.
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
* A
* B
* C
* A+B
* A-B
* A+C
* A-C
* B+C
* 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!
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 {{vector|{{map|17 16 -4} {{map|4 -4 1}}}}. The SNF of this mapping is {{vector|{{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.
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 {{vector|{{map|6 5 -4}} {{map|4 -4 1}}}}, the HNF is {{vector|{{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.
=== 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.
=== 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.
At this point, SAD defactor was considered "a mess".
=== 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.
<nowiki>
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},
  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},
  mNoAllZeros = removeAllZeroRows[m];
  linCombs = linCombsToCheck[mNoAllZeros];
  linCombsDisarmed = Map[extractGcd, linCombs];
  maybeDisarmedRow = Complement[linCombsDisarmed, linCombs];
  If[Length[maybeDisarmedRow] == 0, mNoAllZeros, handleEnfactored[mNoAllZeros, maybeDisarmedRow]]
];</nowiki>
== MADAM (minors and divide-out-GCD, anti- minors) defactoring ==
Another technique which was experimented with 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.
Inspired by Gene Ward Smith's method for computing anti-minors as described [[Mathematical_theory_of_regular_temperaments#Wedgies|here]] and [[Basic_abstract_temperament_translation_code|here]], an anti-minors method was implemented in Wolfram Language. It was found that a defactoring algorithm based on '''M'''inors '''A'''nd '''D'''ivide-out-GCG, '''A'''nti-'''M'''inors, or '''MADAM defactoring''', does indeed work. However, it runs 10 to 20 times slower than Smith defactoring and column Hermite defactoring, and it is not compellingly easier to understand than either of them, so it is not considered to be of significant interest.


= references =
= references =
Retrieved from "https://en.xen.wiki/w/Defactoring"