On Tuesday, March 24, 2015 at 5:56:59 PM UTC+5:30, Kalevi Suominen wrote: > > > > 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. > This can be done using K.convert(a)
> > 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. > Thanks Kalevi for giving such a detailed description. > In summary: Implementation of inequalities in algebraic number fields is a > substantial task. You may want > to reconsider your timeline on that part. > The current status of root isolation makes it pretty easy to implement the above idea and I have given sufficient amount of time to this part of implementation in my timeline. What reconsideration are you talking about? > > 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 [email protected]. To post to this group, send email to [email protected]. 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/c16f2dd0-cfd4-49e4-b60c-8e959c628df8%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
