Opened 7 years ago

Closed 7 years ago

Last modified 5 years ago

#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 robertwb)

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)

9051-FpT_1.patch (25.9 KB) - added by robertwb 7 years ago.
9051-FpT_2.patch (66.6 KB) - added by robertwb 7 years ago.
9051-FpT_3.patch (11.7 KB) - added by robertwb 7 years ago.
9051-FpT_4.patch (12.7 KB) - added by robertwb 7 years ago.
trac_9051-flattened_and_rebased.patch (83.6 KB) - added by was 7 years ago.
flattened parts1-4 and rebased against sage-4.4.4
trac_9051_polycall_fixes.patch (1.6 KB) - added by roed 7 years ago.
Fixes the broken doctests
trac_9051_fixes2.patch (1.6 KB) - added by roed 7 years ago.
Fixes more doctests
trac_9051-everything_flattened.patch (84.4 KB) - added by was 7 years ago.
trac_9051-referee-1.patch (4.6 KB) - added by was 7 years ago.
apply this after the "everything flattened" patch directly above.

Download all attachments as: .zip

Change History (30)

Changed 7 years ago by robertwb

Changed 7 years ago by robertwb

Changed 7 years ago by robertwb

comment:1 Changed 7 years ago by robertwb

  • Status changed from new to needs_review

Apply all three patches in order.

Positive review to 9051-FpT_2.patch (the third was somewhat a rebasing, referee, and fixing some stuff).

comment:2 Changed 7 years ago by robertwb

  • Description modified (diff)

comment:3 Changed 7 years ago by was

Note: 9051-FpT_2.patch is by David Roe.

Changed 7 years ago by robertwb

Changed 7 years ago by was

flattened parts1-4 and rebased against sage-4.4.4

comment:4 Changed 7 years ago by was

  • 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

Changed 7 years ago by roed

Fixes the broken doctests

comment:5 Changed 7 years ago by roed

  • Status changed from needs_work to needs_review

comment:6 Changed 7 years ago by roed

The most recent patch should be applied on top of the flattened and rebased patche.

comment:8 Changed 7 years ago by was

  • Status changed from needs_review to needs_work

Stuff fails. See above link.

comment:9 Changed 7 years ago by was

----------------------------------------------------------------------

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
                                                            

Changed 7 years ago by roed

Fixes more doctests

comment:10 Changed 7 years ago by roed

  • 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:12 Changed 7 years ago by roed

Looks like all tests pass; do you want to review it?

comment:13 Changed 7 years ago by was

Wow, that's excellent that everything finally passes. Yes, I hope to have time to review it soon.

Changed 7 years ago by was

comment:14 Changed 7 years ago by was

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 7 years ago by was

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

Changed 7 years ago by was

apply this after the "everything flattened" patch directly above.

comment:16 Changed 7 years ago by was

  • Status changed from needs_review to positive_review

comment:17 Changed 7 years ago by robertwb

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 7 years ago by minz

  • Cc minz added

comment:19 Changed 7 years ago by mpatel

  • Authors set to Robert Bradshaw, David Roe, William Stein
  • 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 5 years ago by jdemeyer

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 5 years ago by jdemeyer

Please review #13971 to correct this duplicate method.

Note: See TracTickets for help on using tickets.