Bridging FLINT and SymPy for Polynomial GCD Computation
Aasim
Hey everyone!
I'm looking for help with a recent venture I'm planning to embark on.
I have been working on the SymPy codebase for about 6 months now. And my major contributions there have revolved around the solvers and polys modules which are for "solving systems of equations" and "manipulating polynomials" respectively.
Now the issue that has persisted for some time is the slowness of polynomial GCD computation in SymPy. And it slows down a lot of things under the hood consequently.
So, what I wanna do is, or at least take a significant step towards, is the bridging of FLINT and SymPy, since FLINT has its optimized C routines for GCD computation of both dense and sparse representations of polynomials over the integers i.e. ZZ and over the rationals i.e. QQ coefficient domains. SymPy has to work with more complicated domains than ZZ and QQ though,
BUT,
any implementation or GCD computation algorithms that can reduce to cases that are well handled (or rather I should say very well handled) by FLINT will make things immensely faster for SymPy.
Like, for example, it's not very difficult to reduce a polynomial system defined over ZZ_I to ZZ in SymPy, all we have to do is promote the imaginary unit 'I' to the generators as a symbol(jargon for variable in SymPy) and adjoin the minimal polynomial i.e. i**2 + 1 to the system.
Currently, in SymPy, the strategy for computing the GCD of sparse polynomials depends on the coefficient domain:
If the domain is ZZ, the heuristic polynomial GCD algorithm (HEUGCD) is used directly.
If the domain is QQ, denominators are cleared to reduce the polynomials to ZZ, and then HEUGCD is applied.
Otherwise, the dense implementation of the PRS (Polynomial Remainder Sequence) algorithm is used.
However, there are some inefficiencies with this approach:
HEUGCD may not be the best choice, even when working over ZZ.
The dense PRS implementation struggles when there are many generators because it applies itself recursively over multiple nested lists, leading to inefficiencies.
There have been mentions and discussions about how this bridging is pretty useful and a high priority. As of now, FLINT is alien to me since I’ve not had much experience using it unlike SymPy(reason why I came here looking for help).
I’d appreciate any guidance on how to initiate this integration. Are there existing approaches or recommendations for linking SymPy’s polynomial arithmetic with FLINT’s capabilities? Additionally, what would be a good roadmap for incrementally working toward this goal?
SymPy can really benefit from addition of modular GCD algorithms, especially with this bridging with FLINT where the algorithms that reduce to cases well handled by FLINT.
I’ve tried to keep this mail concise and not crowd it up, if you've read this far, I really appreciate it.
Eagerly looking forward to your insights!
Aasim
Oscar Benjamin
It would be better to ask about this on the SymPy mailing list or
otherwise in a SymPy or python-flint GitHub issue:
https://github.com/flintlib/python-flint
The current situation is that SymPy will use FLINT via python-flint
for univariate polynomials over ZZ, QQ or GF(p) and so in that
situation FLINT's GCD implementation is used:
In [6]: p1 = Poly(x**2 - 1)
In [7]: p2 = Poly(x + 1)
In [8]: p1.rep
Out[8]: DUP_Flint([1, 0, -1], ZZ)
In [9]: p1.rep._rep
Out[9]: x^2 + (-1)
In [10]: type(_)
Out[10]: flint.types.fmpz_poly.fmpz_poly
In [11]: p1.gcd(p2) # uses FLINT internally
Out[11]: Poly(x + 1, x, domain='ZZ')
Recent work by Jake Moss on python-flint added wrapper types to expose
FLINT's multivariate polynomials:
In [16]: R = flint.fmpz_mpoly_ctx.get(['x', 'y'])
In [17]: x, y = R.gens()
In [18]: p1 = x**2 - y**2
In [19]: p2 = x - y
In [20]: p1.gcd(p2)
Out[20]: x - y
These multivariate polynomials are not used by SymPy yet though.
Integrating those into SymPy would make it possible to use FLINT for
multivariate GCD calculations. That would make many things faster
since typically GCD calculations in SymPy involve multivariate
polynomials.
Oscar
>
> ---
> You received this message because you are subscribed to the Google Groups "flint-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
> To view this discussion, visit https://groups.google.com/d/msgid/flint-devel/b72e3f23-79a2-45ce-ba9e-acb1464d3845n%40googlegroups.com.
Aasim
I'm gonna be sending a corresponding mail on the SymPy mailing list soon. I truly hope to see you there.
Also, I couldn't replicate the output you showed above; Are you using some unreleased version of python-flint ? I'm using 0.6.0 which has no "get" attribute for flint.fmpz_mpoly_ctx.
Once again, thank you.
To view this discussion, visit https://groups.google.com/d/msgid/flint-devel/CAHVvXxTSV8ydux9ycL8jYCbg4mTr2g%3Dfm8Dfg49eW1tmLxho%3DQ%40mail.gmail.com.