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).
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 MADAM defactoring.
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 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 [math]\displaystyle{ \frac{3^r - 1}{2} }[/math] sums and differences where [math]\displaystyle{ r }[/math] is the rank of the mapping. For example, for a rank-3 mapping with rows [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 {{ket|⟨17 16 -4} ⟨4 -4 1]]. The SNF of this mapping is [⟨1 0 0] ⟨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 doesn't manage to remove the common factor, but it does at least unearth it from the well-hidden state into at least the merely "hidden" state, and possibly the revealed state. For example, in the case of [⟨6 5 -4] ⟨4 -4 1]⟩, the HNF is [⟨2 9 -5] ⟨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.
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]]
];