SIGN DETERMINATION IN RESIDUE NUMBER-SYSTEMS

Sign determination is a fundamental problem in algebraic as well as ge ometric computing. It is the critical operation when using rear algebr aic numbers and exact geometric predicates. We propose an exact and ef ficient method that determines the sign of a multivariate polynomial e xpression with rational coefficients. Exactness is achieved by using m odular computation. Although this usually requires some multiprecision computation, our novel techniques of recursive relaxation of the modu li and their variants enable us to carry out sign determination and co mparisons by using only single precision. Moreover, to exploit modem d ay hardware, we exclusively rely on floating point arithmetic, which l eads us to a hybrid symbolic-numeric approach to exact arithmetic. We show how our method can be used to generate robust and efficient imple mentations of real algebraic and geometric algorithms including Sturm sequences, algebraic representation of points and curves, convex hull and Voronoi diagram computations and solid modeling. This method is hi ghly parallelizable, easy to implement, and compares favorably with kn own multiprecision methods from a practical complexity point of view. We substantiate these claims by experimental results and comparisons t o other existing approaches. (C) 1999-Elsevier Science B.V. All rights reserved.