A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom

Details A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom

2007-11-29

arxiv.org/abs/0711.4656v2

Computer Science

Computational Geometry

Scientific paper

This article considers the problem of solving a system of $n$ real polynomial equations in $n+1$ variables. We propose an algorithm based on Newton's method and subdivision for this problem. Our algorithm is intended only for nondegenerate cases, in which case the solution is a 1-dimensional curve. Our first main contribution is a definition of a condition number measuring reciprocal distance to degeneracy that can distinguish poor and well conditioned instances of this problem. (Degenerate problems would be infinitely ill conditioned in our framework.) Our second contribution, which is the main novelty of our algorithm, is an analysis showing that its running time is bounded in terms of the condition number of the problem instance as well as $n$ and the polynomial degrees.

Affiliated with

Also associated with

No associations

Rating

A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-45643