ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 06 Feb 2011 16:25:26 +0100Is applying a ring homomorphism faster than symbolic substitution?https://ask.sagemath.org/question/7921/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?
Sat, 05 Feb 2011 11:41:57 +0100https://ask.sagemath.org/question/7921/is-applying-a-ring-homomorphism-faster-than-symbolic-substitution/Answer by Simon King for <p>I'm working on a project where I need to do composition of polynomials; something like</p>
<pre><code>P(Q1 + Q2)
</code></pre>
<p>where <code>P</code>, <code>Q1</code>, and <code>Q2</code> 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 <code>.subs()</code> 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 <code>P</code> to <code>Q1 + Q2</code>, and then apply the homomorphism to <code>P</code>.</p>
<p>So my question: will this be worth my while, or are the ring homomorphism methods too slow?</p>
https://ask.sagemath.org/question/7921/is-applying-a-ring-homomorphism-faster-than-symbolic-substitution/?answer=12067#post-id-12067Hi 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.Sun, 06 Feb 2011 14:32:52 +0100https://ask.sagemath.org/question/7921/is-applying-a-ring-homomorphism-faster-than-symbolic-substitution/?answer=12067#post-id-12067Comment by niles for <p>Hi Niles!</p>
<p>Let's try.</p>
<p>Substitution:</p>
<pre><code>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
</code></pre>
<p>Homomorphism:</p>
<pre><code>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
</code></pre>
<p>So, substitution is considerably faster than a homomorphism. I find that's a shame! If other people agree, we should open a ticket.</p>
<p>By the way: I tried the same using a multivariate ring with one variable. The degree 50 example didn't even finish.</p>
https://ask.sagemath.org/question/7921/is-applying-a-ring-homomorphism-faster-than-symbolic-substitution/?comment=22188#post-id-22188Thanks 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?)Sun, 06 Feb 2011 16:25:26 +0100https://ask.sagemath.org/question/7921/is-applying-a-ring-homomorphism-faster-than-symbolic-substitution/?comment=22188#post-id-22188