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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/c073724e-c86f-4674-bad7-1e494911d5f4%40googlegroups.com.
