Sage: Ticket #9051: Fast function field arithmetic
https://trac.sagemath.org/ticket/9051
<p>
Followup to <a class="closed ticket" href="https://trac.sagemath.org/ticket/7585" title="defect: Fast function field arithmetic (closed: duplicate)">#7585</a>, which also did many, many other things.
</p>
<p>
Wrapping flint directly is much faster than the current implementation of <code>Frac(GF(p)['t'])</code>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9051
Trac 1.1.6robertwbWed, 26 May 2010 00:34:28 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>9051-FpT_1.patch</em>
</li>
</ul>
TicketrobertwbThu, 27 May 2010 07:29:28 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>9051-FpT_2.patch</em>
</li>
</ul>
TicketrobertwbThu, 27 May 2010 07:29:39 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>9051-FpT_3.patch</em>
</li>
</ul>
TicketrobertwbThu, 27 May 2010 07:30:02 GMTstatus changed
https://trac.sagemath.org/ticket/9051#comment:1
https://trac.sagemath.org/ticket/9051#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Apply all three patches in order.
</p>
<p>
Positive review to <code>9051-FpT_2.patch</code> (the third was somewhat a rebasing, referee, and fixing some stuff).
</p>
TicketrobertwbThu, 27 May 2010 07:33:50 GMTdescription changed
https://trac.sagemath.org/ticket/9051#comment:2
https://trac.sagemath.org/ticket/9051#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9051?action=diff&version=2">diff</a>)
</li>
</ul>
TicketwasFri, 28 May 2010 22:58:31 GMT
https://trac.sagemath.org/ticket/9051#comment:3
https://trac.sagemath.org/ticket/9051#comment:3
<p>
Note: 9051-FpT_2.patch is by David Roe.
</p>
TicketrobertwbSun, 30 May 2010 09:35:16 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>9051-FpT_4.patch</em>
</li>
</ul>
TicketwasThu, 08 Jul 2010 11:58:21 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>trac_9051-flattened_and_rebased.patch</em>
</li>
</ul>
<p>
flattened parts1-4 and rebased against sage-4.4.4
</p>
TicketwasThu, 08 Jul 2010 12:05:56 GMTstatus changed
https://trac.sagemath.org/ticket/9051#comment:4
https://trac.sagemath.org/ticket/9051#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I took sage-4.4.4 and applied trac_9051-flattened_and_rebased.patch. Doctesting just rings/ fails very seriously after applying this patch:
</p>
<pre class="wiki">
sage -t devel/sage/sage/rings/
The following tests failed:
sage -t devel/sage-main/sage/rings/residue_field.pyx # 16 doctests failed
sage -t devel/sage-main/sage/rings/number_field/order.py # 3 doctests failed
sage -t devel/sage-main/sage/rings/number_field/number_field_element_quadratic.pyx # 2 doctests failed
sage -t devel/sage-main/sage/rings/arith.py # 1 doctests failed
sage -t devel/sage-main/sage/rings/ring.pyx # 5 doctests failed
sage -t devel/sage-main/sage/rings/polynomial/multi_polynomial.pyx # 2 doctests failed
sage -t devel/sage-main/sage/rings/polynomial/multi_polynomial_libsingular.pyx # 7 doctests failed
sage -t devel/sage-main/sage/rings/integer_ring.pyx # 5 doctests failed
sage -t devel/sage-main/sage/rings/number_field/galois_group.py # 8 doctests failed
sage -t devel/sage-main/sage/rings/polynomial/polynomial_element.pyx # 7 doctests failed
sage -t devel/sage-main/sage/rings/misc.py # 1 doctests failed
sage -t devel/sage-main/sage/rings/number_field/number_field_base.pyx # 13 doctests failed
sage -t devel/sage-main/sage/rings/qqbar.py # 4 doctests failed
sage -t devel/sage-main/sage/rings/number_field/number_field_rel.py # 10 doctests failed
sage -t devel/sage-main/sage/rings/polynomial/multi_polynomial_ideal.py # 15 doctests failed
sage -t devel/sage-main/sage/rings/polynomial/polynomial_singular_interface.py # 1 doctests failed
sage -t devel/sage-main/sage/rings/number_field/number_field_element.pyx # 13 doctests failed
----------------------------------------------------------------------
Timings have been updated.
Total time for all tests: 64.0 seconds
</pre>
TicketroedFri, 09 Jul 2010 11:59:27 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>trac_9051_polycall_fixes.patch</em>
</li>
</ul>
<p>
Fixes the broken doctests
</p>
TicketroedFri, 09 Jul 2010 11:59:46 GMTstatus changed
https://trac.sagemath.org/ticket/9051#comment:5
https://trac.sagemath.org/ticket/9051#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketroedFri, 09 Jul 2010 12:00:29 GMT
https://trac.sagemath.org/ticket/9051#comment:6
https://trac.sagemath.org/ticket/9051#comment:6
<p>
The most recent patch should be applied on top of the flattened and rebased patche.
</p>
TicketwasFri, 09 Jul 2010 12:06:22 GMT
https://trac.sagemath.org/ticket/9051#comment:7
https://trac.sagemath.org/ticket/9051#comment:7
<p>
I'm running tests with both patches:
</p>
<blockquote>
<p>
<a class="ext-link" href="http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051.out"><span class="icon"></span>http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051.out</a>
</p>
</blockquote>
TicketwasFri, 09 Jul 2010 12:08:30 GMTstatus changed
https://trac.sagemath.org/ticket/9051#comment:8
https://trac.sagemath.org/ticket/9051#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Stuff fails. See above link.
</p>
TicketwasFri, 09 Jul 2010 12:18:34 GMT
https://trac.sagemath.org/ticket/9051#comment:9
https://trac.sagemath.org/ticket/9051#comment:9
<pre class="wiki">----------------------------------------------------------------------
The following tests failed:
sage -t devel/sage-main/sage/modular/abvar/homspace.py # 20 doctests failed
sage -t devel/sage-main/sage/modular/abvar/abvar.py # 32 doctests failed
sage -t devel/sage-main/sage/modular/modsym/space.py # 6 doctests failed
sage -t devel/sage-main/sage/modular/modsym/ambient.py # 2 doctests failed
sage -t devel/sage-main/sage/modular/modform/element.py # 2 doctests failed
sage -t devel/sage-main/sage/functions/piecewise.py # 6 doctests failed
sage -t devel/sage-main/sage/graphs/graph.py # 1 doctests failed
sage -t devel/sage-main/sage/modular/abvar/morphism.py # 3 doctests failed
sage -t devel/sage-main/sage/modular/abvar/abvar_ambient_jacobian.py # 3 doctests failed
sage -t devel/sage-main/sage/modular/abvar/homology.py # 19 doctests failed
sage -t devel/sage-main/sage/modular/abvar/abvar_newform.py # 12 doctests failed
sage -t devel/sage-main/sage/tests/startup.py # 1 doctests failed
sage -t devel/sage-main/sage/numerical/optimize.py # 2 doctests failed
sage -t devel/sage-main/sage/modular/abvar/constructor.py # 2 doctests failed
sage -t devel/sage-main/sage/schemes/hyperelliptic_curves/hypellfrob.pyx # 1 doctests failed
----------------------------------------------------------------------
Timings have been updated.
Total time for all tests: 355.5 seconds
</pre>
TicketroedFri, 09 Jul 2010 12:29:27 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>trac_9051_fixes2.patch</em>
</li>
</ul>
<p>
Fixes more doctests
</p>
TicketroedFri, 09 Jul 2010 12:30:31 GMTstatus changed
https://trac.sagemath.org/ticket/9051#comment:10
https://trac.sagemath.org/ticket/9051#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Thanks; I was going to run tests while sleeping, but this worked better. I think I have them all now, but I haven't run tests after the fix: I'm doing it on my laptop, so it'll take a while.
</p>
TicketwasFri, 09 Jul 2010 14:34:03 GMT
https://trac.sagemath.org/ticket/9051#comment:11
https://trac.sagemath.org/ticket/9051#comment:11
<p>
Here it goes again:
</p>
<blockquote>
<p>
<a class="ext-link" href="http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051-try2.out"><span class="icon"></span>http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051-try2.out</a>
</p>
</blockquote>
TicketroedFri, 09 Jul 2010 22:02:23 GMT
https://trac.sagemath.org/ticket/9051#comment:12
https://trac.sagemath.org/ticket/9051#comment:12
<p>
Looks like all tests pass; do you want to review it?
</p>
TicketwasSat, 10 Jul 2010 05:11:07 GMT
https://trac.sagemath.org/ticket/9051#comment:13
https://trac.sagemath.org/ticket/9051#comment:13
<p>
Wow, that's excellent that everything finally passes. Yes, I hope to have time to review it soon.
</p>
TicketwasThu, 15 Jul 2010 15:26:58 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>trac_9051-everything_flattened.patch</em>
</li>
</ul>
TicketwasThu, 15 Jul 2010 15:46:47 GMT
https://trac.sagemath.org/ticket/9051#comment:14
https://trac.sagemath.org/ticket/9051#comment:14
<p>
I did a benchmark on sage.math, comparing this code to Magma:
</p>
<p>
SAGE with your patch:
</p>
<pre class="wiki">sage: R.<T> = GF(71)[]; K.<T> = FractionField(R); a=(T^3+T-1)*(T^2-2); b=(3*T^5-T+7)*(T^2-2)
sage: timeit('a/b+b/a')
625 loops, best of 3: 26.3 µs per loop
sage: time v=[a/b+b/a for i in range(10^5)]
CPU times: user 2.94 s, sys: 0.02 s, total: 2.96 s
Wall time: 2.96 s
sage: time v=[a*b for i in range(10^5)]
CPU times: user 0.54 s, sys: 0.02 s, total: 0.56 s
Wall time: 0.56 s
sage: time v=[(1/a)*(1/b) for i in range(10^5)]
CPU times: user 1.80 s, sys: 0.00 s, total: 1.80 s
Wall time: 1.80 s
</pre><p>
Before the patch, the same benchmark is massively slower, so this patch is a very big improvement:
</p>
<pre class="wiki">sage: sage: R.<T> = GF(71)[]; K.<T> = FractionField(R); a=(T^3+T-1)*(T^2-2); b=(3*T^5-T+7)*(T^2-2)
sage: sage: timeit('a/b+b/a')
625 loops, best of 3: 776 µs per loop
</pre><p>
In Magma:
</p>
<pre class="wiki">sage: R.<T> = GF(71)[]; K.<T> = FractionField(R); a=(T^3+T-1)*(T^2-2); b=(3*T^5-T+7)*(T^2-2)
sage: aa=magma(a); bb=magma(b)
sage: magma.eval('a:=%s;b:=%s;'%(aa.name(),bb.name()))
sage: magma.eval('time v := [a/b+b/a : i in [1..10^5]];')
'Time: 0.800'
sage: magma.eval('time v := [a*b : i in [1..10^5]];')
'Time: 0.320'
sage: magma.eval('time v := [(1/a) * (1/b) : i in [1..10^5]];')
'Time: 0.830'
</pre><p>
Something surprising is that working in your rational function field is much faster than working with polynomials!
</p>
<pre class="wiki">sage: R.<T> = GF(71)[]; a=(T^3+T-1)*(T^2-2); b=(3*T^5-T+7)*(T^2-2)
sage: time v=[a*b for i in range(10^5)]
CPU times: user 2.02 s, sys: 0.00 s, total: 2.02 s
Wall time: 2.02 s
</pre>
TicketwasThu, 15 Jul 2010 15:49:31 GMT
https://trac.sagemath.org/ticket/9051#comment:15
https://trac.sagemath.org/ticket/9051#comment:15
<p>
Before the patch... 79 seconds instead of the new 2.9 seconds:
</p>
<pre class="wiki">
sage: sage: time v=[a/b+b/a for i in range(10^5)]
CPU times: user 78.91 s, sys: 0.15 s, total: 79.06 s
Wall time: 79.05 s
</pre>
TicketwasThu, 15 Jul 2010 17:34:56 GMTattachment set
https://trac.sagemath.org/ticket/9051
https://trac.sagemath.org/ticket/9051
<ul>
<li><strong>attachment</strong>
set to <em>trac_9051-referee-1.patch</em>
</li>
</ul>
<p>
apply this after the "everything flattened" patch directly above.
</p>
TicketwasThu, 15 Jul 2010 17:36:28 GMTstatus changed
https://trac.sagemath.org/ticket/9051#comment:16
https://trac.sagemath.org/ticket/9051#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketrobertwbFri, 16 Jul 2010 02:10:08 GMT
https://trac.sagemath.org/ticket/9051#comment:17
https://trac.sagemath.org/ticket/9051#comment:17
<p>
Reviewer patch looks good to me. My only comment is that it would be nice to have a faster not-equals comparison, but that's not worth holding this up.
</p>
TicketminzSat, 17 Jul 2010 19:37:42 GMTcc set
https://trac.sagemath.org/ticket/9051#comment:18
https://trac.sagemath.org/ticket/9051#comment:18
<ul>
<li><strong>cc</strong>
<em>minz</em> added
</li>
</ul>
TicketmpatelTue, 20 Jul 2010 09:28:45 GMTstatus changed; reviewer, resolution, merged, author set
https://trac.sagemath.org/ticket/9051#comment:19
https://trac.sagemath.org/ticket/9051#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>Robert Bradshaw, William Stein</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.5.2.alpha0</em>
</li>
<li><strong>author</strong>
set to <em>Robert Bradshaw, David Roe, William Stein</em>
</li>
</ul>
<p>
I've merged only
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9051/trac_9051-everything_flattened.patch" title="Attachment 'trac_9051-everything_flattened.patch' in Ticket #9051">trac_9051-everything_flattened.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9051/trac_9051-everything_flattened.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9051/trac_9051-referee-1.patch" title="Attachment 'trac_9051-referee-1.patch' in Ticket #9051">trac_9051-referee-1.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9051/trac_9051-referee-1.patch" title="Download"></a>
</li></ul><p>
in 4.5.2.alpha0. Please correct the Author(s) and Reviewer(s) fields, if I'm wrong.
</p>
TicketjdemeyerFri, 18 Jan 2013 08:10:25 GMT
https://trac.sagemath.org/ticket/9051#comment:20
https://trac.sagemath.org/ticket/9051#comment:20
<p>
I assume that it's a mistake that the function
</p>
<pre class="wiki">def fraction_field(self):
</pre><p>
was added <em>twice</em> in <code>sage/rings/polynomial/polynomial_ring.py</code>
</p>
TicketjdemeyerSat, 19 Jan 2013 11:22:23 GMT
https://trac.sagemath.org/ticket/9051#comment:21
https://trac.sagemath.org/ticket/9051#comment:21
<p>
Please review <a class="closed ticket" href="https://trac.sagemath.org/ticket/13971" title="defect: Remove duplicate fraction_field() method (closed: fixed)">#13971</a> to correct this duplicate method.
</p>
Ticket