There was also a GSoC project on this a couple of years ago (https://github.com/sympy/sympy/wiki/GSoC-2013-Application-Katja-Sophie-Hotz:-Faster-Algorithms-for-Polynomials-over-Algebraic-Number-Fields), and I am not fully caught up on what still needs to be implemented. IIRC, though, there were some things that were technically implemented, but were too slow to be usable in practice (particularly multiple extensions, if I am not mistaken).
Aaron Meurer On Tue, Mar 24, 2015 at 4:54 PM, Kalevi Suominen <jks...@gmail.com> wrote: > > > On Tuesday, March 24, 2015 at 11:28:11 PM UTC+2, Aaron Meurer wrote: >> >> The current algebraic extension code in the polys (like >> Poly(extension=[sqrt(x)])) is quite weak. Will this project require >> expanding those abilities? > > > Aaron, > I have not delved deeper into the matter, but it looks like the current > methods in > numberfields would essentially suffice, at least if they function as > expected. > The central one is primitive_element() which enables the > construction of an extension containing any (finite) family of algebraic > numbers. > On the other hand, the methods in AlgebraicField require revision. > > Kalevi >> >> >> 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+un...@googlegroups.com. >> > To post to this group, send email to sy...@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/c9fbe82d-800b-4fe8-8c84-54b646a07cd4%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%3D6%2BwTFOhimT%3Dn6oFc0qeyoReP9qSnTgDYx%3Dgnr0y8%2BTSRg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
