Ask Your Question
0

Is applying a ring homomorphism faster than symbolic substitution?

asked 2011-02-05 04:41:57 -0500

niles gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2011-02-06 07:32:52 -0500

Simon King gravatar image

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.

edit flag offensive delete link more

Comments

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?)

niles gravatar imageniles ( 2011-02-06 09:25:26 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2011-02-05 04:41:57 -0500

Seen: 401 times

Last updated: Feb 06 '11