FLINT-Backed Multivariate Polynomials in SymPy (GSoC'25 Proposal Review)

28 views

Skip to first unread message

Aasim

unread,

Apr 8, 2025, 4:33:23 PMApr 8

Hey everyone!

I've drafted my GSoC'25 proposal for implementing a backend for sparse and dense multivariate polynomials in SymPy using python-flint. It targets polynomials over ℤ and ℚ, leveraging FLINT’s multivariate polynomial support. I have been iteratively refining it since April 1st, I've now uploaded the complete version.

📄 Proposal Link: Copy of GSoC'25 Proposal Draft

The proposal primarily focuses on implementing:

A sparse multivariate distributed polynomial ring (FlintPolyRing)
Its elements (FlintPolyElement)
A new base class to DMP (DMP_Flint)

…along with corresponding tests, docs and benchmarks.

While prototyping for the proposal, I got some exciting results. For instance, using DMP.factor_list() on a large polynomial:

On master (using DMP_Python):

In [3]: p = Poly((x + y + z)**100*(x + y)*(y + z)*(z + x)) # A fairly huge polynomial

In [4]: type(p.rep) # On master where DMP_Python is used to build p

Out[4]: sympy.polys.polyclasses.DMP_Python

In [5]: %time p.rep.factor_list()

CPU times: user 4min 39s, sys: 1.18 s, total: 4min 40s

Wall time: 4min 40s

Out[5]:

(1,

[(DMP_Python([[[1], [1, 0]]], ZZ), 1),

(DMP_Python([[[1]], [[1], []]], ZZ), 1),

(DMP_Python([[[1]], [[1, 0]]], ZZ), 1),

(DMP_Python([[[1]], [[1], [1, 0]]], ZZ), 100)])

On my branch (with DMP_Flint):

In [3]: p = Poly((x + y + z)**100*(x + y)*(y + z)*(z + x)) # The same huge polynomial

In [4]: type(p.rep) # The branch where I introduced DMP_Flint

Out[4]: sympy.polys.polyclasses.DMP_Flint

In [5]: %time p.rep.factor_list()

CPU times: user 13 ms, sys: 0 ns, total: 13 ms

Wall time: 15.4 ms

Out[5]:

(1,

[(DMP_Flint([[[1], [1, 0]]], ZZ), 1),

(DMP_Flint([[[1]], [[1, 0]]], ZZ), 1),

(DMP_Flint([[[1]], [[1], []]], ZZ), 1),

(DMP_Flint([[[1]], [[1], [1, 0]]], ZZ), 100)])

Equivalent result, ~21,000× faster. Most importantly it’s mathematically correct. Similar improvements are observed for other operations like GCD, which are currently bottlenecks.

The proposal is now on my GSoC dashboard. As it's encouraged to shape it collaboratively with the org, I’d deeply appreciate any feedback or suggestions before the deadline hits today. I’ll make one last revision if I hear from you.