Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleNumeric-Symbolic Algorithms for Evaluating One-Dimensional Algebraic Sets
Author(s) Shankar Krishnan, Dinesh Manocha
TypeArticle in Conference Proceedings
AbstractWe present efficient algorithms based on a combination of numeric and symbolic techniques for evaluating one-dimensional algebraic sets in a subset of the real domain. Given a description of a one-dimensional 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 well-conditioned inputs. The resulting algorithm is iterative and its complexity is output sensitive. It has been implemented in floating-point arithmetic and we highlight its performance in the context of computing intersection of high-degree algebraic surfaces.
Translation No
Refereed No
ConferencenameInternational Symposium on Symbolic and Algebraic Computation