Defactoring algorithms: Difference between revisions

Line 81:

= Defactoring methods =

Even better than identifying enfactored mappings is actually full-on defactoring them. Here are two methods that do just that: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [https://en.wikipedia.org/wiki/Henry_John_Stephen_Smith Henry John Stephen Smith], for whom the Smith normal form is named, which this method uses</ref>, and column Hermite defactoring, developed by Dave and Douglas (the name comes, of course, from Hermite normal form, which it uses<ref>named for Charles Hermite, who was French, by the way, and so his name is pronounced more like err-MEET, not like HER-might</ref>).

Even better than identifying enfactored mappings is actually full-on defactoring them. Here are two methods that do just that: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [https://en.wikipedia.org/wiki/Henry_John_Stephen_Smith Henry John Stephen Smith], for whom the [[Smith normal form]] is named, which this method uses</ref>; Pernet-Stein defactoring, described by Clément Pernet and William Stein; and column Hermite defactoring, developed by Dave and Douglas (the name comes, of course, from Hermite normal form, which it uses<ref>named for Charles Hermite, who was French, by the way, and so his name is pronounced more like err-MEET, not like HER-might</ref>).

~~Neither of these methods have~~ been ~~rigorously~~ proven to always defactor mappings, ~~but tests~~ Douglas ran on thousands of random mappings strongly ~~suggested~~ that ~~both~~ methods work and give the exact same results as each other.

Smith defactoring has not yet been mathematically proven to always defactor mappings, while Pernet-Stein and column Hermite defactoring have been proven. Tests Douglas ran on thousands of random mappings, however, strongly suggest that all three methods work all of the time. Pernet-Stein and column Hermite are more closely related, and so they give the exact same results as each other every time, whereas Smith defactoring sometimes gives different results; however, after taking the HNF of the results, all three do become exactly the same.

~~This article prefers column~~ Hermite defactoring ~~to Smith~~ defactoring because it is:

Column Hermite defactoring is arguably the best defactoring algorithm because it is:

* ~~Cheaper~~ computationally, wasting less resources computing things irrelevant to the result<ref>

* Cheapest computationally, wasting less resources computing things irrelevant to the result<ref>

Using the following code in Wolfram Language:

hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]]

Line 104:

AbsoluteTiming[Do[smithDefactor[m],{m,ms}]]

The first several results for Smith defactoring took (in ms) 3.55919, 3.45199, 3.58493, 3.63464, 3.80917, 3.77151, while the first several results for column Hermite defactoring took 3.30063, 3.39137, 3.33808, 3.21195, 3.16469, 3.20419. So this suggests a slight edge for column Hermite defactoring.

The first several results for Smith defactoring took (in ms) 3.55919, 3.45199, 3.58493, 3.63464, 3.80917, 3.77151, while the first several results for column Hermite defactoring took 3.30063, 3.39137, 3.33808, 3.21195, 3.16469, 3.20419. So this suggests a slight edge for column Hermite defactoring. Later, Pernet-Stein was also timed, and gave very slightly slower results than column Hermite defactoring, which makes sense because it is almost identical conceptually, except requires an additional matrix multiplication step.

</ref>,

* Is easy to understand how it works, and can be worked out by hand (as we will demonstrate below),

* easy to understand how it works, and can be worked out by hand (as we will demonstrate below),

* ~~If interested, you can see~~ what the common factor is, if there was any.

* possible to find what the common factor is, if there was any.

Column Hermite defactoring could not have been developed, however, were it not for Gene's pioneering work with the Smith defactoring (what he calls the process of "saturating" a mapping). At first Dave and Douglas had no idea what the right reducing matrix of the Smith decomposition (the process which also provides the Smith normal form) had to do with common factors, only that it somehow magically worked. So they analyzed the Smith decomposition until they isolated its key actions which actually effect the defactoring, and then honed their method down to do only these necessary actions. Again, they wouldn't have known where to start were it not for Gene.

Line 145:

And that result matches what Gene finds in that xen wiki article. Defactoring and normalizing is equivalent to canonicalization.

== Precedent: Pernet-Smith defactoring ==

This algorithm was described in the 2009 paper "Fast computation of HNF of random integer matrices"<ref>https://www.wstein.org/papers/hnf/pernet-stein-fast_computation_of_hnf_of_random_integer_matrices.pdf</ref> by Clément Pernet and William Stein. At the time Dave and Douglas wrote the first draft of this article and developed column Hermite defactoring, they were unaware of this algorithm. After publicizing column Hermite defactoring, they were referred by [[Graham Breed]] to a similar method in [http://x31eq.com/temper/ Graham's popular online regular temperament tool], implemented as <code>saturate</code><ref>https://bitbucket.org/x31eq/regular/src/9bc9b5bd8c8e0ced6223b29c3ea487719d120c43/kernel.py#lines-178</ref> which includes in its commented documentation a link to the aforementioned paper. Unable to reverse-engineer Gene Ward Smith's saturation algorithm, Graham had gone back to the same source Gene had supposedly gotten his inspiration from — the Sage software developed by William Stein, co-author of this paper — and came across this paper. Graham's implementation turned out to be much more similar to the original description by Pernet and Stein than Gene's, differing only by an additional unnecessary use of the HNF at the beginning (while Gene's, by virtue of using the Smith Normal Form, could be said to essentially use some variable number of extraneous uses of HNF). It is not clear how Gene derived his saturation algorithm from Pernet and Stein's work, however, if the fact that Dave and Douglas derived something almost identical to Pernet and Stein's algorithm from Gene's, it suggests that it's not unreasonable for development to lead someone in the opposite direction along the same path. The very close relationship between column Hermite defactoring and Pernet-Stein defactoring will be discussed shortly.

It should also be noted that toward the very beginning of Dave and Douglas's effort to develop a defactoring algorithm, Thomas McMurray Price described — in a message sent to the Xenharmonic Alliance Discord server — an algorithm almost identical to the Pernet-Stein algorithm, while also still being unaware of the Pernet-Stein paper. At this time, Dave and Douglas could not understand Tom's math well enough to realize that he'd just dropped the solution in their laps. Again, it wasn't until column Hermite defactoring was published that Tom commented on the findings and brought his ideas back into the conversation that Dave and Douglas realized the close connection between his ideas, Pernet-Stein defactoring, and column Hermite defactoring.

== New development: column Hermite defactoring ==

@@ Line 81: / Line 81: @@
 = Defactoring methods =
-Even better than identifying enfactored mappings is actually full-on defactoring them. Here are two methods that do just that: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [https://en.wikipedia.org/wiki/Henry_John_Stephen_Smith Henry John Stephen Smith], for whom the Smith normal form is named, which this method uses</ref>, and column Hermite defactoring, developed by Dave and Douglas (the name comes, of course, from Hermite normal form, which it uses<ref>named for Charles Hermite, who was French, by the way, and so his name is pronounced more like err-MEET, not like HER-might</ref>).
+Even better than identifying enfactored mappings is actually full-on defactoring them. Here are two methods that do just that: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [https://en.wikipedia.org/wiki/Henry_John_Stephen_Smith Henry John Stephen Smith], for whom the [[Smith normal form]] is named, which this method uses</ref>; Pernet-Stein defactoring, described by Clément Pernet and William Stein; and column Hermite defactoring, developed by Dave and Douglas (the name comes, of course, from Hermite normal form, which it uses<ref>named for Charles Hermite, who was French, by the way, and so his name is pronounced more like err-MEET, not like HER-might</ref>).
-Neither of these methods have been rigorously proven to always defactor mappings, but tests Douglas ran on thousands of random mappings strongly suggested that both methods work and give the exact same results as each other.
+Smith defactoring has not yet been mathematically proven to always defactor mappings, while Pernet-Stein and column Hermite defactoring have been proven. Tests Douglas ran on thousands of random mappings, however, strongly suggest that all three methods work all of the time. Pernet-Stein and column Hermite are more closely related, and so they give the exact same results as each other every time, whereas Smith defactoring sometimes gives different results; however, after taking the HNF of the results, all three do become exactly the same.
-This article prefers column Hermite defactoring to Smith defactoring because it is:
+Column Hermite defactoring is arguably the best defactoring algorithm because it is:
-* Cheaper computationally, wasting less resources computing things irrelevant to the result<ref>
+* Cheapest computationally, wasting less resources computing things irrelevant to the result<ref>
 Using the following code in Wolfram Language:<br>
 <span style="font-family: monospace; font-size: 10px;">hermiteUnimodular[m_]:=Transpose[First[HermiteDecomposition[Transpose[m]]]]<br>
@@ Line 104: / Line 104: @@
 <br>
 AbsoluteTiming[Do[smithDefactor[m],{m,ms}]]<br></span><br>
-The first several results for Smith defactoring took (in ms) 3.55919, 3.45199, 3.58493, 3.63464, 3.80917, 3.77151, while the first several results for column Hermite defactoring took 3.30063, 3.39137, 3.33808, 3.21195, 3.16469, 3.20419. So this suggests a slight edge for column Hermite defactoring.
+The first several results for Smith defactoring took (in ms) 3.55919, 3.45199, 3.58493, 3.63464, 3.80917, 3.77151, while the first several results for column Hermite defactoring took 3.30063, 3.39137, 3.33808, 3.21195, 3.16469, 3.20419. So this suggests a slight edge for column Hermite defactoring. Later, Pernet-Stein was also timed, and gave very slightly slower results than column Hermite defactoring, which makes sense because it is almost identical conceptually, except requires an additional matrix multiplication step.
 </ref>,
-* Is easy to understand how it works, and can be worked out by hand (as we will demonstrate below),
+* easy to understand how it works, and can be worked out by hand (as we will demonstrate below),
-* If interested, you can see what the common factor is, if there was any.
+* possible to find what the common factor is, if there was any.
 Column Hermite defactoring could not have been developed, however, were it not for Gene's pioneering work with the Smith defactoring (what he calls the process of "saturating" a mapping). At first Dave and Douglas had no idea what the right reducing matrix of the Smith decomposition (the process which also provides the Smith normal form) had to do with common factors, only that it somehow magically worked. So they analyzed the Smith decomposition until they isolated its key actions which actually effect the defactoring, and then honed their method down to do only these necessary actions. Again, they wouldn't have known where to start were it not for Gene.
@@ Line 145: / Line 145: @@
 And that result matches what Gene finds in that xen wiki article. Defactoring and normalizing is equivalent to canonicalization.
+== Precedent: Pernet-Smith defactoring ==
+This algorithm was described in the 2009 paper "Fast computation of HNF of random integer matrices"<ref>https://www.wstein.org/papers/hnf/pernet-stein-fast_computation_of_hnf_of_random_integer_matrices.pdf</ref> by Clément Pernet and William Stein. At the time Dave and Douglas wrote the first draft of this article and developed column Hermite defactoring, they were unaware of this algorithm. After publicizing column Hermite defactoring, they were referred by [[Graham Breed]] to a similar method in [http://x31eq.com/temper/ Graham's popular online regular temperament tool], implemented as <code>saturate</code><ref>https://bitbucket.org/x31eq/regular/src/9bc9b5bd8c8e0ced6223b29c3ea487719d120c43/kernel.py#lines-178</ref> which includes in its commented documentation a link to the aforementioned paper. Unable to reverse-engineer Gene Ward Smith's saturation algorithm, Graham had gone back to the same source Gene had supposedly gotten his inspiration from — the Sage software developed by William Stein, co-author of this paper — and came across this paper. Graham's implementation turned out to be much more similar to the original description by Pernet and Stein than Gene's, differing only by an additional unnecessary use of the HNF at the beginning (while Gene's, by virtue of using the Smith Normal Form, could be said to essentially use some variable number of extraneous uses of HNF). It is not clear how Gene derived his saturation algorithm from Pernet and Stein's work, however, if the fact that Dave and Douglas derived something almost identical to Pernet and Stein's algorithm from Gene's, it suggests that it's not unreasonable for development to lead someone in the opposite direction along the same path. The very close relationship between column Hermite defactoring and Pernet-Stein defactoring will be discussed shortly.
+It should also be noted that toward the very beginning of Dave and Douglas's effort to develop a defactoring algorithm, Thomas McMurray Price described — in a message sent to the Xenharmonic Alliance Discord server — an algorithm almost identical to the Pernet-Stein algorithm, while also still being unaware of the Pernet-Stein paper. At this time, Dave and Douglas could not understand Tom's math well enough to realize that he'd just dropped the solution in their laps. Again, it wasn't until column Hermite defactoring was published that Tom commented on the findings and brought his ideas back into the conversation that Dave and Douglas realized the close connection between his ideas, Pernet-Stein defactoring, and column Hermite defactoring.
 == New development: column Hermite defactoring ==