I think I see things slightly clearer now. One problem is, that, by design, we successively reduce to polynomial rings with fewer generators. More precisely, MPolynomial.gcd converts the input to a univariate polynomial in one of the generators, and UniqueFactorizationDomains.ParentMethods._gcd_univariate_polynomial then relies on the existence of a gcd for the new base ring.
To do this, the new base ring, i.e., the ring with one fewer generator, must be constructed, and this is rather expensive. If I understand correctly, almost all the time is spent there. This is done in `MPolynomial.polynomial` using `S = PolynomialRing(R.base_ring(), Z)` So, the questions are: 1. is there a (much) faster way to construct the univariate polynomial ring? I tried to do S = R.__class__(R.base_ring(), len(Z), [str(z) for z in Z], R.term_order()) when Z has at least two variables (because of the difference between univariate and multivariate polynomial rings) but to my surprise this was actually slower. 2. can we bypass the construction of polynomial rings entirely? On Sunday 3 November 2024 at 17:11:23 UTC+1 Martin R wrote: > Possibly the problem is that MPolynomial.gcd calls > UniqueFactorizationDomains.ParentMethods._gcd_univariate_polynomial, which > recurses on MPolynomial.gcd, but the setup done by MPolynomial.gcd is > possibly not cheap. > > On Sunday 3 November 2024 at 12:31:44 UTC+1 Martin R wrote: > >> Are the following timings to be expected? >> >> sage: R = SymmetricFunctions(QQ).h().fraction_field() >> sage: P = PolynomialRing(R, 200, "x") >> sage: e = P.gen(199); e >> x199 >> sage: %time e.gcd(e) >> CPU times: user 41.1 s, sys: 2.24 s, total: 43.4 s >> Wall time: 43.5 s >> x199 >> >> sage: R = QQ >> sage: P = PolynomialRing(R, 200, "x") >> sage: e = P.gen(199); e >> x199 >> sage: %time e.gcd(e) >> CPU times: user 41 µs, sys: 0 ns, total: 41 µs >> Wall time: 47 µs >> x199 >> >> sage: R = QQbar >> sage: P = PolynomialRing(R, 200, "x") >> sage: e = P.gen(199); e >> x199 >> sage: %time e.gcd(e) >> CPU times: user 3.02 s, sys: 183 ms, total: 3.2 s >> Wall time: 3.21 s >> x199 >> > -- 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 view this discussion visit https://groups.google.com/d/msgid/sage-devel/53c20d2a-6c4b-481d-956f-1d8069f30e0bn%40googlegroups.com.
