Hi and welcome. It looks like you've already done quite a bit of
research on the state of things. I don't have anything to add there.
It is quite likely that a good portion of the project would be
implementing prerequisites for the algorithm, but this is fine.
To answer your question about mentors, not all projects have mentors
listed on the ideas page, but we do have people who can mentor them.
Aaron Meurer
On Tue, Feb 25, 2020 at 9:36 AM Loh Yi Fong <lohyif...@gmail.com> wrote:
>
> 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 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 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)
> - 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.
--
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/CAKgW%3D6Loh93B%3DbznQ31G0gKe_yVO1KVJSpPHT27%3D_gA8TcD%2B-A%40mail.gmail.com.
