Title  NumericSymbolic Algorithms for Evaluating OneDimensional Algebraic Sets 
Author(s)  Shankar Krishnan, Dinesh Manocha 
Type  Article in Conference Proceedings 
Abstract  We present efficient algorithms based on a combination of numeric and symbolic techniques for evaluating onedimensional algebraic sets in a subset of the real domain. Given a description of a onedimensional algebraic set, we compute its projection using resultants. We represent the resulting plane curve as a singular set of a matrix polynomial as opposed to roots of a bivariate polynomial. Given the matrix formulation, we make use of algorithms from numerical linear algebra to compute start points on all the components, partition the domain such that each resulting region contains only one component and evaluate it accurately using marching methods. We also present techniques to handle singularities for wellconditioned inputs. The resulting algorithm is iterative and its complexity is output sensitive. It has been implemented in floatingpoint arithmetic and we highlight its performance in the context of computing intersection of highdegree algebraic surfaces. 
File 

Language  English 
Pages  5967 
Year  1995 
Translation 
No 
Refereed 
No 
Conferencename  International Symposium on Symbolic and Algebraic Computation 