The current algebraic extension code in the polys (like Poly(extension=[sqrt(x)])) is quite weak. Will this project require expanding those abilities?
Aaron Meurer On Tue, Mar 24, 2015 at 7:26 AM, Kalevi Suominen <jks...@gmail.com> wrote: > > > On Tuesday, March 24, 2015 at 2:44:03 AM UTC+2, Luv Agarwal wrote >> >> I have updated my proposal. >> 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. -- 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/CAKgW%3D6LqqBnuDj5WayBLiFVJg_GsGMxE2upfYZvN6Jff26AgeQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
