I have added the implementation details of few functions in the draft.
How can I implement refine_root (and dup_isolate_real_roots_sqf) for polynomials over algebraic numbers?
Thanks, I looked at them.
How can I implement dup_isolate_real_roots_sqf for algebraic domains?
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
The current algebraic extension code in the polys (like
Poly(extension=[sqrt(x)])) is quite weak. Will this project require
expanding those abilities?
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).
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
Is primitive_element doing something similar to simple?. If yes, will there be difference in efficiency of both of these as they take input in different form?.
On Tuesday, March 24, 2015 at 2:44:03 AM UTC+2, Luv Agarwal wroteI 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
What reconsideration are you talking about?
Kalevi