Talk:Defactoring algorithms: Difference between revisions

← Older edit Newer edit →

VisualWikitext

@@ Line 73: / Line 73: @@
 :::: [[User:FloraC|FloraC]] ([[User talk:FloraC|talk]]) 10:58, 10 February 2023 (UTC)
+::::: Ah, very interesting. Thank you for this. I've reviewed that GitHub thread, in particular https://github.com/sympy/sympy/pull/22845#issuecomment-1013936367, "It looks like [Cohen's] Alg 2.4.10 is almost exactly the same [as Alg 2.4.5] except that it also computes the unimodular matrix." Cohen's 2.4.5 is what's implemented in sympy here: https://github.com/sympy/sympy/blob/99b4abb6313990136cde93735f552a6a98152fc6/sympy/polys/matrices/normalforms.py#L177-L248 . Cohen's work can be found here: http://tomlr.free.fr/Math%E9matiques/Math%20Complete/Number%20theory/A%20course%20in%20computational%20algebraic%20number%20theory%20-%20Cohen%20H..pdf (2.4.5 is on page 69, and 2.4.10 is on page 74). So, yes, I can now see that it is possible to compute HNF without also computing the unimodular matrix. However, the unimodular matrix comes essentially for free; it's nothing but the same operations the algorithm chooses to apply to the original matrix, but also applied to an identity matrix. The main effort of the algorithm is choosing those unimodular transformations; tracking them is almost zero cost, computationally.
+::::: So I think the article should be amended to reflect this fact. Sorry I missed it.
+::::: However, in order to prove that Pernet-Stein is more efficient than column Hermite defactoring, you'd have to prove that its extra matrix multiplication step at the end is cheaper than just tracking the unimodular transformations applied to the original matrix. Intuitively, I doubt this is the case. Maybe they'd be almost the same. But empirically testing this would be more work than I'm willing to invest. So it's fine by me if you want to include both methods for now.
+::::: I don't particularly care about "beating" Pernet and Stein. I only wanted to simplify things for our readership if I could. Maybe one day we could settle it. It would be a big win if we only had to teach them one method.
+::::: And regardless to the outcome of possible empirical performance testing, assuming the results will be very very similar whichever way that goes, I think we should teach the one which is the most straightforward to understand ''why''/''how'' it works. I make an argument in the article for that being column Hermite defactoring. You are welcome to write a counterargument for Pernet-Stein if you see it differently, and believe that some readers will find ''its'' process more obvious and illuminating.
+::::: In short, if we can't agree on one algorithm, that's alright. It's not necessarily a strict loss. We can still find a different sort of mutual strength through our different approaches to the problem.
+::::: As for this part of what you said, though, I'm sorry, but I can't figure out what you're referring to: "Then you actually use U<sup>-1</sup> 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." Can you explain another way? Perhaps it may be helpful to reference this set of flow charts I prepared: https://en.xen.wiki/w/File:Comparison_of_defactoring_algorithms.png --[[User:Cmloegcmluin|Cmloegcmluin]] ([[User talk:Cmloegcmluin|talk]]) 17:37, 10 February 2023 (UTC)