polys: make ANP use DMP internally #25764

oscarbenjamin · 2023-10-06T00:10:57Z

References to other Issues or PRs

Followup from gh-25722

Brief description of what is fixed or changed

Make the ANP class that is used for algebraic numberfields use DMP internally. This means that ANP can automatically benefit from any speedups in DMP that arise from using e.g. Flint rather than the existing dmp_* functions.

Other comments

The same should also be done for DMF.

Release Notes

(I will add a release note later)

polys
- The ANP class which is used to represent elements of an algebraic field is now built on top of the DMP class which is used to represent dense polynomials. This means that algebraic number fields like QQ<sqrt(2)> can benefit from the speed improvements of python-flint when the ground types are set to flint.

sympy-bot · 2023-10-06T00:11:04Z

✅

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
- The ANP class which is used to represent elements of an algebraic field is now built on top of the DMP class which is used to represent dense polynomials. This means that algebraic number fields like QQ<sqrt(2)> can benefit from the speed improvements of python-flint when the ground types are set to flint. (#25764 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. -->

Followup from gh-25722

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

Make the ANP class that is used for algebraic numberfields use DMP internally. This means that ANP can automatically benefit from any speedups in DMP that arise from using e.g. Flint rather than the existing `dmp_*` functions.

#### Other comments

The same should also be done for `DMF`.

#### 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. -->

(I will add a release note later)

<!-- BEGIN RELEASE NOTES -->
* polys
    * The ANP class which is used to represent elements of an algebraic field is now built on top of the DMP class which is used to represent dense polynomials. This means that algebraic number fields like `QQ<sqrt(2)>` can benefit from the speed improvements of python-flint when the ground types are set to flint.
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

sylee957 · 2023-10-06T17:38:34Z

sympy/polys/polyclasses.py

+    @property
+    def rep(self):
+        raise RuntimeError("ANP.rep")
+        return self._rep.to_list()
+
+    @property
+    def mod(self):
+        raise RuntimeError("ANP.mod")
+        return self._mod.to_list()


This always raise errors. Are you leaving this because this is part of some incomplete work?

It is incomplete. I haven't decided whether or not to deprecate these. The rep attribute can be replaced with .to_list() just like for DMP. The mod argument does not have an existing replacement. It is perhaps also not too important to deprecate them but I do want to make sure that they aren't use within the sympy codebase itself.

I think that although keeping the rep, dom as list is backward compatible, I don't think that it is more useful than using instance of DMP directly.

I guess at least there should be new public methods/attributes to get the rep and mod as DMP.

github-actions · 2023-10-06T20:04:10Z

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 [8059df73] <sympy-1.12^0>   | After [3bb2ebda]    |   Ratio | Benchmark (Parameter)                                                |
|----------|------------------------------------|---------------------|---------|----------------------------------------------------------------------|
| -        | 86.4±2ms                           | 56.7±0.1ms          |    0.66 | integrate.TimeIntegrationRisch02.time_doit(10)                       |
| -        | 86.0±2ms                           | 55.9±0.4ms          |    0.65 | integrate.TimeIntegrationRisch02.time_doit_risch(10)                 |
| +        | 22.2±0.07μs                        | 35.0±0.05μs         |    1.58 | integrate.TimeIntegrationRisch03.time_doit(1)                        |
| -        | 6.97±0.02ms                        | 3.77±0.01ms         |    0.54 | logic.LogicSuite.time_load_file                                      |
| -        | 2.12±0ms                           | 656±2μs             |    0.31 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'sparse')          |
| -        | 10.4±0.01ms                        | 1.96±0ms            |    0.19 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'sparse')          |
| -        | 368±0.5μs                          | 82.2±0.2μs          |    0.22 | polys.TimePREM_QuadraticNonMonicGCD.time_op(1, 'sparse')             |
| -        | 4.91±0.01ms                        | 365±1μs             |    0.07 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'sparse')             |
| -        | 10.7±0.04ms                        | 1.10±0ms            |    0.1  | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'sparse')             |
| -        | 6.27±0.01ms                        | 3.96±0.01ms         |    0.63 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(2, 'sparse') |
| -        | 27.4±0.04ms                        | 12.1±0.04ms         |    0.44 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'sparse') |
| -        | 6.94±0.03ms                        | 1.17±0.01ms         |    0.17 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(1, 'sparse')    |
| -        | 16.3±0.03ms                        | 9.23±0.01ms         |    0.57 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(2, 'sparse')    |
| -        | 214±0.3ms                          | 70.7±0.1ms          |    0.33 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'sparse')    |
| -        | 6.44±0.02ms                        | 535±1μs             |    0.08 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'sparse')     |
| -        | 28.2±0.06ms                        | 856±2μs             |    0.03 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'sparse')     |
| -        | 614±3μs                            | 199±0.6μs           |    0.32 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(1, 'sparse') |
| -        | 6.58±0.01ms                        | 202±1μs             |    0.03 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'sparse') |
| -        | 17.3±0.01ms                        | 209±5μs             |    0.01 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'sparse') |
| -        | 164±0.7μs                          | 89.0±0.1μs          |    0.54 | solve.TimeMatrixOperations.time_rref(3, 0)                           |
| -        | 316±0.3μs                          | 108±0.2μs           |    0.34 | solve.TimeMatrixOperations.time_rref(4, 0)                           |
| -        | 32.2±0.2ms                         | 13.5±0.01ms         |    0.42 | solve.TimeSolveLinSys189x49.time_solve_lin_sys                       |

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

oscarbenjamin · 2023-10-06T21:30:50Z

Current state:

$ cat t.py 
from sympy import *

N = 20

M = randMatrix(N) + randMatrix(N)*sqrt(2) + randMatrix(N)*sqrt(3) + randMatrix(N)*sqrt(5)

dM = M.to_DM(extension=True)

dM.inv()

$ time python t.py

real	0m38.798s
user	0m38.550s
sys	0m0.214s

$ time SYMPY_GROUND_TYPES=flint python t.py

real	0m2.179s
user	0m2.013s
sys	0m0.170s

More can be done to improve that but maybe for now this is good enough in terms of basic speed. Profiles suggest that most of the time is spent in python-flint rather than in overheads in the Python code so big speed improvements would need to be from a change of algorithm rather than micro-optimisation (at least for the things I have tested).

oscarbenjamin · 2023-10-07T11:45:49Z

I've optimised some of the ANP methods a bit more.

This is without flint:

In [2]: cat t.py
from sympy import *

from time import time

def rand(N):
    M = (
        randMatrix(N)
        + randMatrix(N)*sqrt(2)
        + randMatrix(N)*sqrt(3)
        + randMatrix(N)*sqrt(5)
        + randMatrix(N)*sqrt(7)
        + randMatrix(N)*sqrt(11)
    )
    return M.to_DM(extension=True)

In [3]: run t.py

In [4]: for n in range(1, 5):
   ...:     dM = rand(n)
   ...:     start = time()
   ...:     dM.inv()
   ...:     time_taken = time() - start
   ...:     print(f'{n}x{n} matrix: {time_taken:.3g} seconds')
   ...: 
1x1 matrix: 0.193 seconds
2x2 matrix: 2.39 seconds
3x3 matrix: 6.87 seconds
4x4 matrix: 18.1 seconds

This is with flint:

In [3]: for n in range(1, 10):
   ...:     dM = rand(n)
   ...:     start = time()
   ...:     dM.inv()
   ...:     time_taken = time() - start
   ...:     print(f'{n}x{n} matrix: {time_taken:.3g} seconds')
   ...: 
1x1 matrix: 0.00954 seconds
2x2 matrix: 0.0395 seconds
3x3 matrix: 0.106 seconds
4x4 matrix: 0.218 seconds
5x5 matrix: 0.406 seconds
6x6 matrix: 0.679 seconds
7x7 matrix: 1.11 seconds
8x8 matrix: 1.61 seconds
9x9 matrix: 2.27 seconds

This is about 100x faster for a 4x4 matrix but the difference increases for larger sizes.

oscarbenjamin · 2023-10-07T11:50:00Z

I noticed while timing this that primitive_element still internally uses dup_zz_factor rather than using flint for the factorisation. This is because it factorises polynomials over e.g. QQ<sqrt(2)> which will follow the existing dmp_* functions and at the bottom they end up calling dup_zz_factor. It should be changed so that some lower level functions like dup_zz_factor call out to Flint.

oscarbenjamin · 2023-10-07T19:27:12Z

I think that the main thing missing here is just to add public methods for getting rep and mod as DMP rather than as lists.

oscarbenjamin · 2023-10-07T21:59:53Z

This is now ready for review

jksuom · 2023-10-08T07:57:59Z

Looks good.

oscarbenjamin · 2023-10-08T10:42:17Z

Thanks!

polys: make ANP use DMP internally

fb91f62

oscarbenjamin added polys Performance labels Oct 6, 2023

oscarbenjamin marked this pull request as draft October 6, 2023 00:39

sylee957 reviewed Oct 6, 2023

View reviewed changes

Add back ANP.rep and ANP.mod

685846e

oscarbenjamin added 2 commits October 6, 2023 22:15

perf: optimise some ANP/DMP methods

646ac83

flake8: remove unneeded imports

c27937d

oscarbenjamin added 3 commits October 6, 2023 22:36

Don't try to use fmpz_poly.xgcd

c44398f

Use __reduce__ for pickling DMP etc

7c52b21

perf: optimise some ANP methods

7d1840e

polys: use Flint in dup_zz_factor

d8edaab

polys: Add ANP methods to_DMP, mod_to_DMP and mod_to_list

6b7a0fe

oscarbenjamin marked this pull request as ready for review October 7, 2023 21:59

jksuom merged commit 368eb0f into sympy:master Oct 8, 2023

oscarbenjamin deleted the pr_anp_dmp branch October 8, 2023 10:42

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

polys: make ANP use DMP internally #25764

polys: make ANP use DMP internally #25764

Uh oh!

oscarbenjamin commented Oct 6, 2023 •

edited

Loading

Uh oh!

sympy-bot commented Oct 6, 2023 •

edited

Loading

Uh oh!

sylee957 Oct 6, 2023

Uh oh!

oscarbenjamin Oct 6, 2023

Uh oh!

sylee957 Oct 6, 2023

Uh oh!

oscarbenjamin Oct 6, 2023

Uh oh!

github-actions bot commented Oct 6, 2023 •

edited

Loading

Uh oh!

oscarbenjamin commented Oct 6, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023 •

edited

Loading

Uh oh!

jksuom commented Oct 8, 2023

Uh oh!

oscarbenjamin commented Oct 8, 2023

Uh oh!

Uh oh!

Uh oh!

polys: make ANP use DMP internally #25764

polys: make ANP use DMP internally #25764

Uh oh!

Conversation

oscarbenjamin commented Oct 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

References to other Issues or PRs

Brief description of what is fixed or changed

Other comments

Release Notes

Uh oh!

sympy-bot commented Oct 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sylee957 Oct 6, 2023

Choose a reason for hiding this comment

Uh oh!

oscarbenjamin Oct 6, 2023

Choose a reason for hiding this comment

Uh oh!

sylee957 Oct 6, 2023

Choose a reason for hiding this comment

Uh oh!

oscarbenjamin Oct 6, 2023

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented Oct 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oscarbenjamin commented Oct 6, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023

Uh oh!

oscarbenjamin commented Oct 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jksuom commented Oct 8, 2023

Uh oh!

oscarbenjamin commented Oct 8, 2023

Uh oh!

Uh oh!

oscarbenjamin commented Oct 6, 2023 •

edited

Loading

sympy-bot commented Oct 6, 2023 •

edited

Loading

github-actions bot commented Oct 6, 2023 •

edited

Loading

oscarbenjamin commented Oct 7, 2023 •

edited

Loading