Ralf Hemmecke wrote: > > There is seemingly a problem with the implementation of some functions > from PolynomialFactorizationImplizit in Integer as well as in > FractionInteger.
Well, some parts of machinery related to PolynomialFactorizationExplicit are still unimplemented. ATM my tactic is to avoid puting in a lot of new code, rather I would like to reduce redundancy and eliminate some bugs: - several domains have specialized polynomial factorizers. They are faster than general code so I do not want to simply drop them. Rather, I would like to transfer speed improvements to general code and only after that drop old factorizers - positive characteristic case has large unimplemented part (here relation between square-free factorization and full one is more tricky). - current code assumes that it can factor polynomials in 3 or more variables over finite fields without using field extentions for evaluation points. IIUC this is false, but counter examples are very rare. - for speed 'solveLinearPolynomialEquation' and 'gcdPolynomial' should use modular methods if possible. I believe that using Zippel method would give us large speed improvements (there are newer things than Zippel, it is not clear fro me if they give worthwile improvement over Zippel). Current general case uses fractions which is slower than almost any alternative. In particular I do not want to use this code when we have better specialized version. - in general, PolynomialFactorizationExplicit is build via recursion. This is nice from point of view of high level coding, but means that some expensive computations at lower level need to be done multiple times. IIUC original authors assumed that caching can eliminate cost of multiple evaluation, but caching has its own problems and when we make random choices it simply does not work. In fact I was thinking about something which could be called AlgebraicallyExplicit, that is domains for which we can get information about generators and relations. In other words, we can build explicit partial izomorphizm with subset of algebraic extention of field of rational functions. > In fact, I can only guess what the function "factorSquareFreePolynomial" > should actually return. > > http://fricas.github.io/api/PolynomialFactorizationExplicit.html#l-polynomial-factorization-explicit-factor-square-free-polynomial > > factorSquareFreePolynomial: SparseUnivariatePolynomial % -> Factored > SparseUnivariatePolynomial % > factorSquareFreePolynomial(p) factors the univariate polynomial p > into irreducibles where p is known to be square free and primitive with > respect to its main variable. > > Isn't it strange that it must be mentioned that p is square-free when it > is supposed to be irreducible? Are there irreducible polynomials that > are not square-free? Well, each function has preconditions, that is conditions that is input must satisfy, and postconditions that is what output satisfies. In this case: Precondition: p is square-free and primitive Postcondition: output is factorization of p into irreducibles. If you know a little about factorization precondition is natural: core factorization methods only work for square-free and primitive polynomials. Full factorization routine first computes square-free factorization and make polynomial primitive. Only after that calls core factorizer. If we know that polynomial is square-free and primitive, we can skip first part and directly go to core factorization. In other words, 'factorSquareFreePolynomial' is core factorizer and before calling it you may need some proprocessing. > Ralf > > ================================================================= > (1) -> Z==>Integer;Q==>Fraction Z;SUP==>SparseUnivariatePolynomial > Type: > Void > (2) -> f := (((x-1)*x)^2) :: SUP Z > > 4 3 2 > (2) ? - 2 ? + ? > Type: > SparseUnivariatePolynomial(Integer) > (3) -> squareFree f > > 2 2 > (3) (? - ?) > Type: > Factored(SparseUnivariatePolynomial(Integer)) > (4) -> squareFreePolynomial f > > 2 2 > (4) (? - ?) > Type: > Factored(SparseUnivariatePolynomial(SparseUnivariatePolynomial(Integer))) > (5) -> squareFreePolynomial(f)$Z > > 2 2 > (5) (? - ?) > Type: > Factored(SparseUnivariatePolynomial(Integer)) > (6) -> factor f > > 2 2 > (6) (? - 1) ? > Type: > Factored(SparseUnivariatePolynomial(Integer)) > (7) -> factorSquareFreePolynomial f > > 2 2 > (7) (? - 1) ? > Type: > Factored(SparseUnivariatePolynomial(SparseUnivariatePolynomial(Integer))) You violated precondition, so can not expect sensible result. You may get one (this case probably went trough full factorizer), but there is no warranty. > (8) -> factorSquareFreePolynomial(f)$Z > 2 2 <menu-bar> <signals> <break> > >> System error: > Interactive interrupt at #x5261AA8C. Again, you violated precondition, so can not expect sensible result. In fact, if you look at implementation it is clear that infinite loop is expected here. > (8) -> )clear prop f > (8) -> f := (((x-1)*x)^2) :: SUP Q > > 4 3 2 > (8) ? - 2 ? + ? > Type: > SparseUnivariatePolynomial(Fraction(Integer)) > (9) -> squareFree f > > 2 2 > (9) (? - ?) > Type: > Factored(SparseUnivariatePolynomial(Fraction(Integer))) > (10) -> squareFreePolynomial f > > 2 2 > (10) (? - ?) > Type: > Factored(SparseUnivariatePolynomial(SparseUnivariatePolynomial(Fraction(Integer)))) > (11) -> squareFreePolynomial(f)$Q > Internal Error > The function squareFreePolynomial with signature hashcode is missing > from domain Fraction(Integer) Well, Hyperdoc clearly shows that it is unimplemented. > (11) -> factor f > > 2 2 > (11) (? - 1) ? > Type: > Factored(SparseUnivariatePolynomial(Fraction(Integer))) > (12) -> factorSquareFreePolynomial f > > 2 2 > (12) (? - 1) ? > Type: > Factored(SparseUnivariatePolynomial(SparseUnivariatePolynomial(Fraction(Integer)))) > (13) -> factorSquareFreePolynomial(f)$Q > <menu-bar> <signals> <break> > >> System error: > Interactive interrupt at #x52100D0C. > > -- > You received this message because you are subscribed to the Google Groups > "FriCAS - computer algebra system" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/fricas-devel/21f9e895-d148-ef07-f8f8-335d95f07304%40hemmecke.org. > > --------------65B11D43D9146833BA47C104 > Content-Type: text/plain; charset=UTF-8; > name="sfp-bug.input" > Content-Transfer-Encoding: base64 > Content-Disposition: attachment; > filename="sfp-bug.input" > > KWNsZWFyIGNvbXBsZXRlClo9PT5JbnRlZ2VyO1E9PT5GcmFjdGlvbiBaO1NVUD09PlNwYXJz > ZVVuaXZhcmlhdGVQb2x5bm9taWFsCmYgOj0gKCgoeC0xKSp4KV4yKSA6OiBTVVAgWgpzcXVh > cmVGcmVlIGYKc3F1YXJlRnJlZVBvbHlub21pYWwgZgpzcXVhcmVGcmVlUG9seW5vbWlhbChm > KSRaCmZhY3RvciBmCmZhY3RvclNxdWFyZUZyZWVQb2x5bm9taWFsIGYKZmFjdG9yU3F1YXJl > RnJlZVBvbHlub21pYWwoZikkWgoKKWNsZWFyIHByb3AgZgpmIDo9ICgoKHgtMSkqeCleMikg > OjogU1VQIFEKc3F1YXJlRnJlZSBmCnNxdWFyZUZyZWVQb2x5bm9taWFsIGYKc3F1YXJlRnJl > ZVBvbHlub21pYWwoZikkUQpmYWN0b3IgZgpmYWN0b3JTcXVhcmVGcmVlUG9seW5vbWlhbCBm > CmZhY3RvclNxdWFyZUZyZWVQb2x5bm9taWFsKGYpJFEK > --------------65B11D43D9146833BA47C104-- > -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/E1ieh6R-0002dq-E5%40hera.math.uni.wroc.pl.
