Talk:Defactoring algorithms

Readability and conclusion

This article is way too hard to read than necessary. It looks more like a note rather than an article, with so much development information that's better off collected in a dedicated "history" section. The algorithms should be presented much much more concisely.

The algorithms are currently presented in Mathematica, which isn't quite easy to decode. I think it should be presented in math formula or pseudocode.

The conclusion seems pretty subjective. I'm not sure "Hermite decomposition" can be treated as a single operation. It's (perhaps superficially) the case in Mathematica, but not in other programming languages or math in general.

~~I wonder if the original author(s) of this article will do me a favor to allow me to clean it up. Otherwise I'll have to start anew.~~

FloraC (talk) 10:09, 4 February 2023 (UTC)

Aw, dang. I'm sorry that it was hard for you to read. It feels like so long since I thought about this topic. I think it's good for it to have a new pair of eyes on it, to help balance out my own idiosyncrasies. Please feel free to take a pass on everything, improving the article how you see fit. If we can come to a consensus on how best to present it, that will be best for the community. I only wish for anyone who wants to understand this stuff to have good resources for doing so. I'm glad you're interested in the same stuff! --Cmloegcmluin (talk) 17:32, 4 February 2023 (UTC)

Thank you for giving me the green light. FloraC (talk) 19:20, 4 February 2023 (UTC)

Well I changed my mind. I decided to leave the contents of this dev-note- and research-style page as is, and start anew at Saturation, torsion, and contorsion/Methods, since what I actually want is an encyclopedic article that is suitable for reference. I'm taking the liberty instead of moving this page to something like Research on defactoring algorithms. FloraC (talk) 09:35, 9 February 2023 (UTC)

Hm. Well, as I said before, I'd really rather you not start anew, for the benefit of the community. Could we please first at least try to find a way together to make this article work in your eyes, then? (Note: by the end of this reply, I come to see things closer to the way you see them, but I'd like you to see my thought process.)

I have no problem with presenting algorithms in pseudocode. Feel free to make that change.

I certainly agree that the "Other defactoring methods" section is dev note and research related. Dave himself has recommended I leave out. So I can take that part out, no problem.

As for the main "Defactoring methods" section, however, it seems we have a decision to make. We can either:

1) consider column Hermite defactoring to be the only relevant method, and thus the info on the other two is dev notes,

2) consider all three methods to be relevant, and thus none of them are dev notes.

Personally, I think that it's clear that column Hermite defactoring is the only relevant method, and so the information on the other two should be taken out.

(Why did Dave and I include them in the first place? As you can probably understand, and maybe you also remember: we were introducing our defactoring findings as part of a greater effort, including terminological reform, and a questioning of the usefulness of the EA branch of RTT. So we felt it was important to err on the side of caution, carefully providing all of our research, evidence, proofs, etc. At this point 15 months later, however, it does definitely seem a bit overkill.)

However, I'm not certain you agree that column Hermite defactoring is superior, because you say: "The conclusion seems pretty subjective." I don't know which "conclusion" you're referring to, but my best guess is that you are referring to the statement, "Column Hermite defactoring is arguably the best defactoring algorithm". However, I don't understand how the rest of what you say on that pertains to this. You question whether Hermite decomposition is a "single operation". I don't recall stating in the article that it is a single operation. And I don't know or care whether it is. That doesn't seem relevant to the argument.

* Comparing column Hermite defactoring with the Pernet-Stein method, it's irrelevant because they have the same steps except Pernet-Stein has an extra step.

* Comparing with Smith defactoring it's irrelevant, because Smith defactoring's Smith decomposition is equivalent to repeated Hermite decomposition, as we explain here: "...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."

But perhaps you have a different understanding of the relationship between the Hermite and Smith decompositions that you could explain for me. I do not consider myself an expert from the math side of things. My conclusions, as you know, are based on a bit of math research and a lot of empirical testing with code.

I do appreciate that I have a tendency to write articles on this wiki in a style that is less like an encyclopedia and more like a beginner's textbook. Of course, Wikipedia is an encyclopedia, per the "pedia" part, but in general, wikis don't have to be encyclopedic in style. I rather like how this article starts by getting the reader comfortable with the idea of enfactored mappings and comma bases. And I think it's good to include the brief "Finding the greatest factor" section at the end, too.

Anyway, now as I go over the "New development: column Hermite defactoring" section, even if we decided this was the only method worth keeping here, I can see that you might find a lot of that information tedious, too: the "How/why it works" and "By hand" sections are both way more in my textbook style, less in your encyclopedic style. So, perhaps we should provide two separate resources, since there may be two different learning types which shouldn't be compromised together. That said:

* While it's fine with me if you think this article's title is misleading and needs to be changed, I don't think "Research on defactoring algorithms" is quite right. It's more than only that, particularly on account of the introduction for beginners, tutorials by example, proofs, etc. Perhaps it's more of a "Guide to defactoring". (Though I'm sorry it was not very helpful to you as a guide, that is certainly its intention, given its structure, style, and contents.)

* I recommend that you only need "Saturation, torsion, and contorsion/Method". Singular. That is, I think you only need to document column Hermite defactoring if you are doing a separate encyclopedic type article.

--Cmloegcmluin (talk) 17:13, 9 February 2023 (UTC)

I'm afraid your conclusion (that the column Hermite defactoring was the superior method) was critically affected by Mathematica, the tool of your choice, as it wraps "Hermite decomposition" as a single operation where you simultaneously get both the Hermite normal form and the unimodular matrix. In general, this isn't the case. For example, in SymPy, you have direct access to the function HNF: A → H. You gotta obtain the unimodular matrix U = HA⁺ from UA = H. So using the unimodular matrix involves three steps:

find H = HNF (A);
find the pseudoinverse A⁺;
Multiply them.

By contrast, the Pernet-Stein method only needs H i.e. the first step at this point. It could be simplified a bit in an algorithm that's designed to return both, but the unimodular matrix is still something more than the HNF itself (see discussion at add igcdLLL to numbers by smichr · Pull Request #22845 · sympy/sympy). Your comparsion made it as if they were the same.

Then you actually use U^-1 instead of U, so to sum it up you're taking an inverse after taking a pseudoinverse, with multiplication involved also. That looks to me like there's a lot of back and forth in it.

That's why I chose to implement Pernet-Stein in my code:

import numpy as np
from scipy import linalg
from sympy import Matrix

def __hnf (main):
    return np.flip (np.array (normalforms.hermite_normal_form (Matrix (np.flip (main)).T).T, dtype = int))

def __sat (main):
    return np.rint (linalg.inv (__hnf (main.T).T) @ main).astype (int)

where __hnf is just a wrapper for A → H due to SymPy's unusual implementation as we know. Note it somehow removes the extra rows of zeros already.

So my finding is a 180-degree turn from yours, and I'll insist that Pernet-Stein be included. To be clear I never intended to remove any of these methods, but I just want every word to count. For example, in the first section I think one obvious enfactoring and one hidden enfactoring are enough to show the possibility as well as the difficulty of the heuristic method.

I accept the other suggestions and I'm dropping the idea of starting anew or changing the title.

FloraC (talk) 10:58, 10 February 2023 (UTC)