GSoC 2022: Cylindrical Algebraic Decomposition

[كاي‎]

Hi All,

Hope everyone is doing well.

My name is Kai, I'm a 2nd year undergraduate student studying computer sceince and mathematics at The University of Manchester. I have experience developing open source software and have completed a number of projects in Python and Java programming languages. 

I would be interested in implementing the cylindrical algebraic decomposition algorithm in SymPy over the course of this program, and I am currently writing my proposal for doing so.

Do you know who is mentoring this topic and whether it would be okay to speak with them about some questions I had?

Many Thanks

Kai

[Aaron Meurer]

It's best to just post your questions here.

Aaron Meurer

>
> Many Thanks
> Kai
>
> --
> 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 on the web visit https://groups.google.com/d/msgid/sympy/8f16ab8b-e83b-41f0-bb6c-9348d4900bdan%40googlegroups.com.

[Oscar Benjamin]

‪On Sun, 10 Apr 2022 at 01:46, 'كاي' via sympy <sy...@googlegroups.com> wrote:‬
>
> I would be interested in implementing the cylindrical algebraic decomposition algorithm in SymPy over the course of this program, and I am currently writing my proposal for doing so.

I think implementing CAD itself is way too much for a single project.
The preliminary work needed before someone can even begin to implement
this would probably make multiple projects. If you break that down
then it should be possible to propose something that is achievable.

SymPy does not currently have solvers for linear systems of
inequalities over the reals or integers. Implementing those along with
making use of them as part of other solvers or the assumptions system
is plenty enough work for a single project.

--
Oscar

[كاي‎]

Hi Oscar,

Thanks for the advice, I am looking to prompty begin condensing my proposal and making contributions to the SymPy codebase.

To eliminate some confusion, would you be able to explain how a solver for a linear system of inequalities would be integrated into the CAD algorithm, as from my understanding, we can input a linear system into the CAD and it would output cells from which we can easily determine the solution set of the system?

Essentially this would be doing the same thing twice, or am I mistaken - could this solver be a prerequiasite check to see if the system has a solution before applying the CAD?

Furthermore, can you reccommend which part of this project/idea would be suitable for my first contribution to SymPy, this will also be my patch requirement for GSoC, I was thinking maybe a data structure to hold the set of polynomial inequlaities but it would be great to hear your thoughts first?

Also can you kindly explain a little more about what you meant by assumptions system in your previous reply?

Thanks again

Best Wishes

Kai

[Oscar Benjamin]

‪On Sun, 10 Apr 2022 at 16:40, 'كاي' via sympy <sy...@googlegroups.com> wrote:‬
>
> Hi Oscar,
>
> Thanks for the advice, I am looking to prompty begin condensing my proposal and making contributions to the SymPy codebase.
>
> To eliminate some confusion, would you be able to explain how a solver for a linear system of inequalities would be integrated into the CAD algorithm, as from my understanding, we can input a linear system into the CAD and it would output cells from which we can easily determine the solution set of the system?
>
> Essentially this would be doing the same thing twice, or am I mistaken - could this solver be a prerequiasite check to see if the system has a solution before applying the CAD?

Essentially CAD is a method for solving systems of polynomial
inequalities in multiple real variables. Simpler methods exist for
solving systems of linear inequalities but those are not yet
implemented in SymPy. Adding solvers for linear inequalities would be
much easier and would have immediate applicability. Even if SymPy had
CAD it would not make sense to use it for linear inequalities where
more efficient methods exist.

> Furthermore, can you reccommend which part of this project/idea would be suitable for my first contribution to SymPy, this will also be my patch requirement for GSoC, I was thinking maybe a data structure to hold the set of polynomial inequlaities but it would be great to hear your thoughts first?

I don't think it's worth adding a data structure for this. A list of
inequalities can already be represented easily. Linear systems of
inequalities are typically represented using matrices. Polynomial
systems can be represented just as lists of polynomials.

> Also can you kindly explain a little more about what you meant by assumptions system in your previous reply?

The point is that it would be good to be able to say something like
"assume x + y > 0 and x - y < 1" and then use that to simplify other
conditional expressions like Piecewise. Making this work means being
able to conclude that e.g. the given set of inequalities implies that
say "y > 0" or something. For that a solver for systems of
inequalities is needed.

--
Oscar

[Aaron Meurer]

‪On Sun, Apr 10, 2022 at 9:40 AM 'كاي' via sympy

<sy...@googlegroups.com> wrote:‬
>
> Hi Oscar,
>
> Thanks for the advice, I am looking to prompty begin condensing my proposal and making contributions to the SymPy codebase.
>
> To eliminate some confusion, would you be able to explain how a solver for a linear system of inequalities would be integrated into the CAD algorithm, as from my understanding, we can input a linear system into the CAD and it would output cells from which we can easily determine the solution set of the system?
>
> Essentially this would be doing the same thing twice, or am I mistaken - could this solver be a prerequiasite check to see if the system has a solution before applying the CAD?
>
> Furthermore, can you reccommend which part of this project/idea would be suitable for my first contribution to SymPy, this will also be my patch requirement for GSoC, I was thinking maybe a data structure to hold the set of polynomial inequlaities but it would be great to hear your thoughts first?

Your first contribution doesn't have to be directly related to your
project. Usually for the first PR I recommend just finding an issue
that you think you can fix, even if it is in a part of SymPy that is
unrelated to your project. Knowing how to contribute to an unrelated
part of SymPy will still teach you important thing like how to make a
PR, how to use git, how to respond to requests from reviews, the basic
layout of code style of the SymPy codebase, and so on.

Aaron Meurer

>
> Also can you kindly explain a little more about what you meant by assumptions system in your previous reply?
>
> Thanks again
>
> Best Wishes
> Kai
>
>
> On Sunday, April 10, 2022 at 12:01:06 PM UTC+1 Oscar wrote:
>>
>> ‪On Sun, 10 Apr 2022 at 01:46, 'كاي' via sympy <sy...@googlegroups.com> wrote:‬
>> >
>> > I would be interested in implementing the cylindrical algebraic decomposition algorithm in SymPy over the course of this program, and I am currently writing my proposal for doing so.
>>
>> I think implementing CAD itself is way too much for a single project.
>> The preliminary work needed before someone can even begin to implement
>> this would probably make multiple projects. If you break that down
>> then it should be possible to propose something that is achievable.
>>
>> SymPy does not currently have solvers for linear systems of
>> inequalities over the reals or integers. Implementing those along with
>> making use of them as part of other solvers or the assumptions system
>> is plenty enough work for a single project.
>>
>> --
>> 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 on the web visit https://groups.google.com/d/msgid/sympy/4385e126-efce-4a4b-97d8-87580de5f2b9n%40googlegroups.com.