SymPy, Flint, and sparse polynomial representations

[Jake Moss]

Hi,

I'm looking at SymPy and Flint, and their sparse polynomial representations under the direction of my supervisor for an Honours thesis at the University of Queensland, Australia and I was wondering about the status of the existing integrations of Flint and recommendations from Oscar Benjamin's blog posts.

I've seen that SymPy is now able to use Flint as the ground type for dense univariate polynomials from PR #25722. Is there a similar PR for multivariate polynomials? I haven't seen one myself but perhaps it is hiding from me. I assume any integration work is pending the merging of Adding Fmpz mpoly #59 on python-flint. Is this PR blocked?

Additionally is there any on going work on the sparse polynomial representations? From the existing PRs and Flints documentation I've only been able to find mention of sparsity in the gr_mpoly_t section, which is not mentioned in any of the pending PRs that I've seen.

Is this type of work of interest? If it is I'd be happy to pick up the Fmpz mpoly python-flint PR and work on integrating that into SymPy. I have plenty of (painful) experience with Cython and integrating it with existing C and Python libraries from my day job.

As this would be part of a year long thesis I'd also be interested in there are any more research-y type questions in this area. I'm currently considering an analysis of SymPys existing systems and comparison to Flints along side some profiling and investigation into Flints cache efficiency and current areas for improvement from a HPC side but am open to other ideas.

As for a bit about myself I'm a Computer Science Honours student in my 5th year with Bachelors in Mathematics and Computer Science. I write high-performance Cython modules for my work and am generally interested in everything performance related. I have experience on both sides of C and Python.

Regards,
Jake Moss

[Oscar Benjamin]

On Mon, 11 Mar 2024 at 13:06, Jake Moss <jake...@uqconnect.edu.au> wrote:
>
> Hi,

Hi Jake,

> I'm looking at SymPy and Flint, and their sparse polynomial representations under the direction of my supervisor for an Honours thesis at the University of Queensland, Australia and I was wondering about the status of the existing integrations of Flint and recommendations from Oscar Benjamin's blog posts.

That would be fantastic.

> I've seen that SymPy is now able to use Flint as the ground type for dense univariate polynomials from PR #25722. Is there a similar PR for multivariate polynomials? I haven't seen one myself but perhaps it is hiding from me. I assume any integration work is pending the merging of Adding Fmpz mpoly #59 on python-flint. Is this PR blocked?

The current status is that SymPy can use Flint for:

- The ground domains ZZ, QQ and GF(p).
- Dense univariate polynomials over ZZ, QQ.
- Dense matrices over ZZ and QQ.
- Dense rational functions over ZZ and QQ.
- Algebraic number fields like QQ(sqrt(2)).

There is a PR to use of Flint for polynomials and matrices over GF(p)
here for which I am waiting review:

https://github.com/sympy/sympy/pull/25940

Currently python-flint does not expose any of Flint's multivariate
polynomial types so it is not possible for SymPy to use them yet. The
PR that you have identified is by David Einstein:

https://github.com/flintlib/python-flint/pull/59

The PR is not blocked. I think that David just has not found the time
to complete it yet. I have been intending to take over when I could
find time. Don't let either of us stop you if you want to have a go at
it though. I am sure that David won't mind (although best to mention
something on the PR if you are going to start work on it).

> Additionally is there any on going work on the sparse polynomial representations? From the existing PRs and Flints documentation I've only been able to find mention of sparsity in the gr_mpoly_t section, which is not mentioned in any of the pending PRs that I've seen.

Perhaps "sparse" is the wrong term to use here. In SymPy there are
sparse and dense polynomial representations. The corresponding Flint
types are called fmpz_mpoly etc with m for "multivariate". The
intention would be to use Flint's multivariate polynomials in SymPy in
place of SymPy's sparse and dense multivariate polynomials.

Specifically there are two wrapper classes that I would want to have
to adapt the Flint types at different levels within SymPy:

One would be an analogue of the DUP_Flint type which is for Flint's
univariate polynomials to have something like DMP_Flint for
multivariate polynomials (see sympy/polys/polyclasses.py). These would
be used by SymPy's Poly as the internal type when the domain is
something that is supported by python-flint (currently ZZ, QQ or
GF(p)).

The other place we would want to use Flint's mpoly types is for
polynomial ring domains like QQ[x,y] etc. In this case we would want a
wrapper class that provides an interface that is compatible with
SymPy's PolyElement type. Then SymPy could make use of Flint at the
domain level as well as the Poly level.

That would be the simplest way for SymPy to use python-flint's
multivariate polynomials. Longer term it might be better to have a
general refactor of all of this code to make it more suitable for a
design that can swap Flint in and out.

> Is this type of work of interest? If it is I'd be happy to pick up the Fmpz mpoly python-flint PR and work on integrating that into SymPy. I have plenty of (painful) experience with Cython and integrating it with existing C and Python libraries from my day job.

Yes, this is absolutely of interest. I agree that Cython is sometimes painful...

> As this would be part of a year long thesis I'd also be interested in there are any more research-y type questions in this area. I'm currently considering an analysis of SymPys existing systems and comparison to Flints along side some profiling and investigation into Flints cache efficiency and current areas for improvement from a HPC side but am open to other ideas.

There are all sorts of things that could be done here both in terms of
implementation and research. There are many more things in Flint that
are not exposed in python-flint and there are many more parts of SymPy
that would be improved by making more use of domains, Poly etc.

Once SymPy has Flint's multivariate polynomials for the polynomial
domains that means that SymPy's DomainMatrix will use Flint for
matrices with polynomial or rational functions entries. Most
algorithms for Matrix and DomainMatrix can be reworked and there is
plenty to explore in terms of best algorithms, benchmarking etc.

Another thing that SymPy should do is build a new implementation of
algebraic number fields based on multivariate polynomials and Groebner
bases rather than univariate polynomials and primitive elements.
Similar approaches can be used to handle things like QQ[sin(x),cos(x)]
which are not currently handled by the domain system.

Also Flint has algebraic number fields that are not currently exposed
in python-flint.

> As for a bit about myself I'm a Computer Science Honours student in my 5th year with Bachelors in Mathematics and Computer Science. I write high-performance Cython modules for my work and am generally interested in everything performance related. I have experience on both sides of C and Python.

Sounds like perfect experience for this sort of work!

Oscar

[Jake Moss]

Thank you for such a detailed reply! Seems like there will be plenty for me to do.

I'll reach out to David Einstein on GitHub later this week after meeting with my supervisor and solidifying a plan of sorts.

Regards,
Jake

[Oscar Benjamin]

Hi Jake,

I would be happy to meet (online) with you and your supervisor at some
point if that helps.

Oscar

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d2d2835c-5da5-42af-9fbf-3d17cca6854bn%40googlegroups.com.

[Jake Moss]

Hi Oscar,

Thank you very much for that offer. I may reach out in a couple weeks to organise something but I'll let you know off mailing list.

Regards,
Jake