Opened 5 years ago

Closed 4 years ago

Last modified 4 years ago

#17840 closed enhancement (fixed)

Factorization of multivariate polynomials over the integers

Reported by: bruno 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) Commit:
Dependencies: Stopgaps:

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

  • Branch set to u/bruno/factorization_of_multivariate_polynomials_over_the_integers

comment:2 Changed 5 years ago by bruno

  • Commit set to 60bffcb71e5220ecb07045c8870be8b84bc5d3bb
  • Status changed from new to needs_review

New commits:

60bffcbAdd factorization of multivariate polynomials over the integers

comment:3 follow-up: Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

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

comment:4 Changed 5 years ago by git

  • Commit changed from 60bffcb71e5220ecb07045c8870be8b84bc5d3bb to 28f89b6a73649d8c93c4ab0a5bb92f43b6ac785d

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

28f89b6Sign are now preserved + improvements

comment:5 in reply to: ↑ 3 Changed 5 years ago by bruno

  • Status changed from needs_work to needs_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 follow-up: Changed 5 years ago by bruno

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 ; follow-up: Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Use except Exception: instead of a bare except:

comment:8 Changed 5 years ago by git

  • Commit changed from 28f89b6a73649d8c93c4ab0a5bb92f43b6ac785d to 2f1962e623f4ab8ae305e05306579dfd0b4c2ce8

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

2f1962eException better handled

comment:9 in reply to: ↑ 7 Changed 5 years ago by bruno

  • Status changed from needs_work to needs_review

Replying to jdemeyer:

Use except Exception: instead of a bare except:

Thank you!

comment:10 follow-up: Changed 5 years ago by jdemeyer

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

comment:11 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:12 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by bruno

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

  • Commit changed from 2f1962e623f4ab8ae305e05306579dfd0b4c2ce8 to 0e773f480e56b1b6496ab99f0a9d34623c364998

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

0e773f4Doctest ZZ/nZZ

comment:14 in reply to: ↑ 12 Changed 5 years ago by bruno

  • Status changed from needs_work to needs_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 follow-up: Changed 5 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to needs_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 5 years ago by git

  • Commit changed from 0e773f480e56b1b6496ab99f0a9d34623c364998 to ffe8f4578766dc50cf648e94b7274dce2425318d

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

ffe8f45Remove useless (?) tests

comment:17 in reply to: ↑ 15 Changed 5 years ago by bruno

  • Status changed from needs_work to needs_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 5 years ago by bruno (previous) (diff)

comment:18 Changed 5 years ago by mmezzarobba

Related: #2179

comment:19 Changed 4 years ago by bruno

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 4 years ago by mmezzarobba

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

comment:21 Changed 4 years ago by jdemeyer

  • Branch changed from u/bruno/factorization_of_multivariate_polynomials_over_the_integers to u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers

comment:22 Changed 4 years ago by jdemeyer

  • Commit changed from ffe8f4578766dc50cf648e94b7274dce2425318d to c41d743d8733ab8ccd00aee7bde2312cb4751cbd
  • Status changed from needs_review to positive_review

New commits:

c41d743Minor review changes

comment:23 Changed 4 years ago by vbraun

  • Branch changed from u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers to c41d743d8733ab8ccd00aee7bde2312cb4751cbd
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:24 Changed 4 years ago by chapoton

  • Commit c41d743d8733ab8ccd00aee7bde2312cb4751cbd deleted

see #20435 for something going wrong

Note: See TracTickets for help on using tickets.