Add resultant methods to fmpz_poly and fmpq_poly by rdbliss · Pull Request #274 · flintlib/python-flint · GitHub

This adds resultant methods to fmpz_poly (resultant and resultant_modular) and fmpq_poly (resultant), which were previously only exposed for fmpz_mod_poly, fmpq_mpoly, fmpz_mpoly, nmod_mpoly, and fmpz_mod_mpoly.

I included resultant_modular because it's in flint, but in a quick performance test I didn't see much difference between it and fmpz_poly.resultant, or even fmpq_poly.resultant.

Thanks for this.

Can you add a test sort of like this one:

python-flint/src/flint/test/test_all.py

Lines 3500 to 3501 in b87c681

    
           def test_factor_poly_mpoly(): 
        
               """Test that factor() is consistent across different poly/mpoly types."""

When possible it is best to have generic tests so that we can be sure that all types implement all methods consistently. The tests can make exceptions for particular types though e.g. it looks like there are no resultant functions for fq polynomials.

I suppose that the univariate polynomials have a different signature for resultant because they return a scalar.

@oscarbenjamin tests added!

By the way, I discovered that flint's fmpz_mod_poly does not like it when the modulus is composite. I think a comment mentioning this exists in the tests already. I skipped that case since it seems like an upstream problem. However, it is very easy to cause a crash with this behavior:

>>> from flint import fmpz_mod_poly, fmpz_mod_poly_ctx
>>> x = fmpz_mod_poly([0, 1], fmpz_mod_poly_ctx(164))
>>> x.resultant(x - 2)
Flint exception (Impossible inverse):
    Exception in fmpz_mod_inv: Cannot invert.
Aborted (core dumped)

Would it be worth raising exceptions when using fmpz_mod_poly with composite modulus?

Would it be worth raising exceptions when using fmpz_mod_poly with composite modulus?

Yes. There are lots of cases like this where FLINT aborts but in python-flint we want to raise an exception instead. For fmpz_mod_poly the context stores whether or not the modulus is prime. For nmod_poly there is no context so we don't have a good solution yet.

@oscarbenjamin thanks for the advice! I added an exception for composite moduli in fmpz_mod_poly, and separated that case out in testing. It seems that nmod_poly does not have this problem, so I didn't do anything special for it.

These tests are running in a loop over all polynomial types but don't depend on the type.

I think it would be better just to move all of this out to a separate test_poly_resultants test function but still use _all_polys for the part that loops over the types.

In general it would be better not to have such large test functions as this one.

I agree, I'll split the resultant result checking off into a separate test.

In general it would be better not to have such large test functions as this one.

Do you mean test_all_polys is too long, or that this check with cyclotomic polynomials is too long?

I mean that test_all_polys is too long.

Ideally the test suite would have reasonably short test functions like test_resultants or something but where each test loops over all possible polynomial types. When a new polynomial type is added it should be possible to just add it to to the list in _all_polys and then update each test or add the methods that are needed for consistency with other types.

I'm surprised that nmod_poly doesn't crash here. I guess it sometimes does and sometimes doesn't:

In [3]: a = flint.nmod_poly([1, 2, 3], 12)

In [4]: b = flint.nmod_poly([1, 2, 3], 12)

In [5]: a.resultant(b)
Out[5]: 0

In [6]: b = flint.nmod_poly([1, 2, 3, 4], 12)

In [7]: a.resultant(b)
Flint exception (Impossible inverse):
    Cannot invert modulo 3*4
Aborted (core dumped)

Good to know! I added a similar check for nmod_poly that makes this example throw an exception.

I think it is better not to include this. There are lots of situations where FLINT provides variant functions for an operation like this and we don't generally wrap all of them in python-flint. It looks like the resultant method already switches between either using fmpz_poly_resultant_modular or fmpz_poly_resultant_euclidean depending on the degree and bitsize.

Let me know if you want to record a different name here.

Thanks for this.

Add resultant methods to fmpz_poly and fmpq_poly

fec8a10

Add resultant tests and nmod_poly implementation

86ffb15

Check for composite moduli in resultants

658e502

oscarbenjamin reviewed Mar 21, 2025

View reviewed changes

Refactor resultant tests

8bac286

oscarbenjamin reviewed Mar 31, 2025

View reviewed changes

oscarbenjamin added 2 commits April 9, 2025 12:28

Remove fmpz_poly.resultant_modular

296c96a

Add CHANGELOG for flintlibgh-274

4870eec

oscarbenjamin added the type: new feature label Apr 9, 2025

oscarbenjamin reviewed Apr 9, 2025

View reviewed changes

oscarbenjamin merged commit 117065e into flintlib:main Apr 9, 2025

+                      if is_field and characteristic == 0:
+                          # Check that the resultant of two cyclotomic polynomials is right.
+                          # See Dresden's 2012 "Resultants of Cyclotomic Polynomials"
+                          for m in range(1, 50):
+                              for n in range(m + 1, 50):
+                                  a = flint.fmpz_poly.cyclotomic(m)
+                                  b = flint.fmpz_poly.cyclotomic(n)

+                      else:
+                          assert x.resultant(x) == 0
+                          assert x.resultant(x**2 + x - x) == 0
+                          assert x.resultant(x**10 - x**5 + 1) == S(1)

+                  def resultant_modular(self, other):
+                      """
+                      Returns the resultant of *self* and *other* using Collins' 1971 modular
+                      algorithm.

+              Contributors
+              - Robert Dougherty-Bliss (RDB)
+              Changes
+              - [gh-274](https://github.com/flintlib/python-flint/pull/274),
+                Add resultant methods to `fmpz_poly`, `fmpq_poly` and
+                `nmod_poly`. Now all univariate and polynomial types have the
+                resultant method except for `fq_default_poly`. (RDB)

Add resultant methods to fmpz_poly and fmpq_poly by rdbliss · Pull Request #274 · flintlib/python-flint · GitHub

Repository navigation

Add resultant methods to fmpz_poly and fmpq_poly - #274

Add resultant methods to fmpz_poly and fmpq_poly#274oscarbenjamin merged 6 commits intoflintlib:mainflintlib/python-flint:mainfrom rdbliss:resultantrdbliss/python-flint:resultantCopy head branch name to clipboard

Conversation

rdbliss commented Mar 20, 2025

Uh oh!

oscarbenjamin commented Mar 20, 2025

Uh oh!

rdbliss commented Mar 21, 2025

Uh oh!

oscarbenjamin commented Mar 21, 2025

Uh oh!

rdbliss commented Mar 21, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

oscarbenjamin commented Apr 9, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Add resultant methods to fmpz_poly and fmpq_poly#274
oscarbenjamin merged 6 commits into
flintlib:mainfrom
rdbliss:resultant