Defactoring: Difference between revisions

Line 304:

One reason for doing a column Hermite decomposition on a mapping can be understood by comparing the sizes of the unimodular matrices. Matrices are often described as <math>m×n</math>, where <math>m</math> is the row count and <math>n</math> is the column count. In the case of mappings it may be superior to use variable names corresponding to the domain concepts of rank <math>r</math>, and dimension <math>d</math>, i.e. to speak of <math>r×d</math> mappings. The key bit of info here is that — for non-trivial mappings, anyway — <math>d</math> is always greater than <math>r</math>. So a standard row-based Hermite decomposition, i.e. to the right, is going to produce an <math>r×r</math> unimodular matrix, while a column-based Hermite decomposition, i.e. to the bottom, is going to produce a <math>d×d</math> unimodular matrix. For example, 5-limit meantone has <math>r=2</math> and <math>d=3</math>, so a standard row-based Hermite decomposition is going to produce a unimodular matrix that is only 2×2, while the column-based Hermite decomposition will produce one that is 3×3. With <math>d>r</math>, it's clear that the column-based decomposition in general will always produced the larger unimodular matrix. In fact, the row-based decomposition is too small to be capable of enclosing an amount of entries equal to the count of entries in the original mapping, and therefore it could never support preserving the entirety of the important information from the input (in terms of our example, a 3×3 matrix can hold a 2×3 matrix, but a 2×2 matrix cannot).

==== relationship with Smith defactoring ====

If you describe column Hermite defactoring as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite ... inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until you've achieved Smith normal form, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.

==== by hand ====

@@ Line 304: / Line 304: @@
 One reason for doing a column Hermite decomposition on a mapping can be understood by comparing the sizes of the unimodular matrices. Matrices are often described as <span><math>m×n</math></span>, where <span><math>m</math></span> is the row count and <span><math>n</math></span> is the column count. In the case of mappings it may be superior to use variable names corresponding to the domain concepts of rank <span><math>r</math></span>, and dimension <span><math>d</math></span>, i.e. to speak of <span><math>r×d</math></span> mappings. The key bit of info here is that — for non-trivial mappings, anyway — <span><math>d</math></span> is always greater than <span><math>r</math></span>. So a standard row-based Hermite decomposition, i.e. to the right, is going to produce an <span><math>r×r</math></span> unimodular matrix, while a column-based Hermite decomposition, i.e. to the bottom, is going to produce a <span><math>d×d</math></span> unimodular matrix. For example, 5-limit meantone has <span><math>r=2</math></span> and <span><math>d=3</math></span>, so a standard row-based Hermite decomposition is going to produce a unimodular matrix that is only 2×2, while the column-based Hermite decomposition will produce one that is 3×3. With <span><math>d>r</math></span>, it's clear that the column-based decomposition in general will always produced the larger unimodular matrix. In fact, the row-based decomposition is too small to be capable of enclosing an amount of entries equal to the count of entries in the original mapping, and therefore it could never support preserving the entirety of the important information from the input (in terms of our example, a 3×3 matrix can hold a 2×3 matrix, but a 2×2 matrix cannot).
+==== relationship with Smith defactoring ====
+If you describe column Hermite defactoring as "column-Hermite inverse take-r-rows", the analogous way to describe Smith defactoring would be like "row-Hermite column-Hermite row-Hermite column-Hermite row-Hermite column-Hermite ... inverse take-r-rows". In other words, the nature of Smith decomposition is to essentially repeatedly Hermite decompose from either angle until you've achieved Smith normal form, which is wasteful and unnecessary in this context, when all that is required is a single column-Hermite decomposition. This helps explain why column Hermite defactoring is more performant in general than Smith defactoring, when code is run against thousands of examples at a time.
 ==== by hand ====