QEPCAD

[Ferran Pujol Camins]

Hello,
I represent a group of 6 students from the maths school (FME) of the Universitat Politècnica de Catalunya.
In one of our courses we have been assigned to the task of implementing QEPCAD in python using sympy. Our goal is to develop a module that can be merged into sympy.

We have just started, so our knowledge of QEPCAD and sympy is limited, but we expect to success in our goal by the end of the semester. We would really appreciate some help to get started.

• We have seen that QEPCAD was in a GSOC proposal. AFAIK, the proposal was not accepted or the project didn't get finished. Is there something more about it we should know? Maybe some work is already done?
• We have read that sympy supports python 2 and 3. How does this affect the development process?
• How does QEPCAD fit into the existing modules ecosystem? Should our work go into its own module or inside an already existing one?
• What's the merging policy for a new module? One monolithic PR with functional code? Or several small PR that might not be usable yet?
  
• Any further help or comments are also welcome :)
  

Best regards, Ferran.

[Jason Moore]

Ferran,

Welcome to SymPy! I'll answer some of the questions that I know, other will chime in for the rest.

> We have read that sympy supports python 2 and 3. How does this affect the development process?

You should write your code for Python 3.5 and when you submit a pull request our continuous integration service will run the tests on other versions of Python. You'll then need to fix any errors. We have a compatibility module to help with many of the common needs for dual support of Python 2 and 3. You can also test your code locally on both versions. I recommend using conda to switch between Python 2 and 3 environments.

> We have read that sympy supports python 2 and 3. How does this affect the development process?

We highly recommend smaller atomic pull requests. You are much more likely to get reviewed in a timely fashion if you submit small PRs.

> Any further help or comments are also welcome :)

I recommend starting here: https://github.com/sympy/sympy/wiki/introduction-to-contributing. And don't be shy about asking questions here or on the gitter channel.

Jason
moorepants.info
+01 530-601-9791

--
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+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/2a351f04-26bf-405a-a8bc-76eb6025f5eb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Aaron Meurer]

Can you clarify what QEPCAD is?

Aaron Meurer

--

[Ferran Pujol Camins]

Thank you Jason.

QEPCAD: Quantifier Elimination by Partial Cylindrical Algebraic Decomposition
A brief introduction: https://www.usna.edu/CS/qepcadweb/B/QE.html

Here's the discussion of your GSOC proposal: https://groups.google.com/d/msg/sympy/Ujznd13xfgw/1TB6Yg9G2qkJ

El divendres, 16 setembre de 2016 17:12:28 UTC+2, Aaron Meurer va escriure:

Can you clarify what QEPCAD is?

Aaron Meurer

On Fri, Sep 16, 2016 at 8:57 AM, Ferran Pujol Camins <ferranpu...@gmail.com> wrote:

Hello,
I represent a group of 6 students from the maths school (FME) of the Universitat Politècnica de Catalunya.
In one of our courses we have been assigned to the task of implementing QEPCAD in python using sympy. Our goal is to develop a module that can be merged into sympy.

We have just started, so our knowledge of QEPCAD and sympy is limited, but we expect to success in our goal by the end of the semester. We would really appreciate some help to get started.

• We have seen that QEPCAD was in a GSOC proposal. AFAIK, the proposal was not accepted or the project didn't get finished. Is there something more about it we should know? Maybe some work is already done?
• We have read that sympy supports python 2 and 3. How does this affect the development process?
• How does QEPCAD fit into the existing modules ecosystem? Should our work go into its own module or inside an already existing one?
• What's the merging policy for a new module? One monolithic PR with functional code? Or several small PR that might not be usable yet?
  
• Any further help or comments are also welcome :)
  

Best regards, Ferran.

--
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.

[Aaron Meurer]

Ah. I had not seen the QEP part of that acronym before. 

No, there is no work completed thus far. To answer the other questions:

- We do support Python 2.7 and 3.3-3.5. When you make a pull request Travis CI will test all of these automatically. You mainly need to make sure to use things from sympy.core.compatibility when necessary. 

- I highly recommend splitting things into smaller atomic pull requests wherever possible. For this project, it is also a good idea to discuss your design plans here or on an issue first, since it is a relatively complicated project. That includes discussing the API for the module, and discussing the prerequisites that need to be implemented first. 

Aaron Meurer 

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/3d7602e2-132c-4a60-b35c-92d013a87e53%40googlegroups.com.

[Reinhard Oldenburg]

Hi all,
having quantifier elimination in sympy would be great. However, some thoughts:
- This is a non-trivial piece of software, I hope your advisor knows that.
- Performance is a key issue. QEPCAD is written in C and still much to slow for many easy problems. Why don't you look at RegularChains as implemented in Maple? There is a quantifier elimination on top of this (C. Chen and M. Moreno Maza. Quantifier Elimination by Cylindrical Algebraic Decomposition Based on Regular Chains. In Proc. ISSAC 2014, pages 91–98, 2014.)
So, good luck - I'd be happy if something useful comes out of this because QE is from my point of view (math education) one of the most interesting features a computer algebra system can have but up to now, Mathematica is the only system that can be used - and it is far too expensive for wide use in education.
Reinhard

[Aaron Meurer]

I would reiterate that it's good to start to submit code (start a pull request) early, even before you have a working prototype, so that you can get feedback as early as possible. This is good for any project, but doubly so for a difficult project. Not getting feedback as early as possible would be setting yourself up for failure. 

Aaron Meurer

--
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+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d0280170-803e-48a5-b262-b2ac3a0a4760%40googlegroups.com.

[Ferran Pujol Camins]

Hello, we are indeed working on a prototype for the projection and extension phase. We are going to reach you for feedback ASAP.

During the extension phase, we generate a set of (n+1)-dimensional cell sample points by appending a new coordinate to a n-dimensional sample point from the previous iteration. The coordinate we append is the root of a certain polynomial. What's the best way to model this points?

• Point class from geometry package? (Does it handle numbers as 1d points?) Can we create Points with coordinates being:
  
• AlgebraicNumber
• RootOf

Which one is more adequate?

Best regards, Ferran

El dimarts, 20 setembre de 2016 19:55:54 UTC+2, Aaron Meurer va escriure:

I would reiterate that it's good to start to submit code (start a pull request) early, even before you have a working prototype, so that you can get feedback as early as possible. This is good for any project, but doubly so for a difficult project. Not getting feedback as early as possible would be setting yourself up for failure. 

Aaron Meurer

On Tue, Sep 20, 2016 at 3:25 AM, 'Reinhard Oldenburg' via sympy <sy...@googlegroups.com> wrote:

Hi all,
having quantifier elimination in sympy would be great. However, some thoughts:
- This is a non-trivial piece of software, I hope your advisor knows that.
- Performance is a key issue. QEPCAD is written in C and still much to slow for many easy problems. Why don't you look at RegularChains as implemented in Maple? There is a quantifier elimination on top of this (C. Chen and M. Moreno Maza. Quantifier Elimination by Cylindrical Algebraic Decomposition Based on Regular Chains. In Proc. ISSAC 2014, pages 91–98, 2014.)
So, good luck - I'd be happy if something useful comes out of this because QE is from my point of view (math education) one of the most interesting features a computer algebra system can have but up to now, Mathematica is the only system that can be used - and it is far too expensive for wide use in education.
Reinhard

--
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 post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

[Aaron Meurer]

The geometry package only handles 2D points. You may need to create a
new point class specifically to represent a point from an algebraic
affine space.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/5a77c805-d5b1-423f-a426-f81033a85fe4%40googlegroups.com.

[Ferran Pujol Camins]

In sympy 1.0 docs  I see a general n-dimensional point:
http://docs.sympy.org/latest/modules/geometry/points.html

Anyway, let's say we create our custom class.  What's the appropiate class to store each coordinate? AlgebraicNumber or RootOf? What they differ on?

> email to sympy+unsubscribe@googlegroups.com.

> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/5a77c805-d5b1-423f-a426-f81033a85fe4%40googlegroups.com.
>
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/p-PcoCJMiN0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6Kk%2BeHAuX7%2BZMee%3DryMynWOAxxF_jw4S%2B8e_zuh9MTS4Q%40mail.gmail.com.

[Kalevi Suominen]

On Saturday, October 8, 2016 at 3:40:47 PM UTC+3, Ferran Pujol Camins wrote:

In sympy 1.0 docs  I see a general n-dimensional point:
http://docs.sympy.org/latest/modules/geometry/points.html

Anyway, let's say we create our custom class.  What's the appropiate class to store each coordinate? AlgebraicNumber or RootOf? What they differ on?

The most important difference is that objects of RootOf class have no arithmetic operations defined other than those inherited from Expr class. That makes computations with them inefficient.

[Alan Bromborsky]

You might find the sympy modules at github.com/brombo/galgebra useful since they include an n-dimensional vector space with operations.  Look at galgebra.pdf in the doc directory for a complete description.  The following link might also be of use -

en.wikipedia.org/wiki/Conformal_geometric_algebra

--

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+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/091d7027-0c60-4a5e-911e-1e908160f0e1%40googlegroups.com.

[Ferran Pujol Camins]

Hello,
thanks for your feedback. We are going to simply use python lists to model points by now though.

We have made some progress, and we would love some more feedback.

For the lifting phase, we want to compute the real roots of a polynomial after some of its variables have been substituted by algebraic numbers. Something like this:

rp = Poly(x**5-x**3+2*x-2-1)
r = (rp.real_roots())[0]

p = Poly(x**2+y**2+x*y)
q = p.eval(r)
q.real_roots()

This gives the following error:

NotImplementedError: sorted roots not supported over EX

However, solve correctly determines that there are no real roots, and gives complex roots parametrized with the CRootOf object.

>>> solve(q)
[(-1 + sqrt(3)*I)*CRootOf(x**5 - x**3 + 2*x - 3, 0)/2, -(1 + sqrt(3)*I)*CRootOf(x**5 - x**3 + 2*x - 3, 0)/2]

Why real_roots can't do this? What are the differences between using real_roots() and solve?

El dissabte, 8 octubre de 2016 16:25:04 UTC+2, brombo va escriure:

You might find the sympy modules at github.com/brombo/galgebra useful since they include an n-dimensional vector space with operations.  Look at galgebra.pdf in the doc directory for a complete description.  The following link might also be of use -

en.wikipedia.org/wiki/Conformal_geometric_algebra

On Sat, Oct 8, 2016 at 9:06 AM, Kalevi Suominen <jks...@gmail.com> wrote:

On Saturday, October 8, 2016 at 3:40:47 PM UTC+3, Ferran Pujol Camins wrote:

In sympy 1.0 docs  I see a general n-dimensional point:
http://docs.sympy.org/latest/modules/geometry/points.html

Anyway, let's say we create our custom class.  What's the appropiate class to store each coordinate? AlgebraicNumber or RootOf? What they differ on?

The most important difference is that objects of RootOf class have no arithmetic operations defined other than those inherited from Expr class. That makes computations with them inefficient.

--
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 post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

[Kalevi Suominen]

The implementation of  real_roots()  currently works only with univariate polynomials having integer (or rational) coefficients. To compute the real roots  y  of  p  you have to eliminate  x  algebraically from the two polynomials  rp  and  p, not by substitution.
This can done by passing to the resultant with respect to x:  f = resultant(rp, p, x). Then  real_roots(f)  will give the real values of  y. Note that all possible real values of  y  are included for all values of  x (though, in this case, there are none). Additional checks are needed to find out which  y  corresponds to which value of  x,  if necessary.

[Ferran Pujol Camins]

Thank you Kalevi, is something like this what solve does?

El diumenge, 30 octubre de 2016 19:30:44 UTC+1, Kalevi Suominen va escriure:

[Kalevi Suominen]

Perhaps it can be said that the Gröbner basis method applied by solve is related.

However, I suspect that the elimination method would not be the proper one
for solving equations with non-integral coefficients. It would probably be more
efficient to extend the real_root function to work on polynomials with real algebraic
coefficients. For that purpose, a subclass, RealAlgebraicNumber, of AlgebraicNumber
would have to be defined. Such a class can be provided with comparison methods
that would make it possible to separate real roots the way real_roots does. Such
comparisons are also needed for CAD.

[Ferran Pujol Camins]

What can be done to find roots of p by "substituting" y for an algebraic number a is to compute Res(p, y-a, y).
Thank you for your help.

El dimarts, 1 novembre de 2016 18:08:09 UTC+1, Ferran Pujol Camins va escriure:

[Ferran Pujol Camins]

Yeah this last thing I said does not work in sympy. We'll investigate further, thank you.

El dimarts, 1 novembre de 2016 19:08:20 UTC+1, Ferran Pujol Camins va escriure:

[Enric Cosp Arqué]

Hi all, we are having some troubles using the sympy function: subresultants (sympy.polys.polytools.subresultants(f, g, *gens, **args))

Our goal is to compute the subresultants of two given polynomials. We are comparing the output of this sympy function with some examples published in some related articles and they are not matching.

It happens that this sympy function gives the same results as mathlab function: polylib::subresultant. Take a look at: https://es.mathworks.com/help/symbolic/mupad_ref/polylib-subresultant.html

On the other hand, the results found in the articles match the Wolframalpha function: Subresultants[poly1, poly2, var].

This two functions don't match one another. 

Could you please provide some help?

[Aaron Meurer]

Can you give the polynomials for which they don't agree?

Aaron Meurer 

--

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+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/43e0d68e-6be0-4ff6-adc3-1f11a8a8213b%40googlegroups.com.