Hi Maaz, This sounds like an excellent addition to SymPy.
There was also a recent GitHub issue that discussed a more limited form of CAD: https://github.com/sympy/sympy/issues/26177 The implementations there are based on this paper by Strzebonski: https://core.ac.uk/download/pdf/82649664.pdf There are many different things that a CAD (or GCAD) would be useful for so there are likely a number of different interfaces that it would be good to provide. If you send your code as a pull request then it will be easier to discuss it. Alternatively if the method is similar to the one discussed in gh-26177 then you could discuss it there or open a new issue to discuss it. One thing that SymPy currently lacks is a way to get the roots of a polynomial with irrational algebraic coefficients in RootOf form: https://github.com/sympy/sympy/issues/22943 In general that is needed to be able to represent points in the non-full-dimensional cells. -- Oscar On Tue, 2 Jul 2024 at 23:22, Maaz Muhammad <mmaaz6...@gmail.com> wrote: > Hi all! I'm a PhD student at the University of Toronto, working on > polynomials (optimization, algorithms, and applications). > > As part of my work, I needed to solve systems of polynomials (inequalities > and equalities), which SymPy currently lacks. I have therefore been working > on such a solver for SymPy. The standard algorithm for this is *cylindrical > algebraic decomposition, *which decomposes R^n into "cells" over which > each polynomial is sign-invariant. You can then evaluate the system in each > cell, which allows you to either get a satisfying point (or, a satisfying > point from each true cell), or the algorithm returns that the system is > inconsistent. Here is a demo of my code: > > [image: No description available.] > > The implementation here returns a single satisfying point if it exists, > and otherwise returns an empty list if no satisfying point exists. > > The algorithm relies heavily on the *Hong projection operator*. This was > really the main thing I had to code. The Hong operator relies on taking > resultants, reducta, and derivatives -- all of which can already be done in > SymPy, so it was just a matter of putting it together (after understanding > Hong's paper). > > I previously posted this on my Twitter and was asked by the SymPy Twitter > account to post here. I would love to make this part of SymPy. Note that > thus far, the only two implementations of CAD are in Mathematica or a > software called QEPCAD. > > For now, the algorithm works with sample points from each cell (these > sample points are generated during the running of the algorithm). I'm > thinking that the poly_solve() function could have a parameter like > 'return_type' which can take values either 'one' or 'all' -- the former > would return a satisfying point from a single cell, the latter would return > a satisfying point from all valid cells. > > Another consideration is that CAD can also be used to construct algebraic > formulas that describe all satisfying points. This is called the *solution > formula*. Mathematica and QEPCAD implement this. Unfortunately, this step > is quite challenging, and I have not fully understood it yet. Pretty much > all the information about this step is given in a PhD thesis from the 90s > by Christopher Brown (who actually wrote QEPCAD). I'm studying it right now. > > Overall, I have the following questions: > 1. What would be the process to integrate this algorithm into SymPy? > 2. Should I wait until I figure out the solution formula step to try to > integrate into SymPy? > 3. Are there any rules about me eventually writing a paper about my > implementation in, for example, the INFORMS Journal of Computing ( > https://pubsonline.informs.org/page/ijoc/editorial-statement#Software%20Tools > )? > > Thanks! > > -- > 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+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/d6688cc4-1e09-49fe-800e-a16e3f9e8ba4n%40googlegroups.com > <https://groups.google.com/d/msgid/sympy/d6688cc4-1e09-49fe-800e-a16e3f9e8ba4n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAHVvXxRiMimEV_P-yUhSVOSzo13Sa147gdZxOk%3DxJStzLK0TeQ%40mail.gmail.com.
