Fast function field arithmetic #9051

robertwb · 2010-05-26T00:27:53Z

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'])

CC: @mminzlaff

Component: algebra

Author: Robert Bradshaw, David Roe, William Stein

Reviewer: Robert Bradshaw, William Stein

Merged: sage-4.5.2.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/9051

The text was updated successfully, but these errors were encountered:

robertwb · 2010-05-27T07:29:28Z

Attachment: 9051-FpT_1.patch.gz

robertwb · 2010-05-27T07:29:39Z

Attachment: 9051-FpT_2.patch.gz

Attachment: 9051-FpT_3.patch.gz

robertwb · 2010-05-27T07:30:02Z

comment:1

Apply all three patches in order.

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

williamstein · 2010-05-28T22:58:31Z

comment:3

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

robertwb · 2010-05-30T09:35:16Z

Attachment: 9051-FpT_4.patch.gz

williamstein · 2010-07-08T11:58:21Z

flattened parts1-4 and rebased against sage-4.4.4

williamstein · 2010-07-08T12:05:56Z

comment:4

Attachment: trac_9051-flattened_and_rebased.patch.gz

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

roed314 · 2010-07-09T11:59:27Z

Fixes the broken doctests

roed314 · 2010-07-09T11:59:46Z

comment:5

Attachment: trac_9051_polycall_fixes.patch.gz

roed314 · 2010-07-09T12:00:29Z

comment:6

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

williamstein · 2010-07-09T12:06:22Z

comment:7

I'm running tests with both patches:

http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051.out

williamstein · 2010-07-09T12:08:30Z

comment:8

Stuff fails. See above link.

williamstein · 2010-07-09T12:18:34Z

comment:9

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

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

roed314 · 2010-07-09T12:29:27Z

Attachment: trac_9051_fixes2.patch.gz

Fixes more doctests

roed314 · 2010-07-09T12:30:31Z

comment:10

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.

williamstein · 2010-07-09T14:34:03Z

comment:11

Here it goes again:

http://sage.math.washington.edu/home/wstein/build/sage-4.4.4/devel/sage/9051-try2.out

roed314 · 2010-07-09T22:02:23Z

comment:12

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

williamstein · 2010-07-10T05:11:07Z

comment:13

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

williamstein · 2010-07-15T15:46:47Z

comment:14

Attachment: trac_9051-everything_flattened.patch.gz

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

williamstein · 2010-07-15T15:49:31Z

comment:15

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

williamstein · 2010-07-15T17:34:56Z

Attachment: trac_9051-referee-1.patch.gz

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

robertwb · 2010-07-16T02:10:08Z

comment:17

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.

qed777 · 2010-07-20T09:28:45Z

comment:19

I've merged only

in 4.5.2.alpha0. Please correct the Author(s) and Reviewer(s) fields, if I'm wrong.

qed777 · 2010-07-20T09:28:45Z

Merged: sage-4.5.2.alpha0

qed777 · 2010-07-20T09:28:45Z

Reviewer: Robert Bradshaw, William Stein

qed777 · 2010-07-20T09:28:45Z

Author: Robert Bradshaw, David Roe, William Stein

jdemeyer · 2013-01-18T08:10:25Z

comment:20

I assume that it's a mistake that the function

def fraction_field(self):

was added twice in sage/rings/polynomial/polynomial_ring.py

jdemeyer · 2013-01-19T11:22:23Z

comment:21

Please review #13971 to correct this duplicate method.

robertwb added this to the sage-4.5.2 milestone May 26, 2010

robertwb added c: algebra labels May 26, 2010

robertwb assigned aghitza May 26, 2010

robertwb added the s: needs review label May 27, 2010

This comment has been minimized.

Sign in to view

williamstein added s: needs work and removed s: needs review labels Jul 8, 2010

roed314 added s: needs review and removed s: needs work labels Jul 9, 2010

williamstein added s: needs work and removed s: needs review labels Jul 9, 2010

roed314 added s: needs review and removed s: needs work labels Jul 9, 2010

williamstein added s: positive review and removed s: needs review labels Jul 15, 2010

qed777 mannequin removed the s: positive review label Jul 20, 2010

qed777 mannequin closed this as completed Jul 20, 2010

williamstein mentioned this issue Feb 2, 2012

create a class for basic function_field arithmetic for Sage #9054

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fast function field arithmetic #9051

Fast function field arithmetic #9051

robertwb commented May 26, 2010

robertwb commented May 27, 2010

robertwb commented May 27, 2010

robertwb commented May 27, 2010

This comment has been minimized.

williamstein commented May 28, 2010

robertwb commented May 30, 2010

williamstein commented Jul 8, 2010

williamstein commented Jul 8, 2010

roed314 commented Jul 9, 2010

roed314 commented Jul 9, 2010

roed314 commented Jul 9, 2010

williamstein commented Jul 9, 2010

williamstein commented Jul 9, 2010

williamstein commented Jul 9, 2010

roed314 commented Jul 9, 2010

roed314 commented Jul 9, 2010

williamstein commented Jul 9, 2010

roed314 commented Jul 9, 2010

williamstein commented Jul 10, 2010

williamstein commented Jul 15, 2010

williamstein commented Jul 15, 2010

williamstein commented Jul 15, 2010

robertwb commented Jul 16, 2010

qed777 mannequin commented Jul 20, 2010

qed777 mannequin commented Jul 20, 2010

qed777 mannequin commented Jul 20, 2010

qed777 mannequin commented Jul 20, 2010

jdemeyer commented Jan 18, 2013

jdemeyer commented Jan 19, 2013

Fast function field arithmetic #9051

Fast function field arithmetic #9051

Comments

robertwb commented May 26, 2010

robertwb commented May 27, 2010

robertwb commented May 27, 2010

robertwb commented May 27, 2010

This comment has been minimized.

williamstein commented May 28, 2010

robertwb commented May 30, 2010

williamstein commented Jul 8, 2010

williamstein commented Jul 8, 2010

roed314 commented Jul 9, 2010

roed314 commented Jul 9, 2010

roed314 commented Jul 9, 2010

williamstein commented Jul 9, 2010

williamstein commented Jul 9, 2010

williamstein commented Jul 9, 2010

roed314 commented Jul 9, 2010

roed314 commented Jul 9, 2010

williamstein commented Jul 9, 2010

roed314 commented Jul 9, 2010

williamstein commented Jul 10, 2010

williamstein commented Jul 15, 2010

williamstein commented Jul 15, 2010

williamstein commented Jul 15, 2010

robertwb commented Jul 16, 2010

qed777 mannequin commented Jul 20, 2010

qed777 mannequin commented Jul 20, 2010

qed777 mannequin commented Jul 20, 2010

qed777 mannequin commented Jul 20, 2010

jdemeyer commented Jan 18, 2013

jdemeyer commented Jan 19, 2013