Defactoring algorithms: Difference between revisions

Some matrices can have multiple common factors, such as {{rket| {{map| 17 16 -4}} {{map| 4 -4 1 }} }}. The SNF of this mapping is {{rket| {{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.

SAD defactoring was found to fail in the case of well-hidden common factors, 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 "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 does not manage to remove the common factor, but it does at least unearth it from the well-hidden state into at least a less hidden state, and possibly a revealed state. For example, in the case of {{rket| {{map| 6 5 -4 }} {{map| 4 -4 1 }} }}, the HNF is {{rket| {{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.  

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 cannot always be the topmost row of the matrix. So this increases the complexity of the algorithm.

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 was not quite quashed.

<pre>

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[divideOutGcd, linCombs];

  maybeDisarmedRow = Complement[linCombsDisarmed, linCombs];

  If[Length[maybeDisarmedRow] == 0, mNoAllZeros, handleEnfactored[mNoAllZeros, maybeDisarmedRow]]

];</pre>

A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] took advantage of the fact that the list of largest-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 largest-minors, removed the GCD (at which point you would have a [[Douglas Blumeyer and Dave Keenan%27s Intro to exterior algebra for RTT #Canonical form|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 in [[Mathematical theory of regular temperaments #Wedgies]] and in [[Basic abstract temperament translation code]], an anti-minors method was implemented in Wolfram Language. It was found that a defactoring algorithm based on <u>M</u>inors <u>A</u>nd <u>D</u>ivide-out-GCD, <u>A</u>nti-<u>M</u>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.

[[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]].

This defactoring technique is used specifically in the process of preparing matrices for [[temperament addition]]; it defactors while managing to change only a single row of the original matrix, a necessary constraint of that problem. But this method is not computationally efficient or easier to understand, so unless you have this specific need, it is not your best option. Details can be found in [[Temperament addition #3. Addabiliziation defactoring]].