fix(polys): fix multi factorisation over QQ<a> #26515

oscarbenjamin · 2024-04-17T22:48:43Z

References to other Issues or PRs

Brief description of what is fixed or changed

There are various things here.

Fix dmp_sqf_p to check properly that multivariate polynomials are square free over the ground domain. This is also fixes Poly.is_sqf.
Change dmp_sqf_norm to use shifts in multiple variables.
Add _dmp_sqf_norm_shifts to try to find efficient multivariate shifts.
The sqf_norm functions now return a shift list rather than a single shift integer. This is to compute a shift like f(x1-s1*a, x2-s2*a, ...).
Add dmp_shift and Poly.shift_list for multivariate polynomial shifts.
Add sanity checks that the degrees add up in various factorisation routines.
Add dmp_norm to PolyRing.
Add norm to PolyElement.
Add tests for better general coverage of densetools.
Add missing functions to polys docs and minor improvements to docstrings.
Expand docstrings with explanation of some algorithms and references.

The most important part is the fix for gh-26497 which is that dmp_ext_factor and hence factor over ZZ_I or QQ_I gave incorrect results for some multivariate polynomials. The bug is caused by dmp_sqf_norm choosing a polynomial that is not square-free which is in turn caused by dmp_sqf_p incorrectly reporting some polynomials as square-free.

The implementation of dmp_sqf_p on master treats a multivariate polynomial as if it were a univariate polynomial in its leading variable. This means that it only considers a polynomial to be square-free if it has squared factors of positive degree in the leading variable. Hence:

In [1]: (y**2).as_poly(x, y).is_sqf
Out[1]: True

This is not the sense of "square-free" that is needed for sqf_norm i.e. a polynomial should only be square free if there are no squared factors having positive degree in any variable. Potentially there is some value in having two different notions of square-free but realistically the notion that we generally want is that of being square free in any variable so that is what I have changed it to.

Fixing dmp_sqf_p means that dmp_sqf_norm does not return an incorrect result with a norm that is not square-free. However then dmp_sqf_norm goes into an infinite loop. This is because it tries to shift the polynomial like f(x,y,z,...) -> f(x-1,y,z,...) -> f(x-2,y,z,...). This is sequence of shifts is not guaranteed to result in a square-free norm for a multivariate polynomial. Instead we can use f(x,y,z,...) -> f(x-1,y-1,z-1,...) -> f(x-2,y-2,z-2,...). Shifting all variables like this works and guarantees to find a square-free norm but can be very slow for some polynomials and caused some tests to hang.

A more efficient sequence of shifts requires that we use different shifts for each variable e.g. we try f(x,y,z), f(x-1,y,z), f(x,y-1,z) and so on before shifting all variables. This usually results in finding a shift such that the norm can be computed just as efficiently as before. The problem though is that this means that s returned from dmp_sqf_norm needs to be a list of integer shifts rather than a single integer.

Changing dmp_sqf_norm and also Poly.sqf_norm and sqf_norm to return a list of integer shifts is not backwards compatible. However I doubt that anyone is using these functions for anything. As far as I know their only real purpose is as an internal routine in Trager's algorithm for factorisation (dup_ext_factor/dmp_ext_factor). I don't see why anyone would be using these functions directly rather than e.g. factor so I think it should be okay to change the return type.

In turn I then added dmp_shift and Poly.shift_list so that the list of shifts can be used directly.

I then added various other things including tests, docs, etc as a general cleanup.

Other comments

Release Notes

polys
- A serious bug in factorisation of multivariate polynomials over extension fields was fixed. Previously, incorrect results were returned in some cases. The bug would most likely manifest when calling factor on an expression with more than one symbol and the complex unit I.
- A bug in the Poly method is_sqf was fixed. Previously some multivariate polynomials were incorrectly reported as being square-free.
- BREAKING CHANGE: The sqf_norm function and Poly.sqf_norm functions are now changed to return a list of integer shifts instead of a single integer shift. This is not a backwards compatible change but is needed because in general in the multivariate case different shifts are needed for each variable.
- A new shift_list method is added to Poly and other polynomial types for computing shifts of multivariate polynomials.
- Some documentation was added for internal routines in the polys module.

sympy-bot · 2024-04-17T22:48:49Z

✅

Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

polys
- A serious bug in factorisation of multivariate polynomials over extension fields was fixed. Previously, incorrect results were returned in some cases. The bug would most likely manifest when calling factor on an expression with more than one symbol and the complex unit I. (#26515 by @oscarbenjamin)
- A bug in the Poly method is_sqf was fixed. Previously some multivariate polynomials were incorrectly reported as being square-free. (#26515 by @oscarbenjamin)
- BREAKING CHANGE: The sqf_norm function and Poly.sqf_norm functions are now changed to return a list of integer shifts instead of a single integer shift. This is not a backwards compatible change but is needed because in general in the multivariate case different shifts are needed for each variable. (#26515 by @oscarbenjamin)
- A new shift_list method is added to Poly and other polynomial types for computing shifts of multivariate polynomials. (#26515 by @oscarbenjamin)
- Some documentation was added for internal routines in the polys module. (#26515 by @oscarbenjamin)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.13.

Click here to see the pull request description that was parsed.

<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->

Fixes gh-26497

#### Brief description of what is fixed or changed

There are various things here.

- Fix `dmp_sqf_p` to check properly that multivariate polynomials are square free over the ground domain. This is also fixes `Poly.is_sqf`.
- Change `dmp_sqf_norm` to use shifts in multiple variables.
- Add `_dmp_sqf_norm_shifts` to try to find efficient multivariate shifts.
- The `sqf_norm` functions now return a shift list rather than a single shift integer. This is to compute a shift like `f(x1-s1*a, x2-s2*a, ...)`.
- Add `dmp_shift` and `Poly.shift_list` for multivariate polynomial shifts.
- Add sanity checks that the degrees add up in various factorisation routines.
- Add `dmp_norm` to `PolyRing`.
- Add `norm` to `PolyElement`.
- Add tests for better general coverage of densetools.
- Add missing functions to polys docs and minor improvements to docstrings.
- Expand docstrings with explanation of some algorithms and references.

 The most important part is the fix for gh-26497 which is that `dmp_ext_factor` and hence `factor` over `ZZ_I` or `QQ_I` gave incorrect results for some multivariate polynomials. The bug is caused by `dmp_sqf_norm` choosing a polynomial that is not square-free which is in turn caused by `dmp_sqf_p` incorrectly reporting some polynomials as square-free.

The implementation of `dmp_sqf_p` on master treats a multivariate polynomial as if it were a univariate polynomial in its leading variable. This means that it only considers a polynomial to be square-free if it has squared factors of positive degree in the leading variable. Hence:
```python
In [1]: (y**2).as_poly(x, y).is_sqf
Out[1]: True
```
This is not the sense of "square-free" that is needed for `sqf_norm` i.e. a polynomial should only be square free if there are no squared factors having positive degree in *any* variable. Potentially there is some value in having two different notions of square-free but realistically the notion that we generally want is that of being square free in any variable so that is what I have changed it to.

Fixing `dmp_sqf_p` means that `dmp_sqf_norm` does not return an incorrect result with a norm that is not square-free. However then `dmp_sqf_norm` goes into an infinite loop. This is because it tries to shift the polynomial like `f(x,y,z,...) -> f(x-1,y,z,...) -> f(x-2,y,z,...)`. This is sequence of shifts is not guaranteed to result in a square-free norm for a multivariate polynomial. Instead we can use `f(x,y,z,...) -> f(x-1,y-1,z-1,...) -> f(x-2,y-2,z-2,...)`. Shifting all variables like this works and guarantees to find a square-free norm but can be very slow for some polynomials and caused some tests to hang.

A more efficient sequence of shifts requires that we use different shifts for each variable e.g. we try `f(x,y,z)`, `f(x-1,y,z)`, `f(x,y-1,z)` and so on before shifting all variables. This usually results in finding a shift such that the norm can be computed just as efficiently as before. The problem though is that this means that `s` returned from `dmp_sqf_norm` needs to be a list of integer shifts rather than a single integer.

Changing `dmp_sqf_norm` and also `Poly.sqf_norm` and `sqf_norm` to return a list of integer shifts is not backwards compatible. However I doubt that anyone is using these functions for anything. As far as I know their only real purpose is as an internal routine in Trager's algorithm for factorisation (`dup_ext_factor/dmp_ext_factor`). I don't see why anyone would be using these functions directly rather than e.g. `factor` so I think it should be okay to change the return type.

In turn I then added `dmp_shift` and `Poly.shift_list` so that the list of shifts can be used directly.

I then added various other things including tests, docs, etc as a general cleanup.

#### Other comments


#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers. Formerly, `log(-x)` incorrectly gave `-log(x)`.

* physics.units
  * Corrected a semantical error in the conversion between volt and statvolt which
    reported the volt as being larger than the statvolt.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* polys
    * A serious bug in factorisation of multivariate polynomials over extension fields was fixed. Previously, incorrect results were returned in some cases. The bug would most likely manifest when calling `factor` on an expression with more than one symbol and the complex unit `I`.
    * A bug in the Poly method `is_sqf` was fixed. Previously some multivariate polynomials were incorrectly reported as being square-free.
    * BREAKING CHANGE: The `sqf_norm` function and `Poly.sqf_norm` functions are now changed to return a list of integer shifts instead of a single integer shift. This is not a backwards compatible change but is needed because in general in the multivariate case different shifts are needed for each variable.
    * A new `shift_list` method is added to `Poly` and other polynomial types for computing shifts of multivariate polynomials.
    * Some documentation was added for internal routines in the polys module.
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

oscarbenjamin · 2024-04-17T23:23:17Z

The two doctests that are failing are fine. They can just be updated. The output of dmp_sqf_norm is not uniquely defined so it is fine to return different outputs as long as they satisfy the invariant.

See the Trager 1976 reference noted in the docstring for explanation of what this function is doing.

sympy/polys/sqfreetools.py

github-actions · 2024-04-29T01:05:45Z

Benchmark results from GitHub Actions

Lower numbers are good, higher numbers are bad. A ratio less than 1
means a speed up and greater than 1 means a slowdown. Green lines
beginning with + are slowdowns (the PR is slower then master or
master is slower than the previous release). Red lines beginning
with - are speedups.

Significantly changed benchmark results (PR vs master)

Significantly changed benchmark results (master vs previous release)

| Change   | Before [2487dbb5]    | After [a73da947]    |   Ratio | Benchmark (Parameter)                                                |
|----------|----------------------|---------------------|---------|----------------------------------------------------------------------|
| -        | 68.4±0.6ms           | 44.4±0.4ms          |    0.65 | integrate.TimeIntegrationRisch02.time_doit(10)                       |
| -        | 68.4±0.5ms           | 44.0±0.6ms          |    0.64 | integrate.TimeIntegrationRisch02.time_doit_risch(10)                 |
| +        | 18.6±0.1μs           | 30.0±0.3μs          |    1.61 | integrate.TimeIntegrationRisch03.time_doit(1)                        |
| -        | 5.39±0.06ms          | 2.85±0.01ms         |    0.53 | logic.LogicSuite.time_load_file                                      |
| -        | 74.4±0.4ms           | 29.5±0.3ms          |    0.4  | polys.TimeGCD_GaussInt.time_op(1, 'dense')                           |
| -        | 26.0±0.1ms           | 17.0±0.03ms         |    0.66 | polys.TimeGCD_GaussInt.time_op(1, 'expr')                            |
| -        | 74.6±0.2ms           | 28.9±0.1ms          |    0.39 | polys.TimeGCD_GaussInt.time_op(1, 'sparse')                          |
| -        | 257±2ms              | 126±0.5ms           |    0.49 | polys.TimeGCD_GaussInt.time_op(2, 'dense')                           |
| -        | 260±3ms              | 126±0.9ms           |    0.49 | polys.TimeGCD_GaussInt.time_op(2, 'sparse')                          |
| -        | 669±6ms              | 373±1ms             |    0.56 | polys.TimeGCD_GaussInt.time_op(3, 'dense')                           |
| -        | 668±6ms              | 374±2ms             |    0.56 | polys.TimeGCD_GaussInt.time_op(3, 'sparse')                          |
| -        | 493±2μs              | 287±2μs             |    0.58 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(1, 'dense')            |
| -        | 1.79±0.01ms          | 1.05±0ms            |    0.59 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(2, 'dense')            |
| -        | 5.82±0.02ms          | 3.09±0.03ms         |    0.53 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(3, 'dense')            |
| -        | 451±4μs              | 229±4μs             |    0.51 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(1, 'dense')               |
| -        | 1.50±0.02ms          | 678±6μs             |    0.45 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(2, 'dense')               |
| -        | 4.91±0.03ms          | 1.66±0.01ms         |    0.34 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(3, 'dense')               |
| -        | 371±1μs              | 213±2μs             |    0.58 | polys.TimeGCD_SparseGCDHighDegree.time_op(1, 'dense')                |
| -        | 2.43±0.02ms          | 1.23±0.01ms         |    0.5  | polys.TimeGCD_SparseGCDHighDegree.time_op(3, 'dense')                |
| -        | 9.99±0.06ms          | 4.33±0.02ms         |    0.43 | polys.TimeGCD_SparseGCDHighDegree.time_op(5, 'dense')                |
| -        | 361±3μs              | 172±1μs             |    0.48 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(1, 'dense')            |
| -        | 2.49±0.01ms          | 906±10μs            |    0.36 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(3, 'dense')            |
| -        | 9.56±0.02ms          | 2.69±0ms            |    0.28 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(5, 'dense')            |
| -        | 1.05±0.01ms          | 432±3μs             |    0.41 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'dense')           |
| -        | 1.73±0.01ms          | 554±40μs            |    0.32 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'sparse')          |
| -        | 5.89±0.03ms          | 1.81±0ms            |    0.31 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'dense')           |
| -        | 8.42±0.04ms          | 1.51±0.01ms         |    0.18 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'sparse')          |
| -        | 285±2μs              | 66.0±0.5μs          |    0.23 | polys.TimePREM_QuadraticNonMonicGCD.time_op(1, 'sparse')             |
| -        | 3.57±0.02ms          | 395±3μs             |    0.11 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'dense')              |
| -        | 3.99±0.03ms          | 281±2μs             |    0.07 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'sparse')             |
| -        | 7.04±0.09ms          | 1.28±0.01ms         |    0.18 | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'dense')              |
| -        | 8.60±0.02ms          | 845±5μs             |    0.1  | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'sparse')             |
| -        | 5.04±0.05ms          | 3.04±0.02ms         |    0.6  | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(2, 'sparse') |
| -        | 12.0±0.03ms          | 6.64±0.03ms         |    0.55 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'dense')  |
| -        | 22.2±0.07ms          | 9.11±0.09ms         |    0.41 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'sparse') |
| -        | 5.31±0.01ms          | 879±4μs             |    0.17 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(1, 'sparse')    |
| -        | 12.6±0.05ms          | 7.13±0.03ms         |    0.56 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(2, 'sparse')    |
| -        | 102±1ms              | 26.1±0.1ms          |    0.25 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'dense')     |
| -        | 168±0.8ms            | 54.3±0.1ms          |    0.32 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'sparse')    |
| -        | 171±0.5μs            | 112±0.5μs           |    0.65 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(1, 'dense')      |
| -        | 357±1μs              | 220±0.8μs           |    0.62 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(1, 'sparse')     |
| -        | 4.24±0.04ms          | 849±3μs             |    0.2  | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'dense')      |
| -        | 5.28±0.02ms          | 385±1μs             |    0.07 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'sparse')     |
| -        | 19.8±0.1ms           | 2.79±0.01ms         |    0.14 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'dense')      |
| -        | 22.9±0.4ms           | 624±2μs             |    0.03 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'sparse')     |
| -        | 479±2μs              | 140±1μs             |    0.29 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(1, 'sparse') |
| -        | 4.74±0.03ms          | 629±1μs             |    0.13 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'dense')  |
| -        | 5.34±0.02ms          | 143±0.3μs           |    0.03 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'sparse') |
| -        | 13.1±0.1ms           | 1.30±0ms            |    0.1  | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'dense')  |
| -        | 14.3±0.2ms           | 146±0.7μs           |    0.01 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'sparse') |
| -        | 133±0.6μs            | 74.5±0.5μs          |    0.56 | solve.TimeMatrixOperations.time_rref(3, 0)                           |
| -        | 252±0.7μs            | 88.4±0.7μs          |    0.35 | solve.TimeMatrixOperations.time_rref(4, 0)                           |
| -        | 24.0±0.05ms          | 10.1±0.01ms         |    0.42 | solve.TimeSolveLinSys189x49.time_solve_lin_sys                       |
| -        | 28.1±0.2ms           | 15.5±0.06ms         |    0.55 | solve.TimeSparseSystem.time_linsolve_Aaug(20)                        |
| -        | 54.2±0.1ms           | 25.1±0.07ms         |    0.46 | solve.TimeSparseSystem.time_linsolve_Aaug(30)                        |
| -        | 28.1±0.4ms           | 15.3±0.02ms         |    0.55 | solve.TimeSparseSystem.time_linsolve_Ab(20)                          |
| -        | 54.7±0.2ms           | 25.0±0.2ms          |    0.46 | solve.TimeSparseSystem.time_linsolve_Ab(30)                          |

Full benchmark results can be found as artifacts in GitHub Actions
(click on checks at the top of the PR).

This is needed in general for multivariate polynomials rather than just returning a single integer shift.

oscarbenjamin · 2024-05-03T14:17:59Z

This is ready for review.

skieffer

Still reviewing, but this looks good so far...

The narrative really helped in understanding all the changes that were made, their motivation, etc.

A couple of edits for the release notes:

"Previously incorrect results were returned in some cases." -->

"Previously, incorrect results were returned in some cases."


"functions are no changed to return a list of" -->

"functions are now changed to return a list of"

sympy/polys/sqfreetools.py

sympy/polys/tests/test_rings.py

sympy/polys/factortools.py

sympy/polys/sqfreetools.py

oscarbenjamin · 2024-05-03T23:02:06Z

A couple of edits for the release notes:

Fixed.

sympy/polys/sqfreetools.py

skieffer · 2024-05-03T23:42:32Z

sympy/polys/sqfreetools.py

+    It would be better to use a dedicated algorithm for multivariate
+    polynomials instead.


Fair if you don't have particular candidate algorithms in mind, but if you do have some references, might be good to provide them as a starting point for future developers.

If I had found a good reference describing a simple algorithm for this then I would have implemented it.

The original Yun76 paper did describe a multivariate algorithm as well:
https://dl.acm.org/doi/pdf/10.1145/800205.806320

However that algorithm is more complicated because it depends on the EZGCD algorithm which is not implemented in sympy. I am not sure that it is in general worth implementing EZGCD because I believe it is superseded by other GCD algorithms.

Yun also refers to previous papers that have multivariate algorithms involving Hensel lifting that I assume are also more complicated.

It seems common in textbooks, theses etc to describe Yun's univariate algorithm but not mention the multivariate case.

More recent papers generally often describe the case of multivariate polynomials in positive characteristic e.g.

On square-free factorization of multivariate over a finite field
Laurent Bernardin 1997

Bernardin compares the algorithm for multivariate polynomials in positive characteristic with Yun's multivariate algorithm in characteristic zero. Bernardin's algorithm is claimed to be simpler and have other advantages. It looks a lot like Yun's univariate algorithm but it is for positive characteristic.

I can't seem to find a simple description of the multivariate characteristic zero case. I think possibly the reason for that is because it is "trivial" somehow like maybe Bernardin's algorithm can be trivially adapted to characteristic zero. It doesn't seem trivial to me though...

Bernardin's algorithm requires computing a $p^l$-th root of a polynomial for maximal $l$ where $p$ is the characteristic. I'm not sure what to do with that in the characteristic zero case. Maybe we can just skip that step?

I'm happy to keep thinking about this one, but don't have any good ideas right now.

Anyway, this thread can serve as a good starting point for future work.

skieffer · 2024-05-08T15:40:49Z

This looks good to me.

oscarbenjamin · 2024-05-08T17:11:52Z

Thanks for the review!

oscarbenjamin added the polys label Apr 17, 2024

oscarbenjamin added this to the SymPy 1.13 milestone Apr 17, 2024

fix(polys): fix multi factorisation over QQ<a>

6f7f0ec

oscarbenjamin force-pushed the pr_dmp_ext_factor branch from 6d43c6a to 6f7f0ec Compare April 17, 2024 22:56

oscarbenjamin mentioned this pull request Apr 17, 2024

factor produces wrong output #26497

Closed

oscarbenjamin commented Apr 17, 2024

View reviewed changes

sympy/polys/sqfreetools.py Show resolved Hide resolved

oscarbenjamin added 4 commits April 28, 2024 18:45

polys: fix docstring for dmp_sqf_norm

6b79f06

test: mark two tests as tooslow after fater_ext changes

465e0ac

flake8: remove unneeded import

77c15ef

test: mark ode test as tooslow

4a09fbc

oscarbenjamin added 11 commits May 1, 2024 15:15

polys: sqf_norm returns a list of integer shifts

cc95679

This is needed in general for multivariate polynomials rather than just returning a single integer shift.

polys: use more efficient shifts in dmp_sqf_norm

e9af875

test: restore tests previously marked as tooslow

2912377

polys: sanity check degrees of factors in factor

b1439d7

polys: add docs for Trager's algorithm

73e7190

polys: add tests for factorisation in extension fields

e979edf

polys: use raw docstring in dmp_ext_factor

2e76725

polys: add Poly.shift_list() for multi polys

4a58940

polys: sanity check degrees in sqf factorisation

bdf2cf5

polys: expand dmp_sqf_list docstring

b406a42

polys: rename PolyElement.norm_algebraic -> norm

2c01ca9

oscarbenjamin marked this pull request as ready for review May 3, 2024 14:16

skieffer reviewed May 3, 2024

View reviewed changes

sympy/polys/sqfreetools.py Outdated Show resolved Hide resolved

sympy/polys/tests/test_rings.py Show resolved Hide resolved

sympy/polys/factortools.py Show resolved Hide resolved

skieffer reviewed May 3, 2024

View reviewed changes

sympy/polys/factortools.py Outdated Show resolved Hide resolved

skieffer reviewed May 3, 2024

View reviewed changes

sympy/polys/sqfreetools.py Show resolved Hide resolved

skieffer reviewed May 3, 2024

View reviewed changes

sympy/polys/sqfreetools.py Outdated Show resolved Hide resolved

polys: add test for PolyElement.norm

78bcf84

oscarbenjamin added 3 commits May 4, 2024 00:03

Remove redundant assignment

86ba0a8

polys: fix test name

39d547e

polys: fix ring names

cfe16d4

skieffer reviewed May 3, 2024

View reviewed changes

sympy/polys/sqfreetools.py Show resolved Hide resolved

skieffer reviewed May 3, 2024

View reviewed changes

polys: check factors in dup_trial_division

82c1557

oscarbenjamin merged commit 2658461 into sympy:master May 8, 2024
48 checks passed

oscarbenjamin deleted the pr_dmp_ext_factor branch May 8, 2024 17:12

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix(polys): fix multi factorisation over QQ<a> #26515

fix(polys): fix multi factorisation over QQ<a> #26515

oscarbenjamin commented Apr 17, 2024 •

edited

sympy-bot commented Apr 17, 2024 •

edited

oscarbenjamin commented Apr 17, 2024

github-actions bot commented Apr 29, 2024 •

edited

oscarbenjamin commented May 3, 2024

skieffer left a comment

oscarbenjamin commented May 3, 2024

skieffer May 3, 2024

oscarbenjamin May 4, 2024

skieffer May 8, 2024

skieffer commented May 8, 2024

oscarbenjamin commented May 8, 2024

		It would be better to use a dedicated algorithm for multivariate
		polynomials instead.

fix(polys): fix multi factorisation over QQ<a> #26515

fix(polys): fix multi factorisation over QQ<a> #26515

Conversation

oscarbenjamin commented Apr 17, 2024 • edited

References to other Issues or PRs

Brief description of what is fixed or changed

Other comments

Release Notes

sympy-bot commented Apr 17, 2024 • edited

oscarbenjamin commented Apr 17, 2024

github-actions bot commented Apr 29, 2024 • edited

oscarbenjamin commented May 3, 2024

skieffer left a comment

Choose a reason for hiding this comment

oscarbenjamin commented May 3, 2024

skieffer May 3, 2024

Choose a reason for hiding this comment

oscarbenjamin May 4, 2024

Choose a reason for hiding this comment

skieffer May 8, 2024

Choose a reason for hiding this comment

skieffer commented May 8, 2024

oscarbenjamin commented May 8, 2024

oscarbenjamin commented Apr 17, 2024 •

edited

sympy-bot commented Apr 17, 2024 •

edited

github-actions bot commented Apr 29, 2024 •

edited