# Is applying a ring homomorphism faster than symbolic substitution?

I'm working on a project where I need to do composition of polynomials; something like

P(Q1 + Q2)


where P, Q1, and Q2 are univariate polynomials with several hundred terms, and large integer coefficients (on the order of 10^10 or so). I've been doing this with the .subs() method which, I think, moves things to the symbolic ring and does the substitutions there. (I think this because when I get errors, they have to do with coercing to or from the symbolic ring.) But it occurred to me I could also define a ring homomorphism sending the variable of P to Q1 + Q2, and then apply the homomorphism to P.

So my question: will this be worth my while, or are the ring homomorphism methods too slow?

edit retag close merge delete

Sort by ยป oldest newest most voted

Hi Niles!

Let's try.

Substitution:

sage: R.<x> = QQ[]
sage: p = R.random_element(50)
sage: q = R.random_element(50)
sage: %time r=p(q)
CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s
Wall time: 0.11 s
sage: p = R.random_element(100)
sage: q = R.random_element(100)
sage: %time r=p(q)
CPU times: user 1.10 s, sys: 0.02 s, total: 1.12 s
Wall time: 1.12 s
sage: p = R.random_element(200)
sage: q = R.random_element(200)
sage: %time r=p(q)
CPU times: user 25.27 s, sys: 0.27 s, total: 25.54 s
Wall time: 25.61 s


Homomorphism:

sage: p = R.random_element(50)
sage: q = R.random_element(50)
sage: f = R.hom([q])
# Test that the result is the same
sage: p(q)==f(p)
True
sage: %time r=f(p)
CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
Wall time: 0.45 s
sage: p = R.random_element(100)
sage: q = R.random_element(100)
sage: f = R.hom([q])
sage: %time r=f(p)
CPU times: user 16.73 s, sys: 0.00 s, total: 16.74 s
Wall time: 16.79 s


So, substitution is considerably faster than a homomorphism. I find that's a shame! If other people agree, we should open a ticket.

By the way: I tried the same using a multivariate ring with one variable. The degree 50 example didn't even finish.

more

Thanks Simon :) I guess I could have done something like this myself . . . do you think there's any scenario in which ring homomorphisms beat symbolic substitution? (e.g. maybe when the coefficients are also polynomials?)

( 2011-02-06 16:25:26 +0200 )edit