Opened 8 years ago

Closed 8 years ago

Last modified 7 years ago

#10635 closed enhancement (fixed)

refactor polynomial_element.pyx factor function

Reported by: was Owned by: AlexGhitza
Priority: minor Milestone: sage-4.7.2
Component: basic arithmetic Keywords: sd32
Cc: Merged in: sage-4.7.2.alpha3
Authors: Christopher Hall Reviewers: Mariah Lenox, William Stein, Simon Spicer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by leif)

The "factor" function in polynomial_element.pyx needs to be refactored, because it has to be modified every time a new interesting base ring gets added to Sage.

Instead of importing a ton of different rings, the function should just call a method on the base ring, e.g.,

def _factor_univariate_polynomial(self, f):
    ...

Since the code in factor is for generic polynomials, it doesn't use their internal representation, so this should be fine. It just turns out that factoring algorithms depend a huge amount on the base ring, and polynomials get created over tons of different bases (but there are far less classes that derive from "polynomial").

I suggest for this ticket, at a minimum we add a quick "hasattr" check at the top of the current factor function, then leave the existing code. Then new code can be written to use this. In the near future somebody can move most of the imports and cases out the current factor function, so it becomes very short, and the code gets put in the right place.

A major motivation for this is that people create their own new rings R in external code that depends on sage, and want to be able to factor polynomials over R. They do *not* define a new class for polynomials over R. It seems silly for them to have to patch the core sage library to get factorization functionality.


Apply

  1. trac_10635-new_version_with_tests.patch
  2. trac_10635-fix_doctest_error_due_to_noise.reviewer.patch

to the Sage library.

Attachments (3)

trac_10635_field_hooks.patch (1.2 KB) - added by cjh 8 years ago.
Patch implementing desired changes
trac_10635-new_version_with_tests.patch (4.0 KB) - added by was 8 years ago.
apply only this patch
trac_10635-fix_doctest_error_due_to_noise.reviewer.patch (1.4 KB) - added by leif 7 years ago.
Reviewer patch to fix doctest error on some systems (e.g. x86). Apply on top of other patch.

Download all attachments as: .zip

Change History (18)

comment:1 follow-up: Changed 8 years ago by cjh

As someone interested in this change, let me chime in with a few suggestions of my own.

(1) A similar refactoring should be done for roots(). It's true factor() can be used to find roots, but that's not necessarily the best approach. This suggests the names ._univariate_polynomial_x for x=factor,roots,etc.

(2) So-called 'modular' gcd algorithms give a real boost to rings where applicable, so it would be nice to let x=gcd in (1).

(3) Consider whether options such as 'multiplicities=False' should really be options to .univariate_polynomial_factor() or whether they can be handled 'universally'.

Changed 8 years ago by cjh

Patch implementing desired changes

comment:2 Changed 8 years ago by cjh

  • Status changed from new to needs_review

The patch addresses issue (1) and is for Sage 4.6.2.

comment:3 Changed 8 years ago by mariah

  • Reviewers set to Mariah Lenox
  • Status changed from needs_review to needs_info

Patch applied to sage-4.7.1.alpha2, then did 'sage -b', then 'make testlong'. All tests passed. Positive review!

cjh - you need to add your name to the author field.

comment:4 Changed 8 years ago by was

  • Status changed from needs_info to needs_review

comment:5 Changed 8 years ago by was

  • Status changed from needs_review to needs_work

The patch should have an example that illustrates that each added capability actually works. That could be a class created in a docstring, or a small demo class added to the source code with an example.

comment:6 Changed 8 years ago by was

  • Authors set to Christopher Hall
  • Reviewers changed from Mariah Lenox to Mariah Lenox, William Stein

Changed 8 years ago by was

apply only this patch

comment:7 Changed 8 years ago by was

  • Status changed from needs_work to needs_review

comment:8 Changed 8 years ago by spice

  • Reviewers changed from Mariah Lenox, William Stein to Mariah Lenox, William Stein, Simon Spicer
  • Status changed from needs_review to positive_review

Yep, looks fine. Test pass, code works, couldn't even find a typo. Note that this latest patch only sets it up so that if a base ring has a native _factor_univariate_polynomial() or _roots_univariate_polynomial() method, then those will be used instead of the generic factor() and roots() method in polynomial_element.pyx.

The ring-specific functionality of these two methods still needs to be moved across to their respective files; to address this I've created patch #11731.

comment:9 Changed 8 years ago by was

  • Keywords sd32 added

comment:10 Changed 8 years ago by leif

  • Description modified (diff)

comment:11 Changed 8 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed

Changed 7 years ago by leif

Reviewer patch to fix doctest error on some systems (e.g. x86). Apply on top of other patch.

comment:12 Changed 7 years ago by leif

  • Description modified (diff)

I've attached a reviewer patch fixing a doctest error in a factorization.

(The order of the factors changes, depending on the sign of a "zero" term in the polynomial which is one factor. The example now looks a bit ugly, but I don't want to wait until we have zero_at() methods for all kinds of domains, and just tagging the whole doctest "# random" would also be odd, IMHO. Note that it previously didn't fail on all 32-bit systems, e.g. not 32-bit SPARC, and tagging the results "# 32-bit" and "# 64-bit" would have been inadequate anyway, since the machine word width is completely unrelated, i.e., that the test failed on x86 processors only is just a weird coincidence.)

comment:13 in reply to: ↑ 1 Changed 7 years ago by saraedum

Factorization over function fields (provided by #9054) uses the function defined in this ticket (_factor_univariate_polynomial). However, in some cases it requires a parameter proof=False to work. So, the easy solution for #9054 was to add the default parameter proof=True to polynomial_element.factor() and pass it on to _factor_univariate_polynomial. So, to make #9054 work with this ticket, should we just pass on all *args and kwargs to _factor_univariate_polynomial? I do not understand what you mean by 'universally' but I guess it's related to this question.

Replying to cjh:

(3) Consider whether options such as 'multiplicities=False' should really be options to .univariate_polynomial_factor() or whether they can be handled 'universally'.

comment:14 Changed 7 years ago by saraedum

I opened a ticket for the function field case: #12100

comment:15 Changed 7 years ago by saraedum

Sorry for the false alarm. I must have been working with an outdated version of #9054. Actually the proof parameter is passed on. Anyway, I'm thinking about doing parts of #11731, so I'd still like to know what you had in mind with the 'universally'.

Note: See TracTickets for help on using tickets.