2023-03-18 11:09:28 +0200 | received badge | ● Famous Question (source) |
2017-06-02 17:12:39 +0200 | commented answer | Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields Also when i tried adding a dummy variable in the polynomial ring and type casting the polynomials p and q as multivariate polynomials it was computed very fast. Any reason for why it happens differently when it is a multivariate polynomial over a fraction field versus a univariate polynomial over a fraction field? |
2017-06-02 09:16:11 +0200 | received badge | ● Notable Question (source) |
2017-06-01 20:48:29 +0200 | received badge | ● Scholar (source) |
2017-06-01 20:48:25 +0200 | commented answer | Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields thank you so much for the reply. We are building some packages for sagemath and this gcd is getting called in them. Can you probably explain what you mean by the limitations of sage math - is it for example because of the limitations of singular (Since in the multiplication function it calls the gcd function in multi_polynomial_libsingular.pyx and always hangs there since the number of monomials is big) ? or is it something else in the architecture? The reason I was asking is because I was wondering if it can be ``rectified" if we spend more time on it? or would it be a complete overhaul of the code? |
2017-05-29 07:41:39 +0200 | received badge | ● Popular Question (source) |
2017-05-24 10:38:26 +0200 | commented question | Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields thank you! that will be great! |
2017-05-23 22:54:17 +0200 | commented question | Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields yes I understand that. I will edit the question with more details. |
2017-05-23 15:10:28 +0200 | asked a question | Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$. (Note: In the current version of sage it uses the regular Euclidean algorithm implemented in rings.py for computing gcd in this case. It is much slower than the subresultant algorithm (hangs for degrees >4) which is why I thought the subresultant algorithm will improve things.) Sample input: sage: A.<x,y>=ZZ[] sage: B= Frac(A) sage: C.<z> = B[] sage: p = C.random_element(6) sage: q = C.random_element(6) sage: gcd(p,q) The following function is what I copied into fraction_field.py from unique_factorisation_domain.py. def _gcd_univariate_polynomial(self, f, g): This calls the following pseudo quo remainder function in polynomial_element.pyx. It is in this function I was able to see that it hangs at R = dR - cB.shift(diffdeg). def pseudo_quo_rem(self,other): |