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

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 largest possible 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)

Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the ~~minor determinants~~ of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding minor (this idea is discussed in more detail in a later section of this article). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.

Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail in a later section of this article). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.

Regarding the development of a canonical form for temperaments using only linear algebra, Dave and Douglas did manage to develop such a form, which is documented here: [[defactored Hermite form]]. It was Gene himself who first described this form (as the result of his "saturation" algorithm), so he either didn't realize the full implications of his discovery, or it was simply not popularized and plugged in with the rest of the hive knowledge.</ref>.

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

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 list of the largest possible minor determinants (or "largest-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 largest-minors. So if defactoring a list of largest-minors 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 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' GCD. So, if one simply converted a mapping to its list of 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.

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 [[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 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]]".
+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 largest possible 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)
 <br><br>
-Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the minor determinants of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding minor (this idea is discussed in more detail in a later section of this article). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.
+Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail in a later section of this article). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.
 <br><br>
 Regarding the development of a canonical form for temperaments using only linear algebra, Dave and Douglas did manage to develop such a form, which is documented here: [[defactored Hermite form]]. It was Gene himself who first described this form (as the result of his "saturation" algorithm), so he either didn't realize the full implications of his discovery, or it was simply not popularized and plugged in with the rest of the hive knowledge.</ref>.
@@ 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 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.
+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 list of the largest possible minor determinants (or "largest-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 largest-minors. So if defactoring a list of largest-minors 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 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' GCD. So, if one simply converted a mapping to its list of 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.
+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 [[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.