Condition Analysis of Overdetermined Algebraic Problems

In analogy to numerical linear algebra, the evolving numerical polynomial algebra studies the modifications of classical polynomial algebra necessary to accomodate inaccurate data and inexact computation. A standard part of this endeavor is a condition analysis of the problems to be solved, i.e. an assessment of the sensitivity of their results with respect to variations in their data. In this paper, we extend this condition analysis to overdetermined problems, like greatest common divisors, multivariate factorization etc. Here we must consider the fact that results exist only for data from restricted low-dimensional domains. The discontinuous dependence of the results on the data, however, is “smoothed” by their limited accuracy so that a condition analysis becomes meaningful. As usual, the condition numbers indicate the accuracy with which results may be specified.