Defactoring algorithms: Difference between revisions

Line 1:

This article discusses how to identify enfactoring and then [[defactor]] it.

A major use case for defactoring is to enable a [[canonical form]] for [[regular temperament]] [[mappings]], or in other words, to achieve a unique ID for temperaments in the form of a matrix. Previously this was only available by using lists of minor determinants AKA [[wedgie|wedge products of mapping rows]], which by virtue of reducing the information down to a single list of numbers, could be checked for enfactoring by simply checking the single row's ~~GCF~~<ref>At the time [[Dave Keenan]] and [[Douglas Blumeyer]] began their investigation into Exterior Algebra (EA), most of the math involved in RTT could be handled using only Linear Algebra (LA), a relatively basic and commonplace subject that many people get a chance to learn in high school or university along with subjects like calculus or trigonometry. But there was one crucial task which LA hadn't proven able to handle yet: providing a "fingerprint" — a unique mathematical representation — for each distinct temperament, to allow it to be recognized as the same temperament even though it might be derived in different ways, or in other words, a canonical form for them. For many years, EA had provided this service for RTT, using a structure called a "[[wedgie]]".

A major use case for defactoring is to enable a [[canonical form]] for [[regular temperament]] [[mappings]], or in other words, to achieve a unique ID for temperaments in the form of a matrix. Previously this was only available by using lists of minor determinants AKA [[wedgie|wedge products of mapping rows]], which by virtue of reducing the information down to a single list of numbers, could be checked for enfactoring by simply checking the single row's GCD<ref>At the time [[Dave Keenan]] and [[Douglas Blumeyer]] began their investigation into Exterior Algebra (EA), most of the math involved in RTT could be handled using only Linear Algebra (LA), a relatively basic and commonplace subject that many people get a chance to learn in high school or university along with subjects like calculus or trigonometry. But there was one crucial task which LA hadn't proven able to handle yet: providing a "fingerprint" — a unique mathematical representation — for each distinct temperament, to allow it to be recognized as the same temperament even though it might be derived in different ways, or in other words, a canonical form for them. For many years, EA had provided this service for RTT, using a structure called a "[[wedgie]]".

Dave and Douglas began their investigations with the hypothesis that canonicalization via wedgies was the primary reason it was important for RTT beginners to learn EA, and that if a canonical form could be developed using only LA, then EA could be reframed as an advanced topic. Gene himself, upon introducing the wedgie (which he initially called a "wedge invariant"), dismissed it as a bad idea to use for identifying temperaments: "Since this is an invariant of the temperament, it would be a good thing to use to refer to it, but for the fact that it is opaque and does not immediately tell us how to define the temperament." (see: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_1545.html#1545)

Line 62:

</math>

No column has a ~~GCF~~ > 1. And yet, if we subtract the first comma from the second, we get {{vector|11 -4 -2}} - {{vector|3 4 -4}} = {{vector|8 -8 2}}, which is clearly 2×{{vector|4 -4 2}}.

No column has a GCD > 1. And yet, if we subtract the first comma from the second, we get {{vector|11 -4 -2}} - {{vector|3 4 -4}} = {{vector|8 -8 2}}, which is clearly 2×{{vector|4 -4 2}}.

== Well-hidden enfactoring ==

Line 247:

====Relationship with EA====

Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the minor determinants (or "minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the ~~GCF~~ of the entries in this list of minors. So if defactoring a list of minor determinants means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.

Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the minor determinants (or "minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the GCD of the entries in this list of minors. So if defactoring a list of minor determinants means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.

===By hand ===

Line 342:

\end{array} \end{array} \right]</math>

We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the ~~GCF~~ of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.

We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the GCD of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.

Perhaps another helpful way of thinking about this is that multiplying the row by -1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.

Line 883:

mNoAllZeros = removeAllZeroRows[m];

linCombs = linCombsToCheck[mNoAllZeros];

linCombsDisarmed = Map[~~divideOutGcf~~, linCombs];

linCombsDisarmed = Map[divideOutGcd, linCombs];

maybeDisarmedRow = Complement[linCombsDisarmed, linCombs];

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

Line 890:

===MADAM defactoring ===

A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] 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' ~~GCF~~. So, if one simply converted a mapping to its list of minors, removed the ~~GCF~~ (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.

A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] 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.

@@ Line 1: / Line 1: @@
 This article discusses how to identify enfactoring and then [[defactor]] it.
-A major use case for defactoring is to enable a [[canonical form]] for [[regular temperament]] [[mappings]], or in other words, to achieve a unique ID for temperaments in the form of a matrix. Previously this was only available by using lists of minor determinants AKA [[wedgie|wedge products of mapping rows]], which by virtue of reducing the information down to a single list of numbers, could be checked for enfactoring by simply checking the single row's GCF<ref>At the time [[Dave Keenan]] and [[Douglas Blumeyer]] began their investigation into Exterior Algebra (EA), most of the math involved in RTT could be handled using only Linear Algebra (LA), a relatively basic and commonplace subject that many people get a chance to learn in high school or university along with subjects like calculus or trigonometry. But there was one crucial task which LA hadn't proven able to handle yet: providing a "fingerprint" — a unique mathematical representation — for each distinct temperament, to allow it to be recognized as the same temperament even though it might be derived in different ways, or in other words, a canonical form for them. For many years, EA had provided this service for RTT, using a structure called a "[[wedgie]]".
+A major use case for defactoring is to enable a [[canonical form]] for [[regular temperament]] [[mappings]], or in other words, to achieve a unique ID for temperaments in the form of a matrix. Previously this was only available by using lists of minor determinants AKA [[wedgie|wedge products of mapping rows]], which by virtue of reducing the information down to a single list of numbers, could be checked for enfactoring by simply checking the single row's GCD<ref>At the time [[Dave Keenan]] and [[Douglas Blumeyer]] began their investigation into Exterior Algebra (EA), most of the math involved in RTT could be handled using only Linear Algebra (LA), a relatively basic and commonplace subject that many people get a chance to learn in high school or university along with subjects like calculus or trigonometry. But there was one crucial task which LA hadn't proven able to handle yet: providing a "fingerprint" — a unique mathematical representation — for each distinct temperament, to allow it to be recognized as the same temperament even though it might be derived in different ways, or in other words, a canonical form for them. For many years, EA had provided this service for RTT, using a structure called a "[[wedgie]]".
 <br><br>
 Dave and Douglas began their investigations with the hypothesis that canonicalization via wedgies was the primary reason it was important for RTT beginners to learn EA, and that if a canonical form could be developed using only LA, then EA could be reframed as an advanced topic. Gene himself, upon introducing the wedgie (which he initially called a "wedge invariant"), dismissed it as a bad idea to use for identifying temperaments: "Since this is an invariant of the temperament, it would be a good thing to use to refer to it, but for the fact that it is opaque and does not immediately tell us how to define the temperament." (see: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_1545.html#1545)
@@ Line 62: / Line 62: @@
 </math>
-No column has a GCF > 1. And yet, if we subtract the first comma from the second, we get {{vector|11 -4 -2}} - {{vector|3 4 -4}} = {{vector|8 -8 2}}, which is clearly 2×{{vector|4 -4 2}}.
+No column has a GCD > 1. And yet, if we subtract the first comma from the second, we get {{vector|11 -4 -2}} - {{vector|3 4 -4}} = {{vector|8 -8 2}}, which is clearly 2×{{vector|4 -4 2}}.
 == Well-hidden enfactoring ==
@@ Line 247: / Line 247: @@
 ====Relationship with EA====
-Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the minor determinants (or "minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the GCF of the entries in this list of minors. So if defactoring a list of minor determinants means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.
+Another thought that might help congeal the notion of column Hermite defactoring for you is to use what you know about multimaps (AKA "wedgies"), in particular a) what they are, and b) how to defactor them. The answer to a) is that they are just the minor determinants (or "minors" for short) of rectangular matrices, or in other words, the closest thing rectangular matrices such as mappings have to a real determinant. And the answer to b) is that you simply divide out the GCD of the entries in this list of minors. So if defactoring a list of minor determinants means dividing common factors out, then it should be little surprise that achieving a real determinant of ±1 is equivalent to defactoring, and thereby that leveraging the unimodularity of the other matrix produced by the Hermite decomposition should be valuable in this capacity.
 ===By hand ===
@@ Line 342: / Line 342: @@
 \end{array} \end{array} \right]</math>
-We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the GCF of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.
+We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the GCD of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.
 Perhaps another helpful way of thinking about this is that multiplying the row by -1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.
@@ Line 883: / Line 883: @@
     mNoAllZeros = removeAllZeroRows[m];
     linCombs = linCombsToCheck[mNoAllZeros];
-    linCombsDisarmed = Map[divideOutGcf, linCombs];
+    linCombsDisarmed = Map[divideOutGcd, linCombs];
     maybeDisarmedRow = Complement[linCombsDisarmed, linCombs];
     If[Length[maybeDisarmedRow] == 0, mNoAllZeros, handleEnfactored[mNoAllZeros, maybeDisarmedRow]]
@@ Line 890: / Line 890: @@
 ===MADAM defactoring ===
-A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] 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' GCF. So, if one simply converted a mapping to its list of minors, removed the GCF (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.
+A failed defactoring technique which was experimented with during the development of [[column Hermite defactoring]] 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.