Revision history [back]

I looked into the issue. You correctly identified the place where it hangs. Actually, in the line R = d*R - c*B.shift(diffdeg), the long time is taken by the two multiplications.

The problem is that d and the coefficients of R are very large rational fractions: I stopped the computation at some point when it hanged, and stored the values of R and d there: The degrees in each variable is around 50 for both d and the coefficients of R, and their number of terms is around 2500 each. Already computing the product of d with one coefficient of R takes around 2s on the machine I use.

Looking more into details, the problem is SageMath's multiplication of bivariate polynomials which is quite slow. To sum up: I think there is (unfortunately) no bug, simply the objects are too large for the current capabilities of SageMath.

As a further comment, the value of d and the coefficients of R are all polynomials in $\mathbb Z[x,y]$ (they are rational fractions, but with denominator $1$). Putting them in the ring A (that represents $\mathbb Z[x,y]$ in your example) does not change anything on the computation time. On the other hand, using as a base ring $\mathbb Z[y][x]$ improves the performance of the multiplication (the computation is approx. 20 times faster). One solution may then be to modify pseudo_quo_rem for your needs, using a recursive univariate polynomial ring (U = ZZ['y']['x']) as base ring instead of a multivariate polynomial ring.

P.S.: Though this website is devoted to SageMath, I think that the (free, of course) Computer Algebra System Nemo, written is Julia, is particularly efficient for such kind of computations. You may have a look to it.