Hello new friends, My name is Yi Fong, I'm from Singapore reading Pure Mathematics ('BSc mathematical sciences') at Nanyang Technological University (2nd year). I first came over with the wave of GSoC applicants of 2020 and I am most intrigued at the possibility of doing a project on Cylindrical Algebraic Decomposition (CAD) algorithm over summer and more. (Since I foresee might extend over the scope of summer due to the possible scope involved!)
I was first drawn into this topic by observing similarities to my existing interests in mathematics. I am currently reading, in my ongoing semester: Set Theory, Ordinary Differential Equations, Abstract Algebra, Real Analysis, Numerical Analysis and have read last semester (with especial interest): First order logic and Computability Theory as a supervised independent study. (I will read further Analysis, Algebra and topology the next semester as well.) To me it is interesting how CAD builds on familiar logical constructs such as the well-known Quantifier Elimination to CAD which can solve multi-variate polynomial inequalities amongst other things. Having had my first course in First Order / Mathematical Logic up to Godel's Theorem, I am interested in studying further consequences within (or building on) this area towards a Final Year Project or possibly graduate study. The opportunity to implement CAD with mentorship could hence be part of an exciting exploration whether through logic or mathematics more generally. In terms of computer science, I am self-schooled and most fluent in Python (for 5 years counting; with my first formal course in introductory CS courses in 2018). I use Debian, vim, latex and markdown on a daily basis but I don't make git commits often due to spending more time on mathematics. I code when I'm on little projects: a project involving micropython and image processing last summer, the suite of scientific python libraries, reportlab (pdf generation), mathematical algorithms for a research project and making my own little scripts. However, I have never coded for a large library before and I am keen to join the community in contributing and maintaining our open source libraries (in python) at an excellent standard! For the rest of my post I aim to at least correctly recapitulate the progress on CAD in SymPy and further progress for any interested party! I noticed that the CAD algorithm has been a project on and off on the GSoC Ideas list since early 2010s. A compilation of posts are as follows (appreciate further contributors!). - Past GSoC Applicants with CAD - https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Prateek-Papriwal:-Cylindrical-Algebraic-Decomposition - https://groups.google.com/forum/#!searchin/sympy/CAD|sort:date/sympy/8DtAK-pSECk/ibSsp4i7DQEJ - https://github.com/sympy/sympy/wiki/GSoC-2015-Application-Luv-Agarwal:-Cylindrical-Algebraic-Decomposition - https://groups.google.com/forum/#!searchin/sympy/%22Luv$20Agarwal%22%7Csort:date/sympy/Ujznd13xfgw/w_X8M2RDbyMJ - https://groups.google.com/forum/#!topic/sympy/p-PcoCJMiN0 - 2016; discussion Related - Sagemath <http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html> documentation for interface to QEPCAD >From what I gather, there are a number of reasons that CAD has not been developed in SymPy: - If there are issues with the polynomial solvers, these will cause problems for CAD downstream. - For instance, "currently" (from what I saw here <https://groups.google.com/forum/#!topic/sympy/p-PcoCJMiN0> from 2016), the implementation of real_roots only supports integer or rational coefficients - But the CAD algorithm may requiring recursing through polynomials with algebraic (and not just integer or rational) coefficients. - Any CAD implementation on sympy hence requires algebraic number coefficient polynomials to be solvable. - Historically, the Symbolic Computation community and the satisfiability (SAT)/ satisfiability modulo theories (SMT) tend to work / be studied as separate communities - (above claim from 2018; Matthew England from Coventry U summer school slides <http://www.cs.man.ac.uk/~regerg/ssa/MEngland-CAD-SummerSchool2018.pdf>) - There are few open sourced CAD implementations (see references below) - closed source ones like mathematica and maple - I am not sure if building CAD requires improving or developing SymPy's ability to handle first order logic ("FOL") - Some open pull requests (PRs) for First Order Logic in SymPy - https://github.com/sympy/sympy/pull/7608 - https://github.com/sympy/sympy/pull/17069 - In addition to the papers listed on the GSoC page, I am planning to read the following papers which I believe would be helpful for any interested party: - Mahboubi, Assia. "Implementing the cylindrical algebraic decomposition within the Coq system." Mathematical Structures in Computer Science 17, no. 1 (2007): 99-127. - interactive theorem prover; (see: the "historical separation" from CAS systems; which I don't really understand why exactly yet). - Geletka, Martin. "Implementation of Cylindrical Algebraic Sub-decomposition" (2019). Masaryk University Bachelor's Thesis. - Helpful; JVM implementation on Gitlab (see paper). - QEPCAD (best known open source implementation); can be interfaced through SageMath In any case, I really hope to work with you guys in time to come, gsoc or not. Also; since there is no suggested mentor listed on the GSoC page, is there anyone who would like to make CAD 2020 happen! Perhaps I could try next year as well, but I think there are some algorithmic choices to be made in CAD that must be agreed on as a community since there's decisions of how it should/could build on the existing code base / the variant of the CAD algorithm. Appreciate all comments if my understanding of the situation is wrong, should be supplemented, and so on. Hope to make some pull request by next week or so and look forward to the constructive feedback on where CAD can be picked up from (which I am most keen but also open to other projects for now if it's too immature / large a project to try). Excuse my naivety and cheers! Best, Yi Fong -- 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/c073724e-c86f-4674-bad7-1e494911d5f4%40googlegroups.com.