Opened 12 years ago

Closed 11 years ago

Last modified 11 years ago

#7585 closed defect (duplicate)

Fast function field arithmetic

Reported by: robertwb Owned by: AlexGhitza
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: algebra Keywords:
Cc: roed Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Wrapping flint directly should be much faster than the current implementation of Frac(GF(p)['t'])

Attachments (16)

7585_FpT.patch (19.4 KB) - added by robertwb 12 years ago.
7585_FpT.2.patch (25.0 KB) - added by robertwb 12 years ago.
7585_FpT-more.patch (8.1 KB) - added by robertwb 12 years ago.
apply on top of previous
7585_1_FpT-orig.patch (25.0 KB) - added by roed 12 years ago.
Rebased against 4.3.rc0
7585_2_FpT-more.patch (8.1 KB) - added by roed 12 years ago.
Rebased against 4.3.rc0
7585_3_FpT-update.patch (58.9 KB) - added by roed 12 years ago.
7585_4_sets_with_partial_maps.patch (13.8 KB) - added by roed 12 years ago.
7585_5_finite_fields_to_new_coercion.patch (34.3 KB) - added by roed 12 years ago.
7585_6_gcd.patch (8.5 KB) - added by roed 12 years ago.
7585_7_ideal.patch (20.0 KB) - added by roed 12 years ago.
7585_8_parent_init.patch (4.0 KB) - added by roed 12 years ago.
7585_9_frac_and_coerce_updates.patch (15.1 KB) - added by roed 12 years ago.
7585_10_residue_field.patch (78.5 KB) - added by roed 12 years ago.
7585_11_tate_ff.patch (51.3 KB) - added by roed 12 years ago.
7585_12_fixes.patch (75.3 KB) - added by roed 12 years ago.
7585_ALL.patch (329.6 KB) - added by roed 12 years ago.
This combines all of the above into one patch, for easy application. Based against 4.3.rc0

Download all attachments as: .zip

Change History (33)

Changed 12 years ago by robertwb

comment:1 Changed 12 years ago by robertwb

First pass, 4-40x faster.

comment:2 Changed 12 years ago by robertwb

  • Status changed from new to needs_work

Still has a lot of work (better integration, doctests, testing...)

Changed 12 years ago by robertwb

Changed 12 years ago by robertwb

apply on top of previous

comment:3 Changed 12 years ago by roed

  • Cc roed added

comment:4 Changed 12 years ago by roed

I've added some doctests. I'll try to split the work on FpT off from the rest of the things I've been doing on residue fields and post a patch tomorrow.

Changed 12 years ago by roed

Rebased against 4.3.rc0

Changed 12 years ago by roed

Rebased against 4.3.rc0

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

Changed 12 years ago by roed

This combines all of the above into one patch, for easy application. Based against 4.3.rc0

comment:5 Changed 12 years ago by roed

A bit later than I said, but here are some patches. I'm not sure if this is the right place to put all of them, but they're all related to GF(p)(t)... somehow (if only getting doctests that I broke fixed again)

I've subsumed Robert's patches into 7585_1_FpT-orig.patch and 7585_2_FpT-more.patch. The third patch is mostly focused on fraction_field_FpT.pyx. The rest are mostly consequences of the changes I made to residue_field.pyx, but they're pretty wide ranging.

7585_ALL.patch includes everything, but isn't viewable on trac since it's too big.

comment:6 Changed 12 years ago by AlexGhitza

  • Summary changed from Fast function field arithmatic to Fast function field arithmetic

Robert and David, is this ready for review yet?

comment:7 Changed 12 years ago by roed

I think Robert wanted to factor out some of the stuff I'd written and do some more work on the actual FpT stuff. Robert, what all do you want to happen to this ticket before review?

comment:8 Changed 12 years ago by robertwb

Yes, that is correct. I've been busy out of town, but should get a chance to take a look at this sometime next week. Nothing stopping you from starting to read the code though :).

comment:9 Changed 12 years ago by robertwb

I've split this up as follows:

#7880 7585_4_sets_with_partial_maps.patch

#7881 7585_6_gcd.patch

#7883 7585_7_ideal.patch

#7884 7585_5_finite_fields_to_new_coercion.patch 7585_8_parent_init.patch 7585_9_frac_and_coerce_updates.patch

#7885 7585_10_residue_field.patch 7585_11_tate_ff.patch 7585_12_fixes.patch

comment:10 Changed 12 years ago by robertwb

I'm wary of the changes in 7585_8_parent_init.patch -- could you explain?

comment:11 Changed 12 years ago by roed

I was a bit wary of them too, and wanted to ask a second opinion.

The goal is to make switching to the new coercion system as easy as possible. Defining an _element_constructor_ method on a parent inheriting from parent_old.Parent currently has no effect, since the init method on parent_old.Parent doesn't call the init method on parent.Parent, nor does it set _element_constructor to be equal to _element_constructor_. Ideally, parent_old.Parent's init would call parent.Parent.init, but that change caused a ton of failures. The change in parent_init.patch is more minor, just insuring that IF an _element_constructor_ method is defined, then self._element_constructor is appropriately set (and the coercion system thus believes that this parent uses the new coercion model)

comment:12 Changed 12 years ago by robertwb

FYI, I looked at this a bit during Sage days, but there were a lot of changes to the fraction field code in the alphas, so some rebasing needs to be done (and I didn't have a stable build to rebase on at the time).

comment:13 Changed 12 years ago by robertwb

I've split off the arithmatic into #9051.

comment:14 Changed 11 years ago by davidloeffler

  • Milestone changed from sage-4.6 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to needs_review
  • Summary changed from Fast function field arithmetic to [duplicate??] Fast function field arithmetic

David, Robert: what's the status of this ticket? Now that #9051 is in, and patches 4-12 have been split off into separate tickets, can we close this ticket as a duplicate? If this is true, please set it to "positive review" so the release manager can close it.

comment:15 Changed 11 years ago by roed

  • Status changed from needs_review to positive_review

All of the patches here have found other homes. I'm happy to make it duplicate.

comment:16 Changed 11 years ago by mpatel

  • Resolution set to duplicate
  • Status changed from positive_review to closed

comment:17 Changed 11 years ago by mvngu

  • Summary changed from [duplicate??] Fast function field arithmetic to Fast function field arithmetic
Note: See TracTickets for help on using tickets.