GSoC 2025: Cylindrical algebraic decomposition
Alex Garcia
Hello to the entire SymPy community!
My name is Alejandro García Prada, and I am a third-year student pursuing a Double Degree in Mathematics and Software Engineering at Universidad Rey Juan Carlos in Madrid, Spain.
I am interested in the Cylindrical Algebraic Decomposition (CAD) project. I have been studying the topic for several weeks through the references listed on the ideas page, and I have also read with interest the existing PRs related to it. From what I’ve seen, CAD is an algorithm with doubly exponential worst-case complexity. However, there are several approaches to reduce this algorithmic complexity. One of them is using the Hong projection operator, for which there is already an open PR: https://github.com/sympy/sympy/pull/26785.
I would like to know the current status of this algorithm. As far as I understand, the two main PRs currently related to this topic are the one mentioned above and this one, which deals with computing subresultants that could be used for the CAD algorithm: https://github.com/sympy/sympy/pull/27088.
Do you think a good approach to developing this idea would be to continue working from the code by mmaaz-git (author of the mentioned PRs), or would it be better to start from scratch? Are there any additional PRs or SymPy modules that you consider essential to be familiar with in order to take on this project?
Finally, I would like to mention that I have also read about some improvements to the algorithm, such as TTICAD, which are detailed in the following document: https://davidjohnwilson.github.io/publications/djwthesis.pdf. While it may not be applicable in all cases, it helps avoid some unnecessary decompositions in certain situations.
Thank you very much in advance. I truly appreciate any feedback, additional guidance, or corrections.
Best regards,
Alejandro
Alex Garcia
Hello again to the entire Sympy community!
First of all, sorry for writing again—I know these days, with the opening of proposals for GSoC 2025, you must be swamped with work. But I’m afraid my previous email may not have reached the right people. I’d like to know if anyone knows who I should reach out to in order to discuss the aspects of cylindrical algebraic decomposition that I mentioned in my previous email.
Thank you very much in advance,
Alejandro
Oscar Benjamin
Yes, we would still like to have CAD. I believe the work on it has
stalled probably because mmaaz-git is busy with other things. I think
a first step would be to try to finish the PR that did not get merged
by taking the commits from there, rebasing them to current master, and
then opening a new PR.
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 visit https://groups.google.com/d/msgid/sympy/c476062e-2773-43ff-a2ce-d4ca35e0f0b6n%40googlegroups.com.