On Tuesday, March 24, 2015 at 2:44:03 AM UTC+2, Luv Agarwal wrote
> I have updated my proposal > <https://github.com/sympy/sympy/wiki/GSoC-2015-Application-Luv-Agarwal:-Cylindrical-Algebraic-Decomposition> > . > Please have a look especially at the Timeline part. Is there anything that > I should add or remove?. > > Thanks > Luv Agarwal > Thank you, Luv. I feel there is something I should add about root isolation. It may also affect the timetable. Implementing log() for algebraic numbers should not be difficult. One can pass to numerical values. They are approximate, of course, but then log itself is only used for an estimate. The comparisons of algebraic numbers are harder to implement. As noted before, the methods presented in AlgebraicField cannot be used because they do not conform to the standard order of real numbers. Instead, one could proceed as follows. If a and b are algebraic numbers, the inequality a > b is equivalent to a - b > 0. So it is enough to find the sign of a - b. In other words, to find a field K of algebraic numbers containing a and b , and to implement K.sign(x). An algebraic number field K = Q(theta) is generated by a single algebraic number theta , called the primitive element of the field. If the degree of the minimal polynomial of theta is n , each element of K has a unique representation as a polynomial a = p(theta) with rational coefficients and of degree < n. To compute the sign of a , one looks for an interval (u, v) containing theta and such that the polynomial p(t) has no roots in the interval. Then the sign of a is the sign of p(t) at any t in the interval. One can start with an interval isolating the root theta of the minimal polynomial and then refine it until it contains no roots of p. Such an interval exists if p != 0 , since then also p(theta) != 0. One can do the refinement by simply bisecting the interval, or else following the method of dup_isolate_real_roots_sqf based on representing the root by a continued fraction. The classical method of determining the number of roots in an interval is by means of Sturm's theorem. The method used in dup_isolate_real_roots_sqf is simpler in principle. It is based on using a Moebius mapping to transform the interval to the positive real axis. If the coefficients of the transformed polynomial have the same sign (as reported by dup_sign_variations), it has no positive roots. (This is special case of Descartes' rule of signs which is trivial to verify.) Then the original polynomial has no roots in the refined isolating interval. An extra bonus is that the coefficients of the Moebius mapping are readily obtained from the convergents of the continued fractions. In summary: Implementation of inequalities in algebraic number fields is a substantial task. You may want to reconsider your timeline on that part. Best wishes, Kalevi -- 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 post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/3bd8afe9-f2b9-49cf-a2a2-9381e6f0eb35%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
