On Sep 20, 6:35 am, Bill Hart <[EMAIL PROTECTED]> wrote: > 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.
My code really does do everything using interval arithmetic unless it needs to prove an equality, and then fall back to deducing equality algebraically. I wouldn't say it was "very difficult" to implement, although it certainly wasn't trivial either. > 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. ... There are two costs I'm avoiding. First, if you're working in an algebraic extension field of high degree, polynomial arithmetic can't be all that fast; 128-bit interval arithmetic will be faster than degree-128 polynomial arithmetic. Second, if you need to add two numbers that are in different algebraic extensions of Q, I delay computing a new algebraic extension of Q holding the sum as long as possible (in the hopes that it will never be necessary). I've read several papers by people doing more or less what I'm trying to do (compute topological information about algebraic curves in the plane, or algebraic surfaces in 3 dimensions). The typical approach ends up computing many algebraic numbers (that would end up being in many different algebraic extensions of Q) and checking their sign; if the interval arithmetic suffices to prove that the number is non-zero, then you never need to compute that new field at all. And these papers do report significant speedups by using interval arithmetic first, and doing exact algebraic calculations only to prove equalities (or by avoiding the exact calculations altogether, and proving equalities using very high-precision interval arithmetic and a root separation bound). I have not yet written the code to use my algebraic reals package, so I have no evidence yet that the delayed computation improves performance; but I am strongly hopeful that it will. > If you could implement this faster using adaptive root refinement, > then you definitely should. But I'm unconvinced that it would be > faster. It depends on your use case. If you end up doing long calculations with numbers that end up all being in the same low-degree extension of Q, then the interval arithmetic may well end up being slower than the polynomial arithmetic would be. If all the numbers you compute end up being involved in equality proofs, so that you need exact computation anyway, then the interval arithmetic is definitely wasted effort. On the other hand, if you can avoid computing in a high-degree extension of Q, or especially if you can avoid computing the defining polynomial for a high-degree extension of Q, then the interval arithmetic approach can be arbitrarily faster than the algebraic approach. Here's one (heavily biased) example: sage: sum([sqrt(AA(i)) for i in range(1, 1000)]) [21065.833110879048 .. 21065.833110879056] I'm pretty sure that doing computations with this number algebraically requires dealing with polynomials of degree at least 2^168 (there are 168 primes less than 1000), which is obviously impossible. Carl --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
