Defactoring algorithms: Difference between revisions

Line 81:

== Defactoring methods ==

~~Even better than identifying enfactored mappings is actually full-on defactoring them. Here are~~ three 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>~~).

In this section, we discuss three methods that defactors the mapping: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [[Wikipedia: 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).

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, have empirically proven 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.

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

Douglas argues that Column Hermite defactoring is the preferable defactoring algorithm particularly when the routine for Hermite normal form also gives a [[Wikipedia: Unimodular matrix|unimodular]] transformation matrix, such as that in [[Wikipedia: Wolfram Language|Wolfram Language]]. The following reasons are listed:

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

* It is computationally cheap, wasting little 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 106:

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

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

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

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

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

[[Flora Canou]] has contended that these features are shared by the Pernet-Stein method, and that the Pernet-Stein method is simpler when the unimodular matrix is not provided.

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 81: / Line 81: @@
 == Defactoring methods ==
-Even better than identifying enfactored mappings is actually full-on defactoring them. Here are three 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>).
+In this section, we discuss three methods that defactors the mapping: Smith defactoring, developed by Gene Ward Smith<ref>but the name comes from a different Smith: [[Wikipedia: 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).
 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, have empirically proven 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.
-Column Hermite defactoring is arguably the best defactoring algorithm because it is:
+Douglas argues that Column Hermite defactoring is the preferable defactoring algorithm particularly when the routine for Hermite normal form also gives a [[Wikipedia: Unimodular matrix|unimodular]] transformation matrix, such as that in [[Wikipedia: Wolfram Language|Wolfram Language]]. The following reasons are listed:
-* Cheapest computationally, wasting less resources computing things irrelevant to the result<ref>
+* It is computationally cheap, wasting little 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 106: / Line 106: @@
 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>,
-* easy to understand how it works, and can be worked out by hand (as we will demonstrate below),
+* the way it works is easy to understand, and can be worked out by hand (as we will demonstrate below),
-* possible to find what the common factor is, if there was any.
+* it is possible to find what the common factor is, if there was any.
+[[Flora Canou]] has contended that these features are shared by the Pernet-Stein method, and that the Pernet-Stein method is simpler when the unimodular matrix is not provided.
 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.