On Monday, March 20, 2017 at 11:50:53 PM UTC, Nils Bruin wrote: > > On Monday, March 20, 2017 at 3:03:05 PM UTC-7, Dima Pasechnik wrote: >> >> >> surely you can do this, but it seems to be harder to certify if a number >> is zero or not. >> > > Exactly. That's the idea of Allan's approach: rather than tracking these > questions in characteristic 0, you do it in a finite field of some (large) > characteristic. The bet that unequal numbers will have unequal reduction > modulo your large modulus will almost certainly hold in practice, and if > you track it carefully you know when it fails. THEN you take the hit, lift > everything you had to characteristic 0, and use a different modulus. It > means you basically never have to work with number field representations, > and certainly not run expensive operations such as reducing lattices of > algebraic integers. > > Tracking real embeddings only involves tracking some mild inequalities > (which can be refined using newton iteration whenever necessary). >
the idea that you don't need irreducible polynomials and/or polynomial factorisation is behind the line of research described in "Algorithms in Real Algebraic Geometry <https://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.html>" by Basu, Pollack, and Roy. I have not heard anything about using finite fields to speed up what they do (probably because there are no anywhere complete implementations of algorithms they describe available). Dima -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
