On 20 Sep, 06:39, Robert Bradshaw <[EMAIL PROTECTED]>
wrote:
> Carl Witty did an implementation of the Algebraic Reals by letting
> every element be specified by a polynomial and an interval containing
> a single root. I've been wondering if the same approach could be
> feasible for Qbar, the main difficulty being that the product of two
> balls in C is not a ball (though it is close for small enough
> epsilon). This might be much faster, for instance proving inequality
> is done by numerical verification (with adaptive root refinement) and
> if that fails it falls back to trying to deduce equality algebraically.
I don't think it can fall back to deducing equality algebraically.
That is tantamount to recomputing everything algebraically from the
start. It would be very difficult to implement. You'd need the
numerical approximation method to always succeed, otherwise you may as
well do everything algebraically from the start.
But I don't see where the complexity would be in doing it
algebraically. I agree things couldn't be done algebraically in Pari
since it doesn't have fast polynomial arithmetic. But we are assuming
that SAGE will have it. Surely in order to verify two elements are not
equal, one needs expressions for those elements as complex numbers.
Sure, once you have those expressions, if they differ by a fair bit
then you can easily decide equality. But one first has to get those
expressions, and that may require you to work to quite a high
precision. In the algebraic model, to determine equality, one would
simply need to do two compositions of polynomials, one subtraction and
a reduction modulo a certain polynomial. These should all be fairly
much instantaneous operations. Moreover, if you already had reduced
polynomial expressions for your elements then it is just a comparison
of polynomials, which might just boil down to comparing two integers
if they are sufficiently different. Also, even if you don't have such
polynomial expressions one can make comparison much faster by checking
whether the result is zero as the polynomial is being reduced. As soon
as it turns out to be different to zero, one returns false. Sure,
proving equality has the full complexity, but this is also a problem
with the adaptive root refinement method.
If you could implement this faster using adaptive root refinement,
then you definitely should. But I'm unconvinced that it would be
faster.
Bill.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
