[sage-devel] Re: Multivariate polynomial factoring and bug(?)
I actually tried taking linear combinations of the coefficients, to see if that would help, after reading the suggestion in a paper. But it turned out to be so much slower than not doing it, that I abandoned it. However, I didn't take the size of the coefficients into account, so I certainly wasn't doing exactly what you suggested. It could be worth a try. Bill. On Saturday, 12 November 2016 19:22:12 UTC+1, parisse wrote: > > > > Le samedi 12 novembre 2016 08:16:41 UTC+1, Bill Hart a écrit : >> >> >> >> >> I wonder if it is sometimes worth taking the gcd G of the leading >> coefficients of the original primitive polynomials and then taking the gcd >> H of that with the leading coefficient L of the result of the psr process, >> and then trying L/H as the possible content. >> > > No idea, I don't think this will happen frequently. I would probably first > try to improve content computation by taking random combination of the > coefficients and the smallest one (numbers of monomials). > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Le samedi 12 novembre 2016 08:16:41 UTC+1, Bill Hart a écrit : > > > > > I wonder if it is sometimes worth taking the gcd G of the leading > coefficients of the original primitive polynomials and then taking the gcd > H of that with the leading coefficient L of the result of the psr process, > and then trying L/H as the possible content. > No idea, I don't think this will happen frequently. I would probably first try to improve content computation by taking random combination of the coefficients and the smallest one (numbers of monomials). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
On Saturday, November 12, 2016 at 4:00:15 PM UTC, Ralf Stephan wrote: > > Sorry for hijacking. Do you know if there exists a (more) efficient > multivar poly factoring algorithm (than the general one) for factors > linear in the variables, and coefficients in ZZ? Maybe a geometrical > method using lines? > I looked at it when we wanted to see how to implement things developed in https://arxiv.org/abs/1210.3193 IMHO nothing is known, but my guess is that Gao's method (see e.g. Sect 3.1 of http://www4.ncsu.edu/~kaltofen/bibliography/07/KMYZ07.pdf) might be more suited here---perhaps with some modifications. Dima > > Regards, > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Sorry for hijacking. Do you know if there exists a (more) efficient multivar poly factoring algorithm (than the general one) for factors linear in the variables, and coefficients in ZZ? Maybe a geometrical method using lines? Regards, -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
On Saturday, 12 November 2016 08:14:25 UTC+1, Bill Hart wrote: > > > I wonder if it is sometimes worth taking the gcd G of the leading > coefficients of the original primitive polynomials and then taking the gcd > of that with the leading coefficient L of the result of the psr process, > and then trying L/G as the possible content. Of course one would only want > to try that if other tricks have failed to find the content. > > Sorry, meant: I wonder if it is sometimes worth taking the gcd G of the leading coefficients of the original primitive polynomials and then taking the gcd H of that with the leading coefficient L of the result of the psr process, and then trying L/H as the possible content. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
On Saturday, 12 November 2016 07:42:53 UTC+1, parisse wrote: > > > > Le samedi 12 novembre 2016 06:50:45 UTC+1, Bill Hart a écrit : >> >> >> >> Looking how the content (188 monomials) is computed, it's done by exact >>> divisions only (it's the leading coefficient up to trivial coefficients). >>> >> >> Can you give me a hint where this is implemented. I didn't find this >> yesterday. It's a nice trick. >> >> > It's in gausspol.cc, around line 4100 "Trying p/lgcd(p)) as gcd". If the > degree of the gcd of the evaluation is the same as the degree of one of the > arguments, then there is a very good chance that the gcd itself is one of > the argument. > I think it's a good idea to look at sources, most papers do not describe > tricks, and some papers/books are written by people that did not really > implement, which means they miss some points. > Thanks. I agree, sometimes source code is extremely useful to have. I've implemented something similar now and it works! By the way, the times I reported the other day are not correct. At the time I didn't have code implemented for removing content at the end, and I also had some bugs in my exact division code. Once I implemented code to remove the final content, I was horrified to discover it was almost all of the runtime. I wonder if it is sometimes worth taking the gcd G of the leading coefficients of the original primitive polynomials and then taking the gcd of that with the leading coefficient L of the result of the psr process, and then trying L/G as the possible content. Of course one would only want to try that if other tricks have failed to find the content. Bill. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Le samedi 12 novembre 2016 06:50:45 UTC+1, Bill Hart a écrit : > > > > Looking how the content (188 monomials) is computed, it's done by exact >> divisions only (it's the leading coefficient up to trivial coefficients). >> > > Can you give me a hint where this is implemented. I didn't find this > yesterday. It's a nice trick. > > It's in gausspol.cc, around line 4100 "Trying p/lgcd(p)) as gcd". If the degree of the gcd of the evaluation is the same as the degree of one of the arguments, then there is a very good chance that the gcd itself is one of the argument. I think it's a good idea to look at sources, most papers do not describe tricks, and some papers/books are written by people that did not really implement, which means they miss some points. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
By the way, yesterday I implemented algorithm 3 in Brown's paper on psrgcd. I didn't notice any improvement, so I abandoned it. I wasn't able to decide whether algorithm 4 is actually an algorithm, let alone whether it would be worth implementing, so I didn't bother with that. Bill. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
On Friday, 11 November 2016 21:00:49 UTC+1, parisse wrote: > > > > Le vendredi 11 novembre 2016 07:03:46 UTC+1, Bill Hart a écrit : >> >> I assume you are using the modular algorithm to remove the final lot of >> content at the end of the psr algorithm. Otherwise the algorithm takes >> quite a long time, since even if we remove the known factors of the content >> along the way, as specified by the algorithm, the result is far from >> primitive, and so computing the content in the final step of the algorithm >> takes a long time. >> >> Bill. >> > > I'm using a trick for the last step of psrgcd: since the gcd should be of > degree 6 wrt y (obtained by evaluation of other variables), when I have the > remainder of degree 6 (1276 monomials), I check that the division from the > previous remainder (102 monomials) with the primitive part of this > remainder is exact, this saves one pseudo-division. > I was looking at the source code yesterday and noticed that you figure out the likely degree of the gcd, but I couldn't figure out where it was actually used. But now I think I see where you are using it. > Looking how the content (188 monomials) is computed, it's done by exact > divisions only (it's the leading coefficient up to trivial coefficients). > Can you give me a hint where this is implemented. I didn't find this yesterday. It's a nice trick. Bill. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Le vendredi 11 novembre 2016 07:03:46 UTC+1, Bill Hart a écrit : > > I assume you are using the modular algorithm to remove the final lot of > content at the end of the psr algorithm. Otherwise the algorithm takes > quite a long time, since even if we remove the known factors of the content > along the way, as specified by the algorithm, the result is far from > primitive, and so computing the content in the final step of the algorithm > takes a long time. > > Bill. > I'm using a trick for the last step of psrgcd: since the gcd should be of degree 6 wrt y (obtained by evaluation of other variables), when I have the remainder of degree 6 (1276 monomials), I check that the division from the previous remainder (102 monomials) with the primitive part of this remainder is exact, this saves one pseudo-division. Looking how the content (188 monomials) is computed, it's done by exact divisions only (it's the leading coefficient up to trivial coefficients). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
I assume you are using the modular algorithm to remove the final lot of content at the end of the psr algorithm. Otherwise the algorithm takes quite a long time, since even if we remove the known factors of the content along the way, as specified by the algorithm, the result is far from primitive, and so computing the content in the final step of the algorithm takes a long time. Bill. On Wednesday, 9 November 2016 20:24:56 UTC+1, parisse wrote: > > > > Le mercredi 9 novembre 2016 17:42:32 UTC+1, Bill Hart a écrit : >> >> I implemented a multivariable psr GCD algorithm in Julia and now the >> timings are as follows: >> >> * if z or x is the main variable, it takes a long time (too long to wait >> for) >> >> * if t or y is the main variable it takes 0.1 - 0.2s on average, >> depending on the exact ordering, with the one exception below >> >> * for variables in the order y, x, z, t with y the main variable, it >> takes 1.1s >> >> I have to admit this was about my fourth attempt at implementing the psr >> algorithm. I settled on a sparse univariate format for the main variable >> and sparse distributed format for the remaining variables. >> >> Of course there are much better algorithms for sparse gcds like this. >> Funnily enough, Magma takes 4s, though its timings presumably don't depend >> on the ordering, since they are proper sparse gcd algorithms. >> >> > Comparing with my own timings (0.1s for psrgcd and 18s for modular gcd), I > would guess that Magma is using the modular gcd algorithm and does not have > heuristics to select psrgcd unlike giac. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Le mercredi 9 novembre 2016 17:42:32 UTC+1, Bill Hart a écrit : > > I implemented a multivariable psr GCD algorithm in Julia and now the > timings are as follows: > > * if z or x is the main variable, it takes a long time (too long to wait > for) > > * if t or y is the main variable it takes 0.1 - 0.2s on average, depending > on the exact ordering, with the one exception below > > * for variables in the order y, x, z, t with y the main variable, it takes > 1.1s > > I have to admit this was about my fourth attempt at implementing the psr > algorithm. I settled on a sparse univariate format for the main variable > and sparse distributed format for the remaining variables. > > Of course there are much better algorithms for sparse gcds like this. > Funnily enough, Magma takes 4s, though its timings presumably don't depend > on the ordering, since they are proper sparse gcd algorithms. > > Comparing with my own timings (0.1s for psrgcd and 18s for modular gcd), I would guess that Magma is using the modular gcd algorithm and does not have heuristics to select psrgcd unlike giac. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Thanks very much for writing up this brief note. I'm collecting algorithms at the moment, for an eventual assault on multivariate factoring. This may be useful! Bill. On Tuesday, 8 November 2016 21:03:01 UTC+1, parisse wrote: > > I have improved the sparse multivariate factorization algorithm in giac > 1.2.2-101, it will factor the given polynomial in about 2s. It is based on > a simple idea of comparing a few bivariate factorizations, it is explained > here https://hal.archives-ouvertes.fr/hal-01394062 in order to help other > open-source systems to implement it if they wish. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
I implemented a multivariable psr GCD algorithm in Julia and now the timings are as follows: * if z or x is the main variable, it takes a long time (too long to wait for) * if t or y is the main variable it takes 0.1 - 0.2s on average, depending on the exact ordering, with the one exception below * for variables in the order y, x, z, t with y the main variable, it takes 1.1s I have to admit this was about my fourth attempt at implementing the psr algorithm. I settled on a sparse univariate format for the main variable and sparse distributed format for the remaining variables. Of course there are much better algorithms for sparse gcds like this. Funnily enough, Magma takes 4s, though its timings presumably don't depend on the ordering, since they are proper sparse gcd algorithms. Bill. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
I have improved the sparse multivariate factorization algorithm in giac 1.2.2-101, it will factor the given polynomial in about 2s. It is based on a simple idea of comparing a few bivariate factorizations, it is explained here https://hal.archives-ouvertes.fr/hal-01394062 in order to help other open-source systems to implement it if they wish. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Actually, I didn't even know that I changed the variable (because the fricas interface treats all these as POLY INT). So I did a test in fricas, and indeed, the bad ordering seems to be with y as first variable. Having t first takes no time even on my (old) laptop, having z first takes a second, having x first takes a few seconds... Sorry for the noise. Martin -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Actually, I've now checked and it looks like Fricas uses PSR, which will take forever on this problem if you have the variable ordering with x the main variable. Of course I'm not terribly familiar with the source code layout of Fricas, so I could be wrong here. Bill. On Friday, 4 November 2016 17:54:43 UTC+1, Bill Hart wrote: > > > > On Friday, 4 November 2016 17:38:17 UTC+1, Bill Hart wrote: >> >> Sure, if you change the order of the variables it will finish in no time >> using PSR. >> > > Sorry, I should have said that x has to be the main variable. I could > design some polys for which the timing didn't depend on the main variable, > but for now, x has to be the main variable to see how slow this is (at > least in Sage and Singular). I'm not sure if the first or last variable is > x in Fricas, but if you define your polynomial ring so that the first or > last variable is x, you will likely see a big slowdown. Of course Fricas > may also just use a really fast algorithm. I didn't check. > > Bill. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
On Friday, 4 November 2016 17:38:17 UTC+1, Bill Hart wrote: > > Sure, if you change the order of the variables it will finish in no time > using PSR. > Sorry, I should have said that x has to be the main variable. I could design some polys for which the timing didn't depend on the main variable, but for now, x has to be the main variable to see how slow this is (at least in Sage and Singular). I'm not sure if the first or last variable is x in Fricas, but if you define your polynomial ring so that the first or last variable is x, you will likely see a big slowdown. Of course Fricas may also just use a really fast algorithm. I didn't check. Bill. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Sure, if you change the order of the variables it will finish in no time
using PSR.
On Friday, 4 November 2016 17:27:27 UTC+1, Martin R wrote:
>
> FriCAS does this in no time:
>
> sage: R. = PolynomialRing(QQ)
>
> sage: f = z^40*y^6*x^2100 + 2*t^15*z^53*y^9*x^2078 + z^40*y^7*x^2003 +
> z^40*y^6*x^2000 - 14*z^31*y^6*x^1102 - 2*t*z^20*y^3*x^1101 +
> 78*z^20*y^3*x^1100 - 28*t^15*z^44*y^9*x^1080 - 4*t^16*z^33
> : *y^6*x^1079 + 156*t^15*z^33*y^6*x^1078 - 14*z^31*y^7*x^1005 -
> 2*t*z^20*y^4*x^1004 + 78*z^20*y^4*x^1003 - 14*z^31*y^6*x^1002 -
> 2*t*z^20*y^3*x^1001 + 78*z^20*y^3*x^1000 + 49*z^22*y^6*x^1
> : 04 + 14*t*z^11*y^3*x^103 + (-546*z^11*y^3 + t^2)*x^102 - 78*t*x^101
> + 1521*x^100 + 98*t^15*z^35*y^9*x^82 + 28*t^16*z^24*y^6*x^81 +
> (-1092*t^15*z^24*y^6 + 2*t^17*z^13*y^3)*x^80 - 156*t^
> : 16*z^13*y^3*x^79 + 3042*t^15*z^13*y^3*x^78 + 49*z^22*y^7*x^7 +
> 14*t*z^11*y^4*x^6 + (-546*z^11*y^4 + t^2*y)*x^5 + (49*z^22*y^6 -
> 78*t*y)*x^4 + (14*t*z^11*y^3 + 1521*y)*x^3 + (-546*z^11*
> : y^3 + t^2)*x^2 - 78*t*x + 1521
>
> sage: g = 4*x^1156*y^9*z^46*t^30 + 4*x^1178*y^6*z^33*t^15 +
> x^1200*y^3*z^20 + 4*x^1081*y^7*z^33*t^15 + 4*x^1078*y^6*z^33*t^15 +
> 2*x^1103*y^4*z^20 + 2*x^1100*y^3*z^20 + x^1006*y^5*z^20 + 2*x^
> : 1003*y^4*z^20 + x^1000*y^3*z^20 - 28*x^158*y^9*z^37*t^30 -
> 28*x^180*y^6*z^24*t^15 - 4*x^157*y^6*z^26*t^31 + 156*x^156*y^6*z^26*t^30 -
> 7*x^202*y^3*z^11 - 4*x^179*y^3*z^13*t^16 + 156*x^1
> : 78*y^3*z^13*t^15 - x^201*t + 39*x^200 - 28*x^83*y^7*z^24*t^15 -
> 28*x^80*y^6*z^24*t^15 - 14*x^105*y^4*z^11 - 14*x^102*y^3*z^11 -
> 4*x^82*y^4*z^13*t^16 + 156*x^81*y^4*z^13*t^15 - 4*x^79*y
> : ^3*z^13*t^16 + 156*x^78*y^3*z^13*t^15 - 2*x^104*y*t + 78*x^103*y -
> 2*x^101*t + 78*x^100 - 7*x^8*y^5*z^11 - 14*x^5*y^4*z^11 - 7*x^2*y^3*z^11 -
> x^7*y^2*t + 39*x^6*y^2 - 2*x^4*y*t + 78*x^
> : 3*y - x*t + 39
>
> sage: fricas(g).gcd(fricas(f)).sage()
> 2*z^33*y^6*x^1078*t^15 + z^20*y^3*x^1100 + z^20*y^4*x^1003 +
> z^20*y^3*x^1000 - 14*z^24*y^6*x^80*t^15 - 7*z^11*y^3*x^102 -
> 2*z^13*y^3*x^79*t^16 + 78*z^13*y^3*x^78*t^15 - x^101*t + 39*x^100 -
> 7*z^11*y^4*x^5 - 7*z^11*y^3*x^2 - y*x^4*t + 39*y*x^3 - x*t + 39
>
> sage: timeit("fricas(g).gcd(fricas(f)).sage()")
> 5 loops, best of 3: 329 ms per loop
>
> (and this includes a very stupid way of communication)
>
> Martin
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
FriCAS does this in no time:
sage: R. = PolynomialRing(QQ)
sage: f = z^40*y^6*x^2100 + 2*t^15*z^53*y^9*x^2078 + z^40*y^7*x^2003 +
z^40*y^6*x^2000 - 14*z^31*y^6*x^1102 - 2*t*z^20*y^3*x^1101 +
78*z^20*y^3*x^1100 - 28*t^15*z^44*y^9*x^1080 - 4*t^16*z^33
: *y^6*x^1079 + 156*t^15*z^33*y^6*x^1078 - 14*z^31*y^7*x^1005 -
2*t*z^20*y^4*x^1004 + 78*z^20*y^4*x^1003 - 14*z^31*y^6*x^1002 -
2*t*z^20*y^3*x^1001 + 78*z^20*y^3*x^1000 + 49*z^22*y^6*x^1
: 04 + 14*t*z^11*y^3*x^103 + (-546*z^11*y^3 + t^2)*x^102 - 78*t*x^101 +
1521*x^100 + 98*t^15*z^35*y^9*x^82 + 28*t^16*z^24*y^6*x^81 +
(-1092*t^15*z^24*y^6 + 2*t^17*z^13*y^3)*x^80 - 156*t^
: 16*z^13*y^3*x^79 + 3042*t^15*z^13*y^3*x^78 + 49*z^22*y^7*x^7 +
14*t*z^11*y^4*x^6 + (-546*z^11*y^4 + t^2*y)*x^5 + (49*z^22*y^6 -
78*t*y)*x^4 + (14*t*z^11*y^3 + 1521*y)*x^3 + (-546*z^11*
: y^3 + t^2)*x^2 - 78*t*x + 1521
sage: g = 4*x^1156*y^9*z^46*t^30 + 4*x^1178*y^6*z^33*t^15 + x^1200*y^3*z^20
+ 4*x^1081*y^7*z^33*t^15 + 4*x^1078*y^6*z^33*t^15 + 2*x^1103*y^4*z^20 +
2*x^1100*y^3*z^20 + x^1006*y^5*z^20 + 2*x^
: 1003*y^4*z^20 + x^1000*y^3*z^20 - 28*x^158*y^9*z^37*t^30 -
28*x^180*y^6*z^24*t^15 - 4*x^157*y^6*z^26*t^31 + 156*x^156*y^6*z^26*t^30 -
7*x^202*y^3*z^11 - 4*x^179*y^3*z^13*t^16 + 156*x^1
: 78*y^3*z^13*t^15 - x^201*t + 39*x^200 - 28*x^83*y^7*z^24*t^15 -
28*x^80*y^6*z^24*t^15 - 14*x^105*y^4*z^11 - 14*x^102*y^3*z^11 -
4*x^82*y^4*z^13*t^16 + 156*x^81*y^4*z^13*t^15 - 4*x^79*y
: ^3*z^13*t^16 + 156*x^78*y^3*z^13*t^15 - 2*x^104*y*t + 78*x^103*y -
2*x^101*t + 78*x^100 - 7*x^8*y^5*z^11 - 14*x^5*y^4*z^11 - 7*x^2*y^3*z^11 -
x^7*y^2*t + 39*x^6*y^2 - 2*x^4*y*t + 78*x^
: 3*y - x*t + 39
sage: fricas(g).gcd(fricas(f)).sage()
2*z^33*y^6*x^1078*t^15 + z^20*y^3*x^1100 + z^20*y^4*x^1003 +
z^20*y^3*x^1000 - 14*z^24*y^6*x^80*t^15 - 7*z^11*y^3*x^102 -
2*z^13*y^3*x^79*t^16 + 78*z^13*y^3*x^78*t^15 - x^101*t + 39*x^100 -
7*z^11*y^4*x^5 - 7*z^11*y^3*x^2 - y*x^4*t + 39*y*x^3 - x*t + 39
sage: timeit("fricas(g).gcd(fricas(f)).sage()")
5 loops, best of 3: 329 ms per loop
(and this includes a very stupid way of communication)
Martin
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
I tried the gcd of the 2 polynomials from Bill Hart, I get 2*z^33*y^6*x^1078*t^15-14*z^ 24*y^6*x^80*t^15+z^20*y^4*x^1003+z^20*y^3*x^1100+z^20*y^3*x^1000-2*z^13*y^3*x^79*t^16+78*z^13*y^3*x^78*t^15-7*z^11*y^4*x^5-7*z^11*y^3*x^102-7*z^11*y^3*x^2-y*x^4*t+39*y*x^3-x^101*t+39*x^100-x*t+39 after 20s using the modgcd command of giac (I'll have to check the heuristics in my gcd code because gcd was trying psrgcd...) Back to the multivariate factorization problem: I have I think good dense multivariate factorization in giac (comparable to the current versions of Maple, I did not check with singular). But I believe that this problem is really a sparse multivariate factorization problem, because if you try to do Hensel lift you must translate the polynomials otherwise the factors you get are not coprime and you can not lift. But translating will densify the polynomial a lot. And the evidence is that it requires more advanced sparse algorithms than the current implementation of giac (and singular). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
I tried the gcd of the 2 polynomials from Bill Hart, I get 2*z^33*y^6*x^1078*t^15-14*z^24*y^6*x^80*t^15+z^20*y^4*x^1003+z^20*y^3*x^1100+z^20*y^3*x^1000-2*z^13*y^3*x^79*t^16+78*z^13*y^3*x^78*t^15-7*z^11*y^4*x^5-7*z^11*y^3*x^102-7*z^11*y^3*x^2-y*x^4*t+39*y*x^3-x^101*t+39*x^100-x*t+39 after 20s using the modgcd command of giac (I'll have to check the heuristics in my gcd code because gcd was trying psrgcd...) Back to the multivariate factorization problem: I have I think good dense multivariate factorization in giac (comparable to the current versions of Maple, I did not check with singular). But I believe that this problem is really a sparse multivariate factorization problem, because if you try to do Hensel lift you must translate the polynomials otherwise the factors you get are not coprime and you can not lift. But translating will densify the polynomial a lot. And it requires more advanced algorithms than the current implementation of giac (and singular). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
What are P and Q here? The polynomials to be factored? Magma takes no appreciable time at all to factor these. It also finds the factors of their product in less than 3s with 32mb memory usage. Bill. On Sunday, 30 October 2016 19:21:24 UTC+1, parisse wrote: > > Unless I'm mistaken, the polynomials are at the end. > I guess that the heuristics used by Singular for sparse multivariate > factorization did not succeed for this polynomial (this pair is slightly > more complicated than the previous pairs), and reverted to dense > factorization (probably Hensel lift algorithm), which requires much more > ressources (I have checked with giac and aborted after half an hour and > more than 8G of RAM required). > > P:=373248*a^25*b^9*c^25*d^21*E^21 + > 1866240*a^20*b^9*c^25*d^24*E^21 + > 373248*a^20*b^4*c^25*d^22*E^21 + > 124416*a^20*b^4*c^28*d^21*E^18 + > 37324800*a^16*b^4*c^25*d^21*E^20 + > 186624000*a^16*b^4*c^26*d^21*E^18 + > 18662400*a^13*b^6*c^25*d^21*E^17 + 1244160*a^13*b^5*c^25*d^21*E^12 > + 311040*a^13*b^7*c^23*d^16*E^12 + 1244160*a^13*b^4*c^25*d^16*E^13 > + 311040*a^16*b^4*c^20*d^16*E^12 + 62208*a^13*b*c^21*d^16*E^12 + > 23328*a^13*b*c^20*d^17*E^8 + 7776*a^13*b*c^15*d^18*E^8 + > 2592*a^13*b*c^15*d^14*E^10 + 2592*a^13*b^4*c^15*d^10*E^8 + > 1728*a^8*b*c^15*d^14*E^8 + 324*a^8*b^4*c^15*d^6*E^8 + > 216000*a^4*b^3*c^15*d^6*E^8 + 216000*a^4*b*c^10*d^9*E^8 + > 86400*a^4*b*c^10*d^8*E^7 + 32400*a^7*b*c^10*d^3*E^7 + > 2700*a^4*b^4*c^10*d^3*E^3 + 675*a^6*b*c^7*d^3*E^3 + 1125*a^5*b*c^2*d^3*E^3 > + 135*b^5*c^2*d^3*E^3 + 27*c^2*d^6*E^3 + 12*c^7 + 9*c^3*d^3 + a^2; > > Q:=33177600*a^7*b^16*c^6*d^33*E^36 + > 8294400*a^7*b^16*c^6*d^33*E^35 + > 10368000*a^7*b^16*c^6*d^33*E^31 + > 2073600*a^7*b^15*c^8*d^33*E^29 + > 3110400*a^7*b^15*c^6*d^33*E^29 + > 622080*a^2*b^15*c^6*d^33*E^32 + > 311040*a^2*b^15*c^6*d^33*E^26 + > 51840*a^2*b^19*c^6*d^33*E^20 + 25920*a^2*b^14*c^6*d^37*E^20 > + 6480*a^2*b^14*c^10*d^31*E^20 + > 1728*a^7*b^14*c^2*d^29*E^20 + 6480*a^2*b^14*c^2*d^32*E^20 + > 3456000*a^6*b^12*c^2*d^29*E^20 + 1152000*a^2*b^14*d^29*E^20 + > 72*a^6*b^9*d^29*E^20 + 144000*a*b^9*d^34*E^20 + > 28800*a*b^9*c^3*d^29*E^18 + 23040*a*b^9*d^31*E^18 + > 8640*a*b^9*c^5*d^26*E^17 + 1728*a*b^9*c^4*d^23*E^17 + > 2304*a*b^9*d^18*E^21 + 576*b^9*d^22*E^17 + 1152000*b^14*d^16*E^17 + > 230400*b^12*d^16*E^17 + 138240*b^8*d^21*E^12 + 115200*b^4*d^19*E^12 + > 34560*b^4*d^13*E^14 + 11520*b^6*d^13*E^8 + 2304*b^4*c*d^11*E^8 + > 288*b^4*c^2*d^11*E^3 + 72*b^7*d^8*E^3 + 288*c^2*d^8*E^3 + 18*d^8*E^3 + > 9*b*d^7 + 3*c^5 + 6*b^2*d^3; > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Multivariate polynomial factoring and bug(?)
On Sun, 30 Oct 2016, parisse wrote: I guess that the heuristics used by Singular for sparse multivariate factorization did not succeed for this polynomial (this pair is slightly more complicated than the previous pairs), and reverted to dense factorization (probably Hensel lift algorithm), which requires much more ressources (I have checked with giac and aborted after half an hour and more than 8G of RAM required). OK and thanks! This explains clearly why this happens. -- Jori Mäntysalo
[sage-devel] Re: Multivariate polynomial factoring and bug(?)
Unless I'm mistaken, the polynomials are at the end. I guess that the heuristics used by Singular for sparse multivariate factorization did not succeed for this polynomial (this pair is slightly more complicated than the previous pairs), and reverted to dense factorization (probably Hensel lift algorithm), which requires much more ressources (I have checked with giac and aborted after half an hour and more than 8G of RAM required). P:=373248*a^25*b^9*c^25*d^21*E^21 + 1866240*a^20*b^9*c^25*d^24*E^21 + 373248*a^20*b^4*c^25*d^22*E^21 + 124416*a^20*b^4*c^28*d^21*E^18 + 37324800*a^16*b^4*c^25*d^21*E^20 + 186624000*a^16*b^4*c^26*d^21*E^18 + 18662400*a^13*b^6*c^25*d^21*E^17 + 1244160*a^13*b^5*c^25*d^21*E^12 + 311040*a^13*b^7*c^23*d^16*E^12 + 1244160*a^13*b^4*c^25*d^16*E^13 + 311040*a^16*b^4*c^20*d^16*E^12 + 62208*a^13*b*c^21*d^16*E^12 + 23328*a^13*b*c^20*d^17*E^8 + 7776*a^13*b*c^15*d^18*E^8 + 2592*a^13*b*c^15*d^14*E^10 + 2592*a^13*b^4*c^15*d^10*E^8 + 1728*a^8*b*c^15*d^14*E^8 + 324*a^8*b^4*c^15*d^6*E^8 + 216000*a^4*b^3*c^15*d^6*E^8 + 216000*a^4*b*c^10*d^9*E^8 + 86400*a^4*b*c^10*d^8*E^7 + 32400*a^7*b*c^10*d^3*E^7 + 2700*a^4*b^4*c^10*d^3*E^3 + 675*a^6*b*c^7*d^3*E^3 + 1125*a^5*b*c^2*d^3*E^3 + 135*b^5*c^2*d^3*E^3 + 27*c^2*d^6*E^3 + 12*c^7 + 9*c^3*d^3 + a^2; Q:=33177600*a^7*b^16*c^6*d^33*E^36 + 8294400*a^7*b^16*c^6*d^33*E^35 + 10368000*a^7*b^16*c^6*d^33*E^31 + 2073600*a^7*b^15*c^8*d^33*E^29 + 3110400*a^7*b^15*c^6*d^33*E^29 + 622080*a^2*b^15*c^6*d^33*E^32 + 311040*a^2*b^15*c^6*d^33*E^26 + 51840*a^2*b^19*c^6*d^33*E^20 + 25920*a^2*b^14*c^6*d^37*E^20 + 6480*a^2*b^14*c^10*d^31*E^20 + 1728*a^7*b^14*c^2*d^29*E^20 + 6480*a^2*b^14*c^2*d^32*E^20 + 3456000*a^6*b^12*c^2*d^29*E^20 + 1152000*a^2*b^14*d^29*E^20 + 72*a^6*b^9*d^29*E^20 + 144000*a*b^9*d^34*E^20 + 28800*a*b^9*c^3*d^29*E^18 + 23040*a*b^9*d^31*E^18 + 8640*a*b^9*c^5*d^26*E^17 + 1728*a*b^9*c^4*d^23*E^17 + 2304*a*b^9*d^18*E^21 + 576*b^9*d^22*E^17 + 1152000*b^14*d^16*E^17 + 230400*b^12*d^16*E^17 + 138240*b^8*d^21*E^12 + 115200*b^4*d^19*E^12 + 34560*b^4*d^13*E^14 + 11520*b^6*d^13*E^8 + 2304*b^4*c*d^11*E^8 + 288*b^4*c^2*d^11*E^3 + 72*b^7*d^8*E^3 + 288*c^2*d^8*E^3 + 18*d^8*E^3 + 9*b*d^7 + 3*c^5 + 6*b^2*d^3; -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
