#9051 closed defect (fixed)
Fast function field arithmetic
Reported by: | robertwb | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-4.5.2 |
Component: | algebra | Keywords: | |
Cc: | minz | Merged in: | sage-4.5.2.alpha0 |
Authors: | Robert Bradshaw, David Roe, William Stein | Reviewers: | Robert Bradshaw, William Stein |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Followup to #7585, which also did many, many other things.
Wrapping flint directly is much faster than the current implementation of Frac(GF(p)['t'])
Attachments (9)
Change History (30)
Changed 11 years ago by
Changed 11 years ago by
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Description modified (diff)
comment:3 Changed 11 years ago by
Note: 9051-FpT_2.patch is by David Roe.
Changed 11 years ago by
comment:4 Changed 11 years ago by
- Status changed from needs_review to needs_work
I took sage-4.4.4 and applied trac_9051-flattened_and_rebased.patch. Doctesting just rings/ fails very seriously after applying this patch:
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
comment:5 Changed 11 years ago by
- Status changed from needs_work to needs_review
comment:6 Changed 11 years ago by
The most recent patch should be applied on top of the flattened and rebased patche.
comment:7 Changed 11 years ago by
I'm running tests with both patches:
http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051.out
comment:8 Changed 11 years ago by
- Status changed from needs_review to needs_work
Stuff fails. See above link.
comment:9 Changed 11 years ago by
---------------------------------------------------------------------- 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
comment:10 Changed 11 years ago by
- Status changed from needs_work to needs_review
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.
comment:11 Changed 11 years ago by
comment:12 Changed 11 years ago by
Looks like all tests pass; do you want to review it?
comment:13 Changed 11 years ago by
Wow, that's excellent that everything finally passes. Yes, I hope to have time to review it soon.
Changed 11 years ago by
comment:14 Changed 11 years ago by
I did a benchmark on sage.math, comparing this code to Magma:
SAGE with your patch:
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
Before the patch, the same benchmark is massively slower, so this patch is a very big improvement:
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
In Magma:
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'
Something surprising is that working in your rational function field is much faster than working with polynomials!
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
comment:15 Changed 11 years ago by
Before the patch... 79 seconds instead of the new 2.9 seconds:
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
comment:16 Changed 11 years ago by
- Status changed from needs_review to positive_review
comment:17 Changed 11 years ago by
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.
comment:18 Changed 11 years ago by
- Cc minz added
comment:19 Changed 11 years ago by
- Merged in set to sage-4.5.2.alpha0
- Resolution set to fixed
- Reviewers set to Robert Bradshaw, William Stein
- Status changed from positive_review to closed
I've merged only
in 4.5.2.alpha0. Please correct the Author(s) and Reviewer(s) fields, if I'm wrong.
comment:20 Changed 9 years ago by
I assume that it's a mistake that the function
def fraction_field(self):
was added twice in sage/rings/polynomial/polynomial_ring.py
comment:21 Changed 9 years ago by
Please review #13971 to correct this duplicate method.
Apply all three patches in order.
Positive review to
9051-FpT_2.patch
(the third was somewhat a rebasing, referee, and fixing some stuff).