Opened 8 years ago

Closed 7 years ago

Last modified 6 years ago

#17840 closed enhancement (fixed)

Factorization of multivariate polynomials over the integers

Reported by: Bruno Grenet Owned by:
Priority: major Milestone: sage-6.6
Component: factorization Keywords: multivariate integer polynomial
Cc: Merged in:
Authors: Bruno Grenet Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: c41d743 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

Currently, Sage does not know how to factor multivariate polynomials over the integers:

sage: R.<x,y> = ZZ[]
sage: p = 12 * (x*y - 1) * (x + 2*y + 3)
sage: p.factor()
Traceback (most recent call last):
...
NotImplementedError: Factorization of multivariate polynomials over non-fields is not implemented.

I propose to implement it using the factorization over QQ. Of course it may not be the best possible solution, but at least it is some (temporary?) workaround. This now gives:

sage: R.<x,y> = ZZ[]
sage: p = 12 * (x*y - 1) * (x + 2*y + 3)
sage: p.factor()
2^2 * 3 * (x + 2*y + 3) * (x*y - 1)

Change History (24)

comment:1 Changed 8 years ago by Bruno Grenet

Branch: u/bruno/factorization_of_multivariate_polynomials_over_the_integers

comment:2 Changed 8 years ago by Bruno Grenet

Commit: 60bffcb71e5220ecb07045c8870be8b84bc5d3bb
Status: newneeds_review

New commits:

60bffcbAdd factorization of multivariate polynomials over the integers

comment:3 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

Add a doctest with a negative sign to show that signs are preserved.

comment:4 Changed 8 years ago by git

Commit: 60bffcb71e5220ecb07045c8870be8b84bc5d3bb28f89b6a73649d8c93c4ab0a5bb92f43b6ac785d

Branch pushed to git repo; I updated commit sha1. New commits:

28f89b6Sign are now preserved + improvements

comment:5 in reply to:  3 Changed 8 years ago by Bruno Grenet

Status: needs_workneeds_review

Replying to jdemeyer:

Add a doctest with a negative sign to show that signs are preserved.

They were not! Thanks for spotting this :-).

comment:6 Changed 8 years ago by Bruno Grenet

I have a question: Since the computation for non-fields is enclosed inside a try/except construction, if a computation is long and interrupted with Ctrl+c, a KeyboardInterrupt exception is raised and caught by the except to raise a NotImplementedError exception.

What is a correct solution so that it does not return NotImplementedError?

  • Should the KeyboardInterrupt exception be filtered?
  • Should the try/except be enclosed in sig_on()/sig_off()?
  • Something else?

comment:7 in reply to:  6 ; Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

Use except Exception: instead of a bare except:

comment:8 Changed 8 years ago by git

Commit: 28f89b6a73649d8c93c4ab0a5bb92f43b6ac785d2f1962e623f4ab8ae305e05306579dfd0b4c2ce8

Branch pushed to git repo; I updated commit sha1. New commits:

2f1962eException better handled

comment:9 in reply to:  7 Changed 8 years ago by Bruno Grenet

Status: needs_workneeds_review

Replying to jdemeyer:

Use except Exception: instead of a bare except:

Thank you!

comment:10 Changed 8 years ago by Jeroen Demeyer

You should add an example where the factorisation currently fails (say, over the ring of integers of some number field).

comment:11 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

comment:12 in reply to:  10 ; Changed 8 years ago by Bruno Grenet

Replying to jdemeyer:

You should add an example where the factorisation currently fails (say, over the ring of integers of some number field).

Actually, polynomials over the ring of integers of a number field belong to the class MPolynomial_polydict (defined in multi_polynomial_element.py) and not to MPolynomial_libsingular (defined in multi_polynomial_libsingular.pyx). So it does not make sense to test this in this file.¹

It would be interesting to have such an example of a non-working case. Though I do not know for which ring(s) do the polynomials belong to the class MPolynomial_libsingular.

¹ One may do the same thing for rings of integers of a number field to obtain a factorization algorithm. The point is that the returned factors are not in the rings of integers in this case, so we have to reconstruct them. It's a bit more work than in the current case.

comment:13 Changed 8 years ago by git

Commit: 2f1962e623f4ab8ae305e05306579dfd0b4c2ce80e773f480e56b1b6496ab99f0a9d34623c364998

Branch pushed to git repo; I updated commit sha1. New commits:

0e773f4Doctest ZZ/nZZ

comment:14 in reply to:  12 Changed 8 years ago by Bruno Grenet

Status: needs_workneeds_review

Replying to bruno:

It would be interesting to have such an example of a non-working case. Though I do not know for which ring(s) do the polynomials belong to the class MPolynomial_libsingular.

I haven't been able to find a non-field integral domain D, different from ZZ, such that D['x','y'] belongs to MPolynomial_libsingular. So I add a doctest for Zmod(4)['x','y'] for which the factorization indeed fails.

comment:15 Changed 8 years ago by Jeroen Demeyer

Reviewers: Jeroen Demeyer
Status: needs_reviewneeds_work

Some comments:

  1. Replace raise Exception, "Message." by raise Exception("message").
  1. Is the check for integral domain really needed? If it's not an integral domain, it will be caught by the branch below.
  1. Why did you add the check for symbolic ring? If it's needed, there should also be a doctest added for this case.
  1. The message Factorization of multivariate polynomials over Symbolic Ring is not implemented. Consider using multivariate polynomial rings instead. is confusing, it essentially says "factorization of multivariate polynomials is not supported, use multivariate polynomials instead".

comment:16 Changed 8 years ago by git

Commit: 0e773f480e56b1b6496ab99f0a9d34623c364998ffe8f4578766dc50cf648e94b7274dce2425318d

Branch pushed to git repo; I updated commit sha1. New commits:

ffe8f45Remove useless (?) tests

comment:17 in reply to:  15 Changed 8 years ago by Bruno Grenet

Status: needs_workneeds_review

Replying to jdemeyer:

  1. Replace raise Exception, "Message." by raise Exception("message").

Done.

  1. Is the check for integral domain really needed? If it's not an integral domain, it will be caught by the branch below.
  2. Why did you add the check for symbolic ring? If it's needed, there should also be a doctest added for this case.

These both tests were not really needed. I added them in order to give more meaningful error messages. Now, the error message for the SymbolicRing is kind of weird, but the test I added was probably not the right place where to correct this.¹

For non-integral domains, you know have that multivariate factorization over Ring of integers modulo 4 is not implemented (for instance) while with the previous version it said that the factorization over non-integral rings is not implemented. I personally find the previous message more informative, but that is a matter of taste and I am also fine with the current message.

  1. The message Factorization of multivariate polynomials over Symbolic Ring is not implemented. Consider using multivariate polynomial rings instead. is confusing, it essentially says "factorization of multivariate polynomials is not supported, use multivariate polynomials instead".

Not relevant anymore, though I agree with the confusing aspect of this message!

¹ The main problem is that the SymbolicRing has no is_finite() method. Thus we get a NotImplementedError which is not very informative. See #18054.

Last edited 8 years ago by Bruno Grenet (previous) (diff)

comment:18 Changed 7 years ago by Marc Mezzarobba

Related: #2179

comment:19 Changed 7 years ago by Bruno Grenet

It seems that the code proposed in #2179 is not in its current form ready to use (based on his author's comments). There was supposed to be some improved version, but since it is already 7 years old, we should maybe ignore it for now?

comment:20 Changed 7 years ago by Marc Mezzarobba

Yes, probably, I was only pointing out the other ticket just in case there was something relevant there.

comment:21 Changed 7 years ago by Jeroen Demeyer

Branch: u/bruno/factorization_of_multivariate_polynomials_over_the_integersu/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers

comment:22 Changed 7 years ago by Jeroen Demeyer

Commit: ffe8f4578766dc50cf648e94b7274dce2425318dc41d743d8733ab8ccd00aee7bde2312cb4751cbd
Status: needs_reviewpositive_review

New commits:

c41d743Minor review changes

comment:23 Changed 7 years ago by Volker Braun

Branch: u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integersc41d743d8733ab8ccd00aee7bde2312cb4751cbd
Resolution: fixed
Status: positive_reviewclosed

comment:24 Changed 6 years ago by Frédéric Chapoton

Commit: c41d743d8733ab8ccd00aee7bde2312cb4751cbd

see #20435 for something going wrong

Note: See TracTickets for help on using tickets.