Sum-and-difference defactoring - Revision history

Cmloegcmluin: extract into centralized defactoring algorithms article

2021-11-14T18:33:30Z

extract into centralized defactoring algorithms article

← Older revision		Revision as of 18:33, 14 November 2021
Line 1:		Line 1:
	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).		#REDIRECT [[Defactoring_algorithms#Sum-and-difference_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 [[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 [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 {{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.~~
	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 {{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.~~

	~~== 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>~~

Cmloegcmluin: fix bad vector and map templates

2021-10-11T21:41:26Z

fix bad vector and map templates

← Older revision		Revision as of 21:41, 11 October 2021
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 {{~~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.		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 {{~~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.		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.

Cmloegcmluin: explanatory note

2021-10-08T02:06:31Z

explanatory note

← Older revision		Revision as of 02:06, 8 October 2021
Line 1:		Line 1:
	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).

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

Cmloegcmluin: extracting development notes type stuff

2021-10-08T02:03:17Z

extracting development notes type stuff

New page

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>